递归、递归的常见例子

作者: 纸简书生 | 来源:发表于2017-12-09 15:21 被阅读332次

算法是程序设计的灵魂。为了保持大脑不生锈，一般一两天就刷一刷算法题。这里简单总结下递归、及递归的常见问题。也当是小白教程吧！

在开始讲递归之前，先了解下什么是函数调用栈、以及如何对递归最简单的理解

函数调用、理解递归

对于程序，编译器会对其分配一段内存，在逻辑上可以分为代码段，数据段，堆，栈。

代码段：保存程序文本，指令指针EIP就是指向代码段，可读可执行不可写
数据段：保存初始化的全局变量和静态变量，可读可写不可执行
BSS：未初始化的全局变量和静态变量
堆(Heap)：动态分配内存，向地址增大的方向增长，可读可写可执行
栈(Stack)：存放局部变量，函数参数，当前状态，函数调用信息等，向地址减小的方向增长，非常非常重要，可读可写可执行

来一张图：
[图片上传失败...(image-d902e7-1512804060985)]

上面这些对理解调用栈有什么用呢。其实想要彻底弄明白，还需要懂汇编才行。这里我们只需要知道栈会存放局部变量，函数参数，当前状态，函数调用信息对后面的理解就够了。

下面通过一个例子来理解递归调用的执行过程（Xcode）

void up_and_down(int n)
{
    printf("before: Level %d:n location %p\n",n,&n); /* 1 */
    if(n<4)
        up_and_down(n+1);
    printf("after: Level %d:n location %p\n",n,&n); /* 2 */
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        up_and_down(1);
    }
    return 0;
}

执行结果

before: Level 1:n location 0x7fff5fbff75c
before: Level 2:n location 0x7fff5fbff73c
before: Level 3:n location 0x7fff5fbff71c
before: Level 4:n location 0x7fff5fbff6fc
after: Level 4:n location 0x7fff5fbff6fc
after: Level 3:n location 0x7fff5fbff71c
after: Level 2:n location 0x7fff5fbff73c
after: Level 1:n location 0x7fff5fbff75c
Program ended with exit code: 0

分析过程：　
首先， main() 使用参数 1 调用了函数 up_and_down() ，于是 up_and_down() 中形式参数 n 的值是 1, 故打印语句 #1 输出了 Level1 。然后，由于 n 的数值小于 4 ，所以 up_and_down() （第 1 级）使用参数 n+1 即数值 2 调用了 up_and_down()( 第 2 级 ). 使得 n 在第 2级调用中被赋值 2, 打印语句 #1 输出的是 Level2 。与之类似，下面的两次调用分别打印出 Level3 和 Level4 。

当开始执行第 4 级调用时， n 的值是 4 ，因此 if 语句的条件不满足。这时候不再继续调用 up_and_down() 函数。第 4 级调用接着执行打印语句 /* 2 */，即输出 Level4 ，因为 n 的值是 4 。现在函数需要执行 return 语句，此时第 4 级调用结束，把控制权返回给该函数的调用函数，也就是第 3 级调用函数。第 3 级调用函数中前一个执行过的语句是在 if 语句中进行第 4 级调用。因此，它继续执行其后继代码，即执行打印语句 /* 2 */，这将会输出 Level3 ．当第 3 级调用结束后，第 2 级调用函数开始继续执行，即输出Level2 ．依次类推.

注意，每一级的递归都使用它自己的私有的变量 n ．可以查看地址的值来证明。也就是栈保存了调用的参数。

如果还没看懂，没关系，我再用一种最为简单的方式在解释一下。完全可以简单就是把递归函数一层一层展开。比如上面的例子，如果展开就可以写成下面这样

void up_and_down_simple(int n)
{
    printf("before: Level %d:n location %p\n",n,&n); /* 1 */
    if(n<4)
        up_and_down1(n+1);
    printf("after: Level %d:n location %p\n",n,&n); /* 2 */
}
void up_and_down1(int n)
{
    printf("before: Level %d:n location %p\n",n,&n); /* 1 */
    if(n<4)
        up_and_down2(n+1);
    printf("after: Level %d:n location %p\n",n,&n); /* 2 */
}

void up_and_down2(int n)
{
    printf("before: Level %d:n location %p\n",n,&n); /* 1 */
    if(n<4)
        up_and_down3(n+1);
    printf("after: Level %d:n location %p\n",n,&n); /* 2 */
}
void up_and_down3(int n)
{
    printf("before: Level %d:n location %p\n",n,&n); /* 1 */
    if(n<4)
        up_and_down4(n+1);
    printf("after: Level %d:n location %p\n",n,&n); /* 2 */
}
void up_and_down4(int n)
{
    printf("before: Level %d:n location %p\n",n,&n); /* 1 */
    if(n<4)
        up_and_down(n+1);
    printf("after: Level %d:n location %p\n",n,&n); /* 2 */
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
//        up_and_down(1);
        up_and_down_simple(1);
    }
    return 0;
}

打印的结果：

before: Level 1:n location 0x7fff5fbff75c
before: Level 2:n location 0x7fff5fbff73c
before: Level 3:n location 0x7fff5fbff71c
before: Level 4:n location 0x7fff5fbff6fc
after: Level 4:n location 0x7fff5fbff6fc
after: Level 3:n location 0x7fff5fbff71c
after: Level 2:n location 0x7fff5fbff73c
after: Level 1:n location 0x7fff5fbff75c
Program ended with exit code: 0

这样一对比二者的结果是一样的所以说，如果你对递归还是很难理解，就去用展开的思路理解吧。

总结一下

每一次函数调用都会有一次返回．当程序流执行到某一级递归的结尾处时，它会转移到前一级递归继续执行．
递归函数中，位于递归调用前的语句和各级被调函数具有相同的顺序．如打印语句 #1 位于递归调用语句前，它按照递归调用的顺序被执行了 4 次；位于递归调用语句后的语句的执行顺序和各个被调用函数的顺序相反．
每一级的函数调用都有自己的私有变量．
递归函数中必须包含可以终止递归调用的语句．

常见递归问题

有了上面的基础，现在开始来刷刷几道简单的题：

阶乘n！

按照递归的套路两个： 1. 递归公式：有反复执行的过程（调用自身） 2. 退出条件：有跳出反复执行过程的条件（递归出口）

递归公式 n! = n * (n-1) * (n-2) * ...* 1(n>0)
退出条件 n == 0

int recursive(int n) {
    if (0 == n) {
        return (1);
    }
    else {
        return n * recursive(n - 1);
    }
}

斐波那契数列

斐波纳契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……

递归公式 Fib(n) = Fib(n-1) + Fib(n-2);
退出条件 n == 0 ,n == 1

int Fib(int n) {
    if (0 == n) {
        return 1;
    }
    if (1 == n) {
        return 1;
    }
    
    return Fib(n -1) + Fib(n - 2);
}

全排列

从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

如1,2,3三个元素的全排列为：

  1,2,3
  1,3,2
  2,1,3
  2,3,1
  3,1,2
  3,2,1

这种问题递归公式和退出条件并不是那么明显，需要深入分析。如何去分析呢。一般思路就是总结归纳，先用最简单的例子找到规律，再提炼成公式。

把123的全排列可以看出三组，分别是1xx，2xx, 3xx。可以想成一个数列的全排列的公式：n个元素的全排列=（一个元素作为前缀）+（其余n-1个元素的全排列）；

退出条件：如果只有一个元素的全排列，则说明已经排完，则输出数组；

不断换排头通过for循环就可以实现。然后就是前缀需要交换。先把基本的写好

交换函数：

void Swap(char str[], int a, int b) {
    char temp = str[a];
    str[a] = str[b];
    str[b] = temp;
}

主函数

//全排列
int sum = 0;
void Perm(char str[], int begin, int end) {
    if (begin == end)
    {
        for (int i = 0; i <= end; i++)
        {
            cout << str[i];
        }
        cout << endl;
        sum++;
        return;
    }
    else
    {
        for (int j = begin; j <= end; j++)
        {
            printf("\n swap begin:%d j:%d \n", begin, j);
            Swap(str, begin, j);//交换是第几个
            Perm(str, begin + 1, end);
            Swap(str, j, begin);//归位
        }
    }
}

为了看清整个交换流程，加了个日志

4
abcd

 swap begin:0 j:0 

 swap begin:1 j:1 

 swap begin:2 j:2 
abcd

 swap begin:2 j:3 
abdc

 swap begin:1 j:2 

 swap begin:2 j:2 
acbd

 swap begin:2 j:3 
acdb

 swap begin:1 j:3 

 swap begin:2 j:2 
adcb

 swap begin:2 j:3 
adbc

 swap begin:0 j:1 

 swap begin:1 j:1 

 swap begin:2 j:2 
bacd

 swap begin:2 j:3 
badc

 swap begin:1 j:2 

 swap begin:2 j:2 
bcad

 swap begin:2 j:3 
bcda

 swap begin:1 j:3 

 swap begin:2 j:2 
bdca

 swap begin:2 j:3 
bdac

 swap begin:0 j:2 

 swap begin:1 j:1 

 swap begin:2 j:2 
cbad

 swap begin:2 j:3 
cbda

 swap begin:1 j:2 

 swap begin:2 j:2 
cabd

 swap begin:2 j:3 
cadb

 swap begin:1 j:3 

 swap begin:2 j:2 
cdab

 swap begin:2 j:3 
cdba

 swap begin:0 j:3 

 swap begin:1 j:1 

 swap begin:2 j:2 
dbca

 swap begin:2 j:3 
dbac

 swap begin:1 j:2 

 swap begin:2 j:2 
dcba

 swap begin:2 j:3 
dcab

 swap begin:1 j:3 

 swap begin:2 j:2 
dacb

 swap begin:2 j:3 
dabc
24
Program ended with exit code: 0

根据日志结合代码来分析就很容易理解了。

河内塔问题

n个盘子和3根柱子：A(源)、B(备用)、C(目的)，盘子的大小不同且中间有一孔，可以将盘子“串”在柱子上，每个盘子只能放在比它大的盘子上面。起初，所有盘子在A柱上，问题是将盘子一个一个地从A柱子移动到C柱子。移动过程中，可以使用B柱，但盘子也只能放在比它大的盘子上面。

从上面的分析得出：
该问题可以分解成以下子问题：
第一步：将n-1个盘子从A柱移动至B柱（借助C柱为过渡柱）
第二步：将A柱底下最大的盘子移动至C柱
第三步：将B柱的n-1个盘子移至C柱（借助A柱为过渡柱）

int i;    //记录步数  
//i表示进行到的步数,将编号为n的盘子由from柱移动到to柱(目标柱)  
void move(int n, char from, char to) {  
    printf("第%d步:将%d号盘子%c---->%c\n", i++, n, from, to);  
}  
  
//汉诺塔递归函数  
//n表示要将多少个"圆盘"从起始柱子移动至目标柱子  
//start_pos表示起始柱子,tran_pos表示过渡柱子,end_pos表示目标柱子  
void Hanio(int n, char start_pos, char tran_pos, char end_pos){  
    if(n == 1) {    //很明显,当n==1的时候,我们只需要直接将圆盘从起始柱子移至目标柱子即可.  
        move(n,start_pos, end_pos);  
    }  
    else {  
        Hanio(n-1, start_pos, end_pos, tran_pos);   //递归处理,一开始的时候,先将n-1个盘子移至过渡柱上  
        move(n, start_pos, end_pos);                //然后再将底下的大盘子直接移至目标柱子即可  
        Hanio(n-1, tran_pos, start_pos, end_pos);    //然后重复以上步骤,递归处理放在过渡柱上的n-1个盘子  此时借助原来的起始柱作为过渡柱(因为起始柱已经空了)  
    }  
}

这个思考起来有点麻烦，所以注释写得很多。

除了上面列举的几个例子，还有比较常见的，二分查找，快排也用到了递归的思想。先这样吧。脑子还是得多用才能更加灵活。

扩展阅读

深入理解递归函数的调用过程
 函数调用--函数栈
 算法设计-全排列递归
 算法设计-全排列递归

递归、递归的常见例子

函数调用、理解递归

常见递归问题

阶乘n！

斐波那契数列

全排列

河内塔问题

更多

扩展阅读

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读