C语言(6)----函数的递归思想

1.递归是什么？

递归需要拆开来理解这个词的意思

递：递推的意思

归：回归的意思

那么连在一起就是先递推再回归，是具有一个先后的逻辑关系的。

递归就是函数自己调用自己的一个过程。

就是函数把自己递推出去再回归回来的一个过程。

很简单的一个函数自我调用的过程，它就是递归。

当我们按下执行键的时候，屏幕上就会一直打印hehe直到栈溢出stack overflow。

这个现象说明了两个点。

A：当一个函数不断的调用自己的过程也就是递归，这在这段代码中很好的体现了出来。

B：每次当我们调用函数的时候都会向内存的栈区申请一块空间，这块空间被称为运行时堆栈，也就是函数栈帧空间。而反复申请空间的操作称为堆栈。当栈区被堆满之后那么就会溢出，也就是所说的stack overflow。

2.递归的实际运用

阶乘可以很好的体现递归的特点：大事化小，使事情变得简单。

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

那么如果我们需要求得n！，也就需要直到(n - 1）!是什么，那么我们如果需要知道（n - 1）!是什么，也就需要知道（n - 2）!是什么...以此类推下来，如果我们需要求一个阶乘，那么其实只需要知道最后一个阶乘的数值是多少就可以了，然后再从末尾阶乘一步步返回计算直到n！。

我们就可以写一个函数：

这个函数可以清晰看出阶乘递归思想的逻辑。

那么我们用递归思想就可以很容易得出计算阶乘的方式。

从中我们可以看出：递归的思想即相当于把一件复杂的事情一步一步解析直到成为最简单的形式，直到不能再简单。其实这个思想和数学中数列或者求不等式等一系列的题型有相似之处，可以自行对比，比如说高中数学经常会出现类似

这种化简，那么可以看到经过一系列操作把没必要的项全部抵消了，其实用的也是一种递归思想，就是一步一步递推再一步一步回归，最终化繁为简。

那么递归看似十分的方便，只需要用简单几行代码就可以实现一些运算，其实这也是需要付出一定的代价或者说是开销的。

上文我们说到递归的过程中是会占用函数栈帧空间的，那么也就是会占用内存，如果我们运用递归时运算的需求量过大，那么就可能会出现栈溢出的情况。

更有可能会由于太过于庞大的计算导致计算时间过久。因为递归的思想逻辑是很简单的，那么其实也就是很死板的，它只能先递推再回归再递推再回归，那么就会出现冗长的情况。

比如当我们用递归思想来求斐波那契数时，函数是这么写的：

先执行它：

我们任意输入一个数：n

可以发现这个数字较小的时候，编译器是可以应付的；

但当这个数字较大时，编译器的计算速度就会显著变慢，甚至可能出现计算不出来的情况。

这就是因为在斐波那契数列中，越是到后面，数就越大，而递归的思想是将第前一项和第前两项相加得到这一项，那么就很繁琐了：

向下会有呈指数倍增长的分支，计算能不困难吗？

所以说白了，递归思想很简单，但它的使用很死。所以这就是它的缺点。

3.递归和迭代

其实不难看出，递归的思想很像循环，特别是for循环，简直不能太像。

那么当我们难以用递归解决高运算时，应该怎么办呢？这时候我们就要用迭代。

其实迭代就是循环的意思。

在斐波那契数的计算中，如果我们用while循环来代替递归，是可以很快就算出结果的，这是因为它没有经过一层又一层的剖析，而是直接通过迭代计算出结果。至于为什么是个负数，因为这个数实在是太大了，对于int类型是不在范围内的。

总而言之我们可以得出：

当我们需要编写容易简单的代码，进行简单的运算时，我们就用递归；

如果遇到递归难以解决的问题，我们就用迭代。

在实际应用中，我们不能迷恋递归，也不能死板地只用其中一种方法，只有灵活运用，才能使代码的简洁性和实用性更高。