递归简述

数组求和

如上图为求解一个int数组中所有元素的和，此处是可以用一重循环解决，只是为了更直观简单的说明什么是递归，所以才以此为例。

一个递归函数应包含最基本的两部分：

1.求解初最基本问题（递归终止条件）

      **即当问题被拆分为最小时，应该如何处理**

2.将原问题转化为更小的问题

书写递归函数时，不应该被函数的自我调用逻辑所迷惑，应该注重当前函数所需要解决的问题，自我调用只是解决问题的一个步骤（可以理解为只是调用了一个子过程，子过程结束后返回相应结果，然后主过程继续运行）

链表删除节点

上图为利用递归函数，解决leetcode中删除头结点为head的链表中值为val的节点，非常简洁！

下图为未使用递归函数的解（代码量上升，且逻辑复杂）：

image.png

递归的代价

递归的代价

如上面列举的“数组求和”及“链表删除节点”，当数组元素足够多，或者链表节点足够多时，那么栈内存将会溢出~
并且递归调用函数实际也是会消耗更多的时间。

递归在处理线性问题时确实不具备优势，但是用递归处理树形结构数据时，将会是非常适合的，后续章节，我将记录利用递归思想处理树形数据结构