本章内容：

1.函数递归

1）什么是递归？

        递归就是一句话的概念，函数自己调用自己，我们也可以让opencode来回答一下：

        我们来写一个最简单的递归程序：

        这里举个例子，就是让道友们看一下递归的基本形式，这个代码最终会陷入死递归，导致栈溢出了

2）递归的思想及限制条件

• 递归的思想

        其实就是把一个大型的复杂问题层层转化为一个与原问题相似，但规模较小的子问题来求解，直到子问题不能再被拆分，递归就结束了，所以递归的思想就是把大事化小的过程，递归中的递就是递推的意思，归就是回归的意思，有没有这样一种感觉，看完概念字面意思可能理解了，但是在程序中是怎样的反而又不知道了，这个概念性的东西有时候确实不好理解哈，没关系，下面我们再来慢慢来体会哈。

• 递归的限制条件

        我们写代码的时候，使用到递归是由两个必要条件的：

1. 递归存在限制条件，当满足这个条件的时候，递归不再继续
2. 每次递归调用之后越来越接近这个限制条件

        就比如上面那个简单的递归程序，由于main函数不断地调用自己，没有限制条件，就会导致栈溢出了，通过下面的举例我们再来好好感受递归的两个限制条件

3）递归的举例

• 举例1：递归求n的阶乘（不考虑溢出）

        先来分析一下代码，比如：

   5！= 5*4*3*2*1

   4！= 4*3*2*1

   所以5！= 5*4！

   那么就可以得出一个公式：n！=n*(n-1)！

        从这个公式也不难看出，如何把一个较大的问题，转化为一个与原问题相似，但规模较小的问题来求解，我们要求5！可以先求出4！，要求4！可以先求3！，这样一直递推下去，那么什么时候结束呢，就是n==0的时候，0！是1对吧，这样我们就可以得到n！的递推公式：

        下面就代码实现一下：

        代码写出来，其实还是有点不好理解的，主要原因就是递归的程序很简单，复杂的是它的运行逻辑，我们只有看到递归底层的运行逻辑，才能理解这个代码，比如我们输入的n是5，也就是求5!，我画图来带大家分析一下：

• 举例2：顺序打印一个正整数的每一位

比如：输入1234       输出：1 2 3 4

           输入520         输出：5 2 0

        简单分析一下这个问题，如何得到这个正整数的每一位呢，如果n是一位数，n的每一位就是n自己，那么我们也就找到了递推的限制条件，其次，一个数字的最低位其实是最容易得到的，通过%10就能得到，比如1234%10就得到了4，然后1234/10就可以得到123，相当于把4给去除了，这样我们也就可以分析出这个递归的公式，如下：

Print(n)  //打印n的每一位，假设n是1234

Print(1234)  //打印1234的每一位

那么Print(1234)就可以写成Print(123) + printf("%d",4);

                        Print(123) = Print(12) + printf("%d",3);

                        Print(12) = Print(1) + printf("%d",2);

                        Print(1) = printf("%d",1);

那么这个递归函数的公式就是：Print(n) = Print(n/10) + printf("%d",n%10);

        第一种写法，比较好理解

        第二种写法代码更简短一点，可能不太好理解，但底层运行逻辑是一样的

        那我再来画图给各位道友推演一下它底层的运行逻辑，就会更好理解了：

4）递归与迭代（循环）

        递归是一种很巧妙的编程技巧，但是它也是一把双刃剑，用的好，就能很大程度的提高代码的运行效率和代码的简洁性，但是就是不好理解代码，同时递归也有个很致命的问题就是递归的层次不能太深，就比如上面求n的阶乘，递归每递推一次，就会进行一次函数调用，而每一次的函数调用都需要申请一块内存空间来保存函数调用期间的各种局部变量的值，如果函数不返回，函数调用对应的内存空间就会一直被占用，也就是递归层次太深的话，就会浪费太多的内存空间，就很有可能导致栈溢出。

        那么求n！若不想用递归，就得使用其他的方法，通常就是迭代（循环）的方式，代码如下：

        这个代码也可以完成求n！并且效率是要比递归高的，但是很多问题我们通常会使用递归的形式，因为它比非递归的形式更加清晰，但是这些问题用迭代实现效率往往比递归高，所以说我们使用递归是需要判断什么情况下使用最为合适，比如说当一个问题非常复杂，难以使用迭代的方式去实现，此时递归的简洁性就可以弥补它所带来的运行时内存的开销，还有就是这个问题非常简单，递归几句代码就能解决，而且效率比迭代方式高或者差不多的情况，也可以优先使用递归的方式

• 求第n个斐波那契数

        什么是斐波那契数，我们可以让opencode来回答一下：

        观察发现，斐波那契数的特点是前两项之和等于第三项，但是我们通常不去求第0个斐波那契数，都是从第一个开始的，发现第一个和第二个斐波那契数都是1，这里其实也就发现了递归的限制条件，也就是n<=2的时候，返回1就好，那么通过它的特点，我们也可以推出递归的公式，就是若求第10个斐波那契数，只需要求出第8个和第9个斐波那契数，公式如下：

Fib(n) = Fib(n-1) + Fib(n-2);

        求第10个斐波那契数：发现使用递归写代码确实简短的多，而且用迭代写代码其实是不太好写的

        但是我们让这个递归层次深一点，比如求第50个斐波那契数：

        发现它突然间就求不出来了，其实它是一直在不停的计算的，但是里面是有大量的重复计算的，就比如第三个斐波那契数，我们看它计算了多少次：

        虽然递归写代码确实很快，但是它也是会有问题的，这个时候就需要用迭代的方式来解决这个问题了：

        但是我自己试了一下，定义为long long类型，发现第50个斐波那契数的值还是要大于long long类型的最大值，只能说明这个值非常的大，那我们也就不用去考虑这个问题了，但是代码是没有问题的，而且运行效率也是远高于递归的

        所以有时候，递归虽然好，但是不要过度迷恋递归，适可而止就好，因为它毕竟是一把双刃剑，使用的好，就能达到很好的效果，使用的不好，反而会导致一些问题的产生。

2.总结

        递归的设计还是很巧妙的，希望各位道友看了我的文章，可以对递归有一个新的认识和启发，能够真切的帮助到各位，也希望道友们可以学好递归，巧妙地使用起来，不仅提升你编程能力的同时，也可以很好的提高你的逻辑思维能力，因为有些场景递归确实不太好推出它的递归公式，但是一但推出公式，写起来就非常的方便快捷，那本篇文章就先分享到在这里哈，我们下篇文章再见！！！