九、函数递归

———————————————————————————————————————————

目录

1、递归是什么？

1.1、递归的思想

1.2、递归的限制条件

2、递归举例

2.1、举例1：求n的阶乘

2.1.1、分析和代码实现

2.2.1分析和代码实现

3、递归与迭代

3.1举例3：求第n个斐波那契数

1、递归是什么？

在C语言中，递归就是函数自己调用自己。

上面算是一个比较容易理解的一个简短的递归程序，但是一个错误的示范。

如果无限递归下去，就会出现这样的错误，栈溢出！！！

每一次函数调用，都要为这个函数调用分配内存空间（是从内存的战区上分配的，如果无限的递归调用函数，就会将栈区空间填满（使用完）），这时就出现了栈溢出的现象。

1.1、递归的思想

递归其实是把一个大型复杂的问题层层转化为一个与原问题相似，但规模较小的问题来求解；直到子问题不能再拆分，递归就结束了。所以递归的思考方式就是发大事化小的过程。

递归中的“递”就是递推的意思，“归”就是回归的意思。

1.2、递归的限制条件

递归在书写时有两个必要条件

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

（2）每次递归调用之后越来越接近这个限制条件。

2、递归举例

2.1、举例1：求n的阶乘

一个正整数的阶乘是所有小于及等于该数的正整数的积，并且0的阶乘为1。

自然数n的阶乘写作n！

题目：计算n的阶乘（不考虑栈溢出），n的阶乘就是1~n的数字累积相乘

2.1.1、分析和代码实现

我们知道n的阶乘公式：n! = n*(n-1)！

举例：

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

4！=4*3*2*1

--------------------

5！= 5*4！

4！= 4*3！

3！= 3*2！

这样的思路就是把一个较大的问题，转换为一个与原问题相似，但规模较小的问题来求解的。

当n==0时，n的阶乘是1，其余的阶乘都是可以通过公式计算的。

n的阶乘递归公式如下：

递归是少量的代码完成了大量复杂的运算

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

题目：输入一个整数m，按照顺序打印整数的每一位

比如：

2.2.1分析和代码实现

这个题目，放在我们面前，首先想到的是，怎么得到这个数的每一位呢？

n如果超过一位数的话，就得拆分每一位。

但是这里有个问题就是得到的数字顺序是倒着的，那既然递归能将正序变为倒序，那一定也可以将倒序改成正序。

画图理解：

3、递归与迭代

递归是一种很好的编程技巧，但很可能被误用，就像举例1一样，很容易被写成递归的形式

Fact函数是可以产生正确的结果，但是在递归函数调用的过程中涉及一些运行时的开销。

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

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

所以如果采用函数递归的方式完成代码，递归层次太深就会浪费太多的栈帧空间，也可能引起栈溢出 ( stack overflow ) 的问题。

所以如果不想使用递归，就得想其他办法，通常就是迭代的方式 ( 循环的方式 )。

比如：计算n的阶乘，也是可以产生1~n的数字累计乘在一起的。 

上述代码是能够完成任务，并且效率是比递归的方式更好的。

3.1举例3：求第n个斐波那契数

如果要计算斐波那契数，是不适合使用递归求解的，但是斐波那契数的问题通过是使用递归的方式描述的，如下：

斐波那契数列：

有很多重复运算。

用递归方式解决问题：

该类问题不适合使用递归的方式解决，所以换一种思路，使用迭代的方式。

代码如下：

有时候，递归虽好，但是也会引入一些问题，所以我们使用递归时，适可而止就好。

拓展学习：

（1）青蛙跳台阶问题

本质：斐波那契数列问题

一次能跳一个台阶或两个台阶，问这只青蛙跳上n个台阶有多少种跳法？

（2）汉诺塔问题

借助于B，将A上的盘子挪到C上

挪的过程中，盘子一定是上小，下大

以上两个问题都可以使用递归很好的解决。