C语言基础-递归

基本概念

C 语言允许函数调用它自己，这种调用的过程称为递归

基本原理

栈：一种数据结构，其特点为先进后出

C 语言在执行代码时会从 main()开始依次将调用的函数放入栈中
放完后便将栈中的方法，从栈顶一个个取出并执行

如图( 计算 3! )：

解释：

1. 开始执行，先将main( )函数放入栈底并执行
2. 遇到了fun(3)后把 mian( )函数暂时放在栈中，去调用fun(3)函数
3. 执行fun(3)时又发现调用了fun(2)，又把fun(2)放入栈中去掉fun(1)
4. fun(1)时发现没有调用了( 此时fun(1)在栈顶 )，便开始返回，把返回值给了fun(2)，fun(2)也继续下面的语句，返回给了fun(3)
5. 最后fun(3)返回给main( )，main( )继续执行下面的语句

由此可以看成递归的形成至少需要两个条件：

1. 变化的参数
2. 递归终止条件

栈溢出：内存空间是有限的，分配给 C 程序的栈空间也是有限的，如果递归没有结束条件的话就会导致无限的调用，形成栈溢出

---

尾递归

最简单的递归形式就是把递归调用置于函数的末尾，即正好在 return 语句之前。这种形式的递归被称为 尾递归 (如上图所示)，它相当于循环。

如果效果和循环差不多时最好使用循环

---

递归的优缺点

递归的语法易被人理解，但空间成本消耗太大。所以在使用递归时要特别注意，尤其是效率优先的程序

注：main( )函数可以调用自己，且两函数间不可以相互调用

---

递归算法实战-汉诺塔问题

问题叙述

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。

思路

我们倒着的开始，假如要移动 64 个

1. 我们要把上面的 63 个移动到 B
2. 把第 64 个移动到 C
3. 把 B 上的 63 个移动到 C

那么就会产生问题了：怎么移动那 63 个呢
和上面的思路一样

1. 我们要把上面的 62 个移动到 B
2. 把第 63 个移动到 C
3. 把 B 上的 62 个移动到 C

直到问题变为：怎么移动上面的那 1 个呢，这时我们就会了，移动了 1 个后，我们就会移动 2 个，移动 2 个后，我们就会第 3 个，依次下去，就能把 64 个都移动完了

所以整个过程是

1. 我们要把上面的n-1个移动到 B
2. 把第n个移动到 C
3. 把 B 上的n-1个移动到 C

其中移动 n-1 个盘子的操作是递归操作
1，3 步分别用了递归

下面是 java 语言代码实现部分( 用 C 表达出来的效果不好啊，还是 java 的看着舒服 ，其实基本都是一样的):

class Solution {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        move(A.size(),A,B,C);
    }
    //从这开始看
    //盘子用数字代替，n代表需要移动的盘子数，List是盘子的集合
    public void move(int n,List<Integer> A, List<Integer> B, List<Integer> C){
        //当需要移动的盘子数只有1个时，此时这个盘子就是最下面的，其它的都移动到B上(第一步)或者A(第三步)上了了
        // 把A的盘子直接移动到C就行了
        if(n == 1){
            C.add(A.remove(A.size()-1)); //注意这里是最下面的盘子数最大
            return;
        }
        //没到最上面时，则一直重复123步骤
        move(n-1,A,C,B); //对应第一步
        C.add(A.remove(A.size()-1));  //对应第二步
        move(n-1,B,A,C);  //对应第三步
    }
}

---

递归总结

要运用递归的地方都有以下的共同点

1. 拥有大量重复的步骤，或者说可将复杂的步骤转换为计算大但容易理解的重复步骤
2. 拥有当达到某种条件时，可返回一个确定值，即遇见某种情况时可向前推导

这样便可以将代表条件的变量设为函数参数，把步骤设为函数具体代码

---

推荐阅读

知乎-如何理解汉诺塔的递推
leetcode-递推(有点难度)

Donate