函数递归

一. 递归是什么1.1 递归的思想1.2 递归的限制条件 二. 递归举例2.1 求n的阶乘2.2 按顺序打印一个整数的每一位 三. 递归与迭代3.1 求第n个斐波那契数

一. 递归是什么

递归是学习C语言很重要的一个知识，递归就是函数自己调用自己，是一种解决问题的方法，下面就使用一个简单的代码帮助大家理解：下面展示一些 内联代码片。

#include <stdio.h>int main(){ printf("hehe\n");main() //出现了main函数自己调用自己return 0；

上图展示的代码就是一个简单的调用函数的例子，不断的调用main函数也就是要不断输出hehe，形成了一个循环，这就是一个简单的函数递归。

1.1 递归的思想

把一个大型问题转换成一个与原问题相似但是规模较小的子问题来解决，直到到子问题不能再被拆分，递归就结束了。递归中的递就是递推的意思，归就是回归的意思，下面会有详细的解释。

1.2 递归的限制条件

递归在书写的时候，有两个必要条件：

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

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

二. 递归举例

2.1 求n的阶乘

为了让大家更好理解递归是怎么回事，我们可以举几个例子，下面为大家展示第一个例子求n的阶乘的代码： 内联代码片。

int Fact(int n){ if (n == 0)return 1;else if (n > 0)return n * Fact(n - 1);//相当于是多次调用这个函数，形成一个循环，不断地累乘}int main(){ int n = 0;scanf("%d", &n);int r = Fact(n);printf("%d", r);return 0;}

上述代码就给大家演示了一遍比较基本的函数递归，我们可以看到如果n大于0的话，就会返回n*Fact(n-1)，所以就相当于不断的调用Fact函数，如果大家还是不太理解，下面我们用一张图帮助大家进一步理解：

2.2 按顺序打印一个整数的每一位

这是为大家展示的第二个例子，按顺序打印一个整数的每一位。首先我们看到这个题目，我们不难想到用%的方法，假如现在给一个数字1234，要如何打印出1 2 3 4 这四个数字呢？首先就是很容易想到1234%10=4，这时候我们就得到了4，然后1234/10=123(默认取整),然后再用123%10=3，这时候我们就得到了3…按照这个思路我们的代码就能实现，后面我还会再加上图片解释，方便大家进一步理解： 内联代码片。

void get(int n){ if (n > 9){ get(n / 10);}printf("%d ", n % 10);}int main(){ int n = 0;scanf("%d", &n);get(n);return 0;}

三. 递归与迭代

(1)递归是⼀种很好的编程技巧，但是和很多技巧⼀样，也是可能被误⽤的，就像举例1⼀样，看到推导的公式，很容易就被写成递归的形式，为大家解释一下，我们的第一个例子求n的阶乘，我们用递归的方法很容易算出来，但是我们可以自己操作一下，如果数值小的话，计算结果是很快出来，但是如果我们的数值偏大，假如我们输入50，那么计算结果就会很慢，原因就是 Fact函数是可以产生正确的结果，但是在递归函数调用的过程中涉及⼀些运行时的开销。

在C语言中每⼀次函数调用，都需要为本次函数调用在内存的栈区，申请⼀块内存空间来保存函数调用期间的各种局部变量的值，这块空间被称为运行时堆栈，或者函数栈帧。函数不返回，函数对应的栈帧空间就⼀直占用，所以如果函数调用中存在递归调用的话，每⼀次递归函数调用都会开辟属于自己的栈帧空间，直到函数递归不再继续，开始回归，才逐层释放栈帧空间。所以如果采用函数递归的方式完成代码，递归层次太深，就会浪费太多的栈帧空间，也可能引起栈溢出（stackoverflow）的问题。

(2)所以如果不想使用递归，就得想其他的办法，通常就是迭代的方式（通常就是循环的方式）比如我们举的第一个例子计算n的阶乘，也是可以产⽣1~n的数字累计乘在⼀起的。

上述代码是能够完成任务，并且效率是比递归的方式更好的。事实上，我们看到的许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更加清晰，但是这些问题的迭代实现往往比递归实现效率更高。但是当⼀个问题非常复杂，难以使用迭代的方式实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销。所以我们不能说是递归更便捷还是迭代更便捷，我们更多的要去思考问题本身。

3.1 求第n个斐波那契数

我们也能举出更加极端的例⼦，就像计算第n个斐波那契数，是不适合使⽤递归求解的，但是斐波那契数 (1 1 2 3 5 8 13…前两个数相加) 的问题通过是使⽤递归的形式描述的，如下：

当我们n输⼊为50的时候，需要很长时间才能算出结果，这个计算所花费的时间，是我们很难接受的，这也说明递归的写法是非常低效的，那是为什么呢？其实递归程序会不断的展开，在展开的过程中，我们很容易就能发现，在递归的过程中会有重复计算，而且递归层次越深，冗余计算就会越多。

就像上面的图片上展示的，计算一个数值，就要将它拆分成另外两个数，以此类推，会循环很多很多次，也造成了巨大的计算量，所以在有些时候我们不妨试试另一种方法，例如迭代的方法，其实循环也算是迭代的一种，下图计算将递归的方法转换成迭代的方式去实现这个代码，效率就要高出很多了。有时候，递归虽好，但是也会引⼊⼀些问题，所以我们⼀定不要迷恋递归，适可而止就好。

以上就是关于递归的一些初级的理解，在后期我也会为大家继续写更多关于递归的知识，以及一些深入的了解。