c语言函数递归（图解）_c语言递归图解

一、递归的基础概念

什么是递归

递归是⼀种解决问题的⽅法，在C语⾔中，递归就是函数⾃⼰调⽤⾃⼰。
我举个例子：

上述就是一个简单的递归程序——main()函数中又调用了main()函数，重复调用。只不过上面的递归只是为了演示递归的基本形式，不是为了解决问题，代码最终也会陷入死递归，导致栈溢出（Stack overflow）

1.递归思想

递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接
调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。
递归的递就是递推，归就是回归，下面的例题我会让大家体验递归的过程。

2.递归限制条件

递归在书写的时候，有2个必要条件：
• 递归存在限制条件，当满⾜这个限制条件的时候，递归便不再继续。
• 每次递归调⽤之后越来越接近这个限制条件。

二、递归例题

递归经典例题

1.求n的阶乘

题⽬：计算n的阶乘（不考虑溢出），n的阶乘就是1~n的数字累积相乘。 我们知道n的阶乘的公式： n！ = n ∗ (n − 1)!

解题思路：n的阶乘为1234…(n-1)n，我们可以先用递推的思想，先算出n(n-1)的值，再用n(n-1)的值乘以(n-2),这样依次乘下去，以n=1为限制条件，返回1。然后再用回归思想，返回回去，及可得到n的阶乘。

int fact(int n)
{
	if (n <= 0)
		return 1;
	else
		return n * fact(n - 1);
}



#include<stdio.h>
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = fact(n);
	printf("%d\n", ret);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

运⾏结果（这⾥不考虑n太⼤的情况，n太⼤存在溢出）：

推演过程：

2.打印一个数的每一位

输⼊：1234 输出：1 2 3 4
输⼊：520 输出：5 2 0

例如1234：我们要想得到每一位数，比较好的方法就是拆分
当小于10时，直接取他本身。（所以1不用再计算）
可是这样的问题是，取到的数字是倒序。
那么我们可以先将123打印下来，最后再打印4.

图解递归过程：

三、递归的缺点

斐波那契数（演示）

斐波那契数不适合用递归求解的，但是斐波那契数的问题是通过递归的形式描述的：

看到这个公式，很容易让我们联想到递归，代码如下：

#include <stdio.h>
int Fib(int n)
{
	if (n <= 2)
		return 1;
	else
		return Fib(n - 1) + Fib(n - 2);
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fib(n);
	printf("%d", ret);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

运行结果：

这个函数使用了双递归的方式，暴露了一个问题：
当函数是第一级递归调用时，会创建一个变量n，然后在该函数中药要调用Fib()两次，在第二级递归调用又要分别创建两个变量n，这两次调用中的每次调用又会进行两次调用，因而在第三级递归中要创建4个名为n的变量。此时总共创建7个变量。由于每次递归创建的变量都是上一级递归的两倍，所以变量的数量呈现指数增长！
所以在这个例子中，指数增长的变量数量很快就消耗掉计算机的大量内存，导致程序崩溃。
图解如下：

所以，我们用迭代的方式，就能很好的实现斐波那契数的实现：

提示：

有时，递归确实比迭代简便很多，但是，如果递归的层次太深，就容易引起栈溢出的问题。

本小白的c语言学习时间很短，不知道这篇博客是否对你有帮助，如果各位大佬发现有不对的地方，请帮我指出，谢谢大家！！！