递归算法的三个分解步骤

递归是⼀个重要的算法，希望你也能学得会。递归的三⼤步骤

编写递归函数的步骤，可以分解为三个。递归第⼀个步骤：明确函数要做什么

对于递归，⼀个最重要的事情就是要明确这个函数的功能。这个函数要完成⼀样什么样的事情，是完全由程序员来定义的，当写⼀个递归函数的时候，先不要管函数⾥⾯的代码是什么，⽽要先明确这个函数是实现什么功能的。⽐如，我定义了⼀个函数，这个函数是⽤来计算n的阶乘的。// 计算n的阶乘（假设n不为0）int f(int n) {

// 先不管内部实现逻辑}

这样，就完成了第⼀个步骤：明确递归函数的功能。递归第⼆个步骤：明确递归的结束（退出递归）条件

所谓递归，就是会在函数的内部逻辑代码中，调⽤这个函数本⾝。因此必须在函数内部明确递归的结束（退出）递归条件，否则函数会⼀直调⽤⾃⼰形成死循环。意思就是说，需要有⼀个条件（标识符参数）去引导递归结束，直接将结果返回。要注意的是，这个标识符参数需要是可以预见的，对于函数的执⾏返回结果也是可以预见的。

⽐如在上⾯的计算n的阶乘的函数中，当n=1的时候，肯定能知道f(n)对应的结果是1，因为1的阶乘就是1，那么我们就可以接着完善函数内部的逻辑代码，即将第⼆元素（递归结束条件）加进代码⾥⾯。// 计算n的阶乘（假设n不为0）int f(int n) { if (n == 1) { return 1; }}

当然了，当n=2的时候，也可以知道n的阶乘是2，那么也可以把n=2作为递归的结束条件。// 计算n的阶乘（假设n>=2）int f(int n) { if (n == 2) { return 2; }}

这⾥就可以看出，递归的结束条件并不局限，只要递归能正常结束，任何结束条件都是允许的，但是要注意⼀些逻辑上的细节。⽐如说上⾯的n==2的条件就需要n>2，否则当n=1的时候就会被漏掉，可能导致递归不能正常结束。完善⼀下就是当n<=2的时候，f(n)都会等于n。// 计算n的阶乘（假设n不为0）int f(int n) { if (n <= 2) { return n; }}

这样，就完成了第⼆步骤：明确递归的退出条件。递归的第三个步骤：找到函数的等价关系式

递归的第三个步骤就是要不断地缩⼩参数的范围，缩⼩之后就可以通过⼀些辅助的变量或操作使原函数的结果不变。⽐如在上⾯的计算n的阶乘的函数中，要缩⼩f(n)的范围，就可以让f(n)=n* f(n-1)，这样范围就从n变成了n-1，范围变⼩了，直到范围抵达n<=2退出递归。并且为了维持原函数不变，我们需要让f(n-1)乘上n。说⽩了，就是要找到⼀个原函数的等价关系式。在这⾥，f(n)的等价关系式为n*f(n-1)，即f(n)=n*f(n-1)。// 计算n的阶乘（假设n不为0）int f(int n) { if (n <= 2) { return n; }

// 把n打出来看⼀下，你就能明⽩递归的原理了 System.out.println(n); // 加⼊f(n)的等价操作逻辑 return n * f(n - 1);}

到这⾥f(n)的功能就基本实现了。每次写递归函数的时候，强迫⾃⼰跟着这三个步骤⾛，能达到事半功倍的效果。另外也可以看出，第三个步骤⼏乎是最难的⼀个步骤。

递归案例1：斐波那契数列

斐波那契数列的是这样⼀个数列：1、1、2、3、5、8、13、21、34、….，即第⼀项 f(1) = 1、第⼆项 f(2) = 1、…..、第 n 项⽬为 f(n)=f(n-1)+f(n-2)，求第 n项的值是多少。

递归第⼀个步骤：明确函数要做什么假设f(n)的功能是求第n项的值，代码如下：int f(int n) { }

递归第⼆个步骤：明确递归的结束（退出递归）条件

显然，当n=1或者n=2的时候，我们可以轻易得知结果是f(1)=f(2)=1。所以递归结束的条件可以是n<=2，代码如下：int f(int n) { if (n <= 2) { return 1; }}

递归的第三个步骤：找到函数的等价关系式

在题⽬中已经有等价关系式了，即f(n) = f(n-1) + f(n-2)。int f(int n) {

// 先写递归结束条件 if (n <= 2) { return 1; }

// 写等价关系式 return f(n - 1) + f(n - 2);}

这个案例⾮常简单。递归案例2：⼩青蛙跳台阶

⼀只青蛙⼀次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上⼀个n级的台阶总共有多少种跳法。递归第⼀个步骤：明确函数要做什么

假设f(n)的功能是求青蛙跳上⼀个n级台阶总共有多少种跳法，代码如下：int f(int n) {}

递归第⼆个步骤：明确递归的结束（退出递归）条件

上⾯说了，求递归结束的条件，直接把n压缩到很⼩很⼩就⾏了，因为n越⼩我们就能越直观地算出f(n)的多少。这⾥，当n=1的时候，f(1)=1，因此可以将n=1作为递归结束条件。int f(int n) { if (n == 1) { return 1; }}

递归的第三个步骤：找到函数的等价关系式

接下来找到函数的等价关系式就是这个函数的难点了，下⾯来分析⼀下。1.假设台阶只有⼀级，那么显然只有⼀种跳法。

2.要是有两级台阶，那么就有两种跳法：⼀种是⼀次跳⼀级台阶，⼀种是⼀次跳两级台阶。

3.要是有三级台阶，青蛙的第⼀步就有两种跳法：当青蛙第⼀步跳了⼀级台阶，那么就只剩下了两级台阶，将问题转化成为两级台阶的跳法，当青蛙第⼀步跳了两级台阶，那么就只剩下了⼀级台阶，就将问题转化为了⼀级台阶的跳法。4.n阶台阶与三阶台阶的分析是⼀样的。

我们把跳n级台阶时的跳法看成是n的函数，记为f(n)。当n=1时，f(1)=1；当n=2时，f(2)=2；当n=3时，f(3)=f(2)+f(1)；当n=4时，f(4)=f(3)+f(2)......当n=n的时候，f(n)=f(n-2)+f(n-1)，显然这是⼀个斐波那契数列。int f(int n) {

// 先写递归结束条件 if (n == 1) { return 1; }

// 写等价关系式 return f(n - 1) + f(n - 2);

}

要注意的是，上⾯的递归结束条件显然不够严谨，因为当n=2的时候，这⾥的递归退出条件就不能够限制递归的正常退出了，需要稍微完善⼀下。int f(int n) {

// 先写递归结束条件 if (n < 1) { return 0; }

if (n == 1) { return 1; }

if (n == 2) { return 2; }

// 写等价关系式 return f(n - 1) + f(n - 2);}

因此建议在写完递归函数之后要回头去校验递归退出条件。递归案例3：反转单链表

反转单链表是⼀个常见的算法。例如链表为1->2->3->4。反转后为 4->3->2->1。链表的节点定义如下：class Node { int date;

Node next; // 存储下⼀个节点}

递归第⼀个步骤：明确函数要做什么

假设函数reverseList(head)的功能是反转单链表，其中head表⽰链表的头节点。代码如下：Node reverseList(Node head) {}

递归第⼆个步骤：明确递归的结束（退出递归）条件

当链表只有⼀个节点，或者如果是空链表的话，就直接返回head就⾏了。Node reverseList(Node head) { if (head == null || head.next == null){ return head; }}

递归的第三个步骤：找到函数的等价关系式// ⽤递归的⽅法反转链表

public static Node reverseList2(Node head) { // 递归结束条件

if (head == null || head.next == null) { return head; }

// 递归反转⼦链表

Node newList = reverseList2(head.next); // 改变1，2节点的指向 // 通过head.next获取节点2 Node t1 = head.next; // 让2的next指向 2 t1.next = head; // 1的next指向null head.next = null; // 把调整之后的链表返回 return newList;}

递归的⼀些优化思路

递归的优化也是⼀门学问，这⾥列出两个优化思路。

考虑是否重复计算

递归的时候很可能会出现⼦运算重复计算的问题。什么是⼦运算？f(n-1)，f(n-2)等就是⼦运算。例如，在上⾯的案例中，等价表达式是f(n)=f(n-1)+f(n-2)，递归调⽤的状态图如下：

可以看出，在递归调⽤的时候，重复计算了两次f(5)，五次f(4)等......这时⾮常恐怖的，因为n越⼤，重复计算的就越多，因此必须想办法优化。

如何优化呢，⼀般的做法是把计算的结果保存起来，例如把f(4)的结果保存起来，当再次要计算f(4)的时候，先判断⼀下之前是否计算过，计算过就可以直接取结果了。⽤什么保存呢，可以⽤数组或者HashMap保存，这⾥⽤数组保存好了。把n作为数组下标，f(n)作为值，例如arr[n]=f(n)这样⼦。当f(n)还没有计算过的时候，我们让arr[n]等于⼀个特殊值，例如arr[n]=-1。当我们要判断的时候，如果arr[n]=-1，则证明f(n)没有计算过，否则，f(n)就已经计算过了，且f(n)=arr[n]。// 假定arr数组已经初始化好int f(int n) { if (n <= 1) { return n; }

// 先判断有没计算过 if (arr[n] != -1) { // 计算过，直接返回 return arr[n]; } else {

// 没有计算过，递归计算,并且把结果保存到 arr数组⾥ arr[n] = f(n - 1) + f(n - 1); reutrn arr[n]; }}

也就是说，使⽤递归的时候，必须要考虑有没有重复计算，如果重复计算了，⼀定要把计算过的状态值保存起来。考虑是否可以⾃底向上

对于递归，⼀般的思路是从上往下递归，直到递归到达最底层，再⼀层⼀层地把值返回。

这样的话，在n⽐较⼤的情况下，⽐如当n=10000的时候，就必须要往下递归10000层直到n<=1的时候才开始将结果逐层返回，可能会导致栈空间不够⽤⽽报出StackOverflowException的异常。

对于这种情况就可以考虑⾃底向上递归的做法。int f (int n) { if (n <= 2) { return n; }

int f1 = 1; int f2 = 2; int sum = 0;

for (int i = 3; i <= n; i++) { sum = f1 + f2; f1 = f2; f2 = sum; }

return sum;}

另外的，这种⽅法也可以被称为递推。总结

其实递归并不⼀定总是从上往下，也有很多从下往上的写法。⽐如可以从n=1开始，⼀直递归到n=1000，常⽤在⼀些排序组合的场景。⽽对于这种从下往上的写法，也是有相应的优化技巧。

最后要说的是，对于递归这种⽐较抽象的思想，需要⾃⼰多思考和多写才能对较好地掌握递归，可能要秃头才敢说对递归熟练吧（⼿动滑稽）。

\"就这样吧，再坏的也不要⾛了，再好的也不要来了。\"