【C语言】函数递归

1、递归的概念

        其实我们在前面的学习中已经使用过函数的递归了。那么什么是递归呢

        递归是一种解决问题的方法，就是函数自己调用自己，例如下面的函数。

         上面就是一个简单的函数递归，在main函数内调用自己。

2、递归的使用思路和限制条件

        1、使用思路

              在将一个大型问题一层一层转化为一个与原问题类似，但是规模较小的子问题来解，，                  直到这个问题没办法再拆分，递归就结束了，所以递归是把大事化小的一个过程。

         2、限制条件

              递归在使用的时候有下面两个限制条件：

              1、递归存在一个条件，当程序运行到满足这个条件后，，递归就结束，如果没有这个条                     件可能会陷入死递归

              2、每次递归后，程序会越来越接近限制条件。

3、递归实例

        例1：求n的阶乘

        题目描述：一个正整数的阶乘：是他和比他小的数的阶乘的乘积，而且0的阶乘为1。

                          我们可以发现n！=n*（n-1）！

                          例如：5！=5*4！=5*4*3！=5*4*3*2！=5*4*3*2*1!=5*4*3*2*1

        n的递归公式如下：

      运行结果：

    4、递归与迭代

             递归是一种很好的编程技巧，但是和很多技巧一样，也是有可能被误用的，就如上面的例               子一样，看到推导的公式，很容易就写成递归的形式

             C语言在每次函数调用，都要为本次函数调用在内存中的栈区，申请一块空间来保存函数               调用期间的各种局部变量的值，这块空间被称为运行时的堆栈，或者函数堆帧。

             函数不返回，函数对应的栈帧空间就一直占用，所以如果函数调用中存在递归调用的话，               每一次递归函数都会开辟属于自己的空间，直到函数递归不再继续，开始回归，才逐层释               放栈帧空间

             所以如果使用函数递归的方式解决问题，当问题规模大起来，要递归的次数多起来后，会               造成栈帧空间被大量浪费，还有可能会引起栈溢出的问题。

             如果不想使用递归的方式就得想想其他的方法，通常就会使用迭代的方法（一般都是使用               循环）

             例如：计算n的阶乘，

                  上面定义的函数也可以完成题目的要求，而且效率是要比递归的方法要高的。我们可                      以去求一个大一点的数的阶乘，就可以发现递归和迭代的效率差距了。

                  事实上，我们看到许多问题是以递归的方式进行解释的，这只是因为它比非递归的形                      式更加清晰，代码更加容易写，但是这些问题使用迭代的方式运行的效率是会更高的

                  当一个问题非常复杂，难以使用迭代的方式实现的时候，此时递归的方式实现的简洁                      性可以补偿它所带来的运行时的开销

5、递归和迭代的实例

         例：求第n个斐波那契数列

               计算第n个斐波那契数，是不适合使⽤递归求解的，但是斐波那契 数的问题通过是使⽤                   递归的形式描述的。如下：

                看到这个公式我们会很容易想到使用递归方式。如下所示：

                当我们要求第50个的时候就需要很长时间了，如下图所示：

                可以看到程序要一直递归下去。效率会非常低，所以我们使用非递归的方法实现