title: 如何理解递归
date: 2019-03-13 17:07:25
categories: 代码
tags: 算法学习

递归

定义

程序调用自身的编程技巧称为递归（ recursion）。

递归二字顾名思义就是：递过去，归回来。一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

注意：

  1. 递归就是在过程或函数里调用自身。
  2. 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

递归算法一般用于解决三类问题：

  1. 数据的定义是按递归定义的（fibonacci函数）
  2. 问题解法按递归算法实现（回溯）
  3. 数据的结构形式是按递归定义的（树的遍历，图的搜索）

代码分析

代码1

  2. private static boolean flag = true;
  3. private static void test1(){
  4.     for (int i = 0; i < 10; i++) {
  5.         if(flag && i == 6){
  6.             flag = false;
  7.             System.out.println("递归");
  8.             test1();
  9.         }
  10.         System.out.println("i = " + i);
  11.     }
  12. }

代码1运行结果

i = 0
i = 1
i = 2
i = 3
i = 4
i = 5
递归
i = 0
i = 1
i = 2
i = 3
i = 4
i = 5
i = 6
i = 7
i = 8
i = 9
i = 6
i = 7
i = 8
i = 9

代码2

  2. public static void test2(int n) {
  3.     System.out.println("1-lexe:" +  n);   //#1
  4.     if (n < 3)
  5.         test2(n + 1);
  6.     System.out.println("2-lexe:" +  n);   //#2
  7. }

代码2运行结果

1-lexe: 1
1-lexe: 2
1-lexe: 3
2-lexe: 3
2-lexe: 2
2-lexe: 1

test2方法流程解读：
首先， main() 调用了函数 test2(1) ，于是test2(1)中形参 n 的值是 1, 故打印语句 #1 输出了：1-lexe:1 。
然后，由于 n < 3 ，( 第 2 级 )的test2(n+1)被调用. 此时n+1=2，故打印语句 #1 输出了：1-lexe:2。
然后，由于 n < 3 ，( 第 3 级 )的test2(n+1)被调用. 此时n+1=3，故打印语句 #1 输出了：1-lexe:3。
由于此时，n=3 , 不再执行if语句。
然后执行 #2 语句 ， 因为此时 n 的值为 3 ， 故打印语句 #2 输出了： 2-lexe:3 。 —————————————-这时完成了一个“递过去”

此时函数调用完成
现在函数需要“归回来” ， 回到最后一次调用函数的地方 ， 即 n+1=2 的地方 ， 故打印语句 #2 输出了：2-lexe:2。
再返回上一级调用的地方 ， n =1 的地方 ， 故打印语句 #2 输出了：2-lexe:1。——————————————-完成了一个“归回来“

递归的理解

基本定义

谈到递归，我们会想到自己调用自己，比如如下代码段：

  1. void foo()
  2. {
  3.     // 自己调用自己就是递归
  4.     foo();
  5. }

而这个程序跑起来除了报一个「堆栈溢出」的错，根本没什么用，因为它不满足确定的返回条件，无法避免无限递归。一个完整的递归程序应该是这样的：

  1. void foo()
  2. {
  3.     // 返回部分
  4.     if (condition)
  5.     {
  6.         return;
  7.     }
  9.     // 递归部分
  10.     foo();
  11. }

紧接着看一个具体的递归计算：

  1. unsigned int fibo(unsigned int n)
  2. {
  3.     // 返回部分
  4.     if (n == 0)
  5.         return 0;
  6.     if (n == 1) {
  7.         return 1;
  8.     }
  10.     // 递归部分
  11.     return fibo(n - 1) + fibo(n - 2);
  12. }

这就是斐波那契数列，这个算法能很好的解决斐波那契问题，这也是递归优雅充满魅力的地方。

从本质上来说递归就是「分而治之」概念的一个应用。以递归计算斐波纳切数列来举例，要计算斐波纳切数列的第n项该怎么办？通过数列的定义我们知道第n项的值等于第n-1项加上第n-2项，所以我们可以把计算第n项这个问题分解成计算n-1项和n-2项两个子问题。我们知道计算n-1和n-2项要比计算n项更容易点（因为n-1和n-2都比n要来得小）。那么n-1项由如何计算呢？根据定义n-1项等于（n-1）- 1项和（n-1）-2项的值，好了，我们在这里碰到了递归，好，我们先就此打住。因为n在一直减少，最终会减到1，再减到0，而第0项和第1项的值我们不用计算就知道的，这就是递归终结的时候了。

通用概括一下，在面对递归的问题时，我们可以使用分而治之的概念去帮助理解。步骤如下：

  1. 把问题分解成更容易解决的子问题集合，比如可以把计算斐波那契数列的第n项问题分解转换成计算第n-1项加上第n-2项这两个子问题
  2. 假设我们有一个函数可以应用在所有的子问题上，比如计算斐波那契数列的fibo函数
  3. 基于步骤2的函数，实现如何把子问题的解拼成最终问题的解，这就是递归部分，在计算斐波那契数列的例子里就是fibo(n-1) + fibo(n-2)部分
  4. 递归部分确定了，然后再考虑子问题最终简化到到最底层时该返回什么值。
  5. 上面4步都做好了之后，剩下的就只是毫无条件的相信计算机了……

实践

根据上面的步骤我们来尝试一下解决下面这个很常见的面试题目：「实现一个函数翻转给定的字符串」。假设我们要翻转的字符串是「abcdef」，那么翻转之后的结果应该是「fedcba」。毫无疑问这个字符串我们是没办法一下子就翻转过来的，那么「分而治之」吧。我们不能把多个字符一下子就完全翻转过来，但是假如字符串里的字符只有一个呢？我们翻转起来最方便了，因为什么都不用做。好了，我们可以把「abcdef」分解成「a」和「bcdef」两个子字符串。「bcdef」比「abcdef」短一个字符，理论上也稍微容易点。假设我们有这样的函数能接受一个字符串，然后像变戏法一样就能返回一个翻转后的字符串，如下

  1. string revertString(const string& str)
  2. {
  3.     // 戏法
  4. }

那么有了这个函数之后，我们怎么应用这个函数把「a」和「bcdef」组合成最后的结果呢？很简单我们只要把「a」加到「bcdef」的翻转字符串后面去就可以了，如下：

  1. string revertString(const string& str)
  2. {
  3.     // str = 'abcdef'
  4.     // str[0] = 'a'
  5.     // str.substr(1) = 'bcdef'
  6.     return revertString(str.substr(1)) + str[0];
  7. }

当然现在这个函数还不能直接交给计算机去执行，因为我们传给revertString的参数字符串在不断的缩短，当缩短到一个字符或者一个字符也没有时，我们就没办法再继续缩短了，我们要把这些情况也处理掉才行：

  1. string revertString(const string& str)
  2. {
  3.     if (str.length() <= 1) {
  4.         return str;
  5.     }
  6.     // str = 'abcdef'
  7.     // str[0] = 'a'
  8.     // str.substr(1) = 'bcdef'
  9.     return revertString(str.substr(1)) + str[0];
  10. }

这样的递归就可以交给计算机执行了。递归可以解决另一个常见的面试问题：如何判断一个字符串是否是回文。友情提示，可以把问题分解成判断头尾两个字符和除了头尾之外的子字符串都是否符合回文条件。

递归虽然在代码组织上是优雅的，但是在时间和空间复杂度上往往不是最优的。