加深理解函数递归

一、递归是什么？

       1.1 定义

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

       递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。

       1.2 递归的思想

       把⼀个⼤型复杂问题层层转化为⼀个与原问题相似，但规模较⼩的⼦问题来求解；直到⼦问题不能再 被拆分，递归就结束了。所以递归的思考⽅式就是把⼤事化⼩的过程。 递归中的递就是递推的意思，归就是回归的意思，递归就是用空间来换时间。接下来慢慢来体会。

       1.3 优缺点

       优点：

1. 简洁清晰：递归能够简洁地表达某些算法和问题的解决方案，使代码更易于理解和维护。
2. 问题分解：递归能够将复杂问题分解为简单的子问题，从而降低问题的复杂度。
3. 适用性广泛：递归在数学、计算机科学等领域有着广泛的应用，能够解决许多问题。

       缺点：

1. 性能问题：递归调用会增加函数调用的开销，可能导致性能下降。递归深度过深时，还可能导致栈溢出。
2. 内存消耗：每次递归调用都需要在内存中保存函数调用的上下文，可能占用大量内存空间。
3. 难以调试：递归调用过程比较隐晦，容易出现逻辑错误，增加调试的难度。

       1.4 限制条件

       递归存在限制条件，当满⾜这个限制条件的时候，递归便不再继续。

       每次递归调⽤之后越来越接近这个限制条件。

二、初识函数递归

       2.1 何为递归

       观察以下代码，并猜测运行结果

1. #include <stdio.h>      
2. int main()
3. {
4.  printf("hello\n");
5.  main();
6.  return 0;
7. }

       这一段代码，便是函数递归的简单实现。它的实现思想通俗来讲就是：我调我自己。

       以上代码的运行结果想必大家已经看出来了即——死循环。

       为什么是死循环？

       因为，没有限制条件。没有限制的自由，便不是自由；没有限制的递归，便不是递归。所以，我们在使用时一定要加限制条件。

       2.2 用递归 实现打印数字每一位

       说了那么多，来一个小实践吧。想到打印每一个数的每一位，大家会不约而同的想到使用%与/来进行操作。那，咱们这一次来使用递归实现吧！

       接受一个整型值（无符号），按照顺序打印它的每一位。

       例如：输入：1234，输出 1234.

解题思路：这种输入输出数字的题，我们一定要想到取模和取余的方法,并且要有限制条件，每次函数递归后，都会越来越接近这个值。

       所以先函数递推1234%10=4,123%10=3,12%10=2,1%10=1，给定限制条件n>9,直到n=1，打印出最后值1，最后函数回归打印出1234。

        代码实现：

1. #include <stdio.h>      
2. void Printf(int a)
3. {
4.  if (a > 9)
5.  {
6.     Printf(a / 10);
7.  }
8.  printf("%d", a%10);
9. }
10. int main()
11. {
12.   int a = 1234;
13.   Printf(a);
14.   return 0;
15. }

       好了，正序打印我们已经实现了，感兴趣的话可以试试逆序打印。

三、深入理解函数递归

       我们用两道例题来简单巩固一下吧。

       3.1 运用递归思想求第n个斐波那契数

               斐波那契数列（Fibonacci sequence），又称黄金分割数列 ，因数学家莱昂纳多· 斐波那契 （Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称“兔子数列”，其数值为：1、1、2、3、5、8、13、21、34……在数学上，这一数列以如下 递推 的方法定z义：F(0)=1，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）。

      分析：根据 F(0)=1，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）公式我们自然可以想到运用函数递归的方法来完成此题目。即：斐波那系数是前两项加起来等于后一项，所以我们可以以n<=2为限制条件，当n=1或2时，返回1，然后到n=3项时就是n=1项和n=2项之和，然后依次往后推，即Fib(n)就是Fib(n-1)和Fib(n-2)之和。

       代码实现：

1. #include <stdio.h>      
2. int Fib(int n)
3. {
4.  if (n <= 2)
5.    return 1;
6.  else
7.    return Fib(n - 1) + Fib(n - 2);   
8. }
9. int main()
10. {
11.   int n = 0;
12.   scanf("%d", &n);
13.   int ret = Fib(n);
14.   printf("%ld", ret);
15.   return 0;
16. }

        3.2  经典问题之《汉诺塔问题》

         问题描述：  总共有三个柱子，在一根柱子上，从下往上按照大小顺序摞着n片圆盘。我们需要按大小顺序重新摆放在另一根柱子上。并且规定，在移动过程，小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

       分析：

       代码实现：

1. #include <stdio.h>      
2. void Move(char src, char dest)
3. {
4.  printf("盘子从%c柱子->%c柱子\n", src, dest);
5. }
6. void Plate_Move(int n,char A, char B,char C)
7. {
8.  if (n == 1)
9.  {
10.     Move(A, C);//这里即递归停下来的地方，把最底下一层的盘子（n），移动到C柱上
11.   }
12.   else
13.   {
14.     Plate_Move(n - 1, A, B, C);//当不只一个圆盘时，我们先将上面 （n -1）个圆盘 借助 C柱子  从 A 柱子移动到 B 柱子
15.     Move(A, C);//A柱剩余一个圆盘，将剩下的一个圆盘从 A 移动到 C
16.     Plate_Move(n - 1, B, A, C);//以A柱为中转站，把B柱上的圆盘放在C上。
17.   }
18. }
19. int main()
20. {
21.   int n = 0;
22.   scanf("%d", &n);
23.   Plate_Move(n, 'A', 'B', 'C');
24.   return 0;
25. }

完！