开始之前
编程语言中，函数Func(Type a,……)直接或间接调用函数本身，则该函数称为递归函数。递归是一种计算过程，如果其中每一步都要用到前一步或前几步的结果，称为递归的。用递归过程定义的函数，称为递归函数，例如连加、连乘及阶乘等。凡是递归的函数，都是可计算的。这篇文章就是从宏观视角聊一聊递归这种算法思想，文章主要内容如下：
通过数组求和看递归的基本性质
链表的天然递归性
通过数组求和看递归的基本性质
递归代码的编写
递归代码的编写一是要知道递归终止条件，对于数组求和这个问题来说，其终止条件是数组中没有元素需要计算了，代码表示是：
// begin 表示从数组中哪个索引位置开始// 当begin == arr.length表示数组中没有剩余元素if (begin == arr.length) {return 0;}
二是要知道递归递推公式，就数组求和这个问题来说，递推公式是:
arr[begin] + sum(begin + 1, arr);
有了终止条件和递推公式，就可以写出递归求解数组中所有元素和的代码了，实现如下：
public int sum (int[] arr) {// 调用递归函数，初始从0开始return sum(0, arr);}// 递归函数public int sum(int begin, int[] arr) {// begin 表示从数组中哪个索引位置开始// 当begin == arr.length表示数组中没有剩余元素if (begin == arr.length) {return 0;}// 我只计算我拿到的数组中第一个元素的值// 和数组中剩余元素总和的和return arr[begin] + sum(begin + 1, arr); // 递归调用}
这里我们在第7行sum(int begin, int[] arr)这个方法中调用了sum(int begin, int[] arr)方法它自己，即16行的sum(begin + 1, arr)，这一点可能会让你觉得困惑。
我们可以这样理解，方法sum(int begin, int[] arr)是计算数组中从索引begin开始所有元素的总和，而该方法的计算规则是我计算的是当前数组起始位置begin所对应的元素值和数组中剩余元素的总和的和。那么，我就需要有个方法可以告诉我数组中剩余元素的总和是多少。
这时，刚好有个方法fun(int begin, int[] arr)，只要我告诉它数组是什么样的，以及从哪个索引位置开始计算，它就会告诉我数组中剩余元素的总和。只不过这个方法fun(int begin, int[] arr)所需的参数和我自己一样而已。于是，在代码中看起来就是方法sum(int begin, int[] arr)调用了它自己。
链表的天然递归性
代码实现
public ListNode removeElements(ListNode head, int val) {// 递归终止条件if (head == null) {return null;}// 调用方法removeElements将当前结点之后的链表部分中的// 和val值相等的结点删除ListNode result = removeElements(head.next, val);// 如果当前结点head的值等于val则返回resultif (head.val == val) {return result;} else {// 如果当前结点head的值不等于val则// 将result挂在当前结点head之后返回head.next = result;return head;}}
小结
这篇文章介绍了什么是递归。通过两个小例子介绍了如何编写一个递归函数。
