C语言学习(10)—递归

目录

1. 什么是递归

1.1 递归的思想

1.2 递归的限制条件

2. 递归举例

2.1 求n的阶乘

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

3. 递归与迭代

1. 什么是递归

递归就是函数自己调用自己，下图为递归的流程图

1.1 递归的思想

1.2 递归的限制条件

• 使用递归时，需要注意定义一个从函数退出的条件，否则会进入死循环。
• 每次递归调用之后越来越接近这个限制条件。

2. 递归举例

2.1 求n的阶乘

计算n的阶乘，n的阶乘就是1~n的数字累计相乘

 分析与代码现实： n=0时，n的阶乘为1，其余n的阶乘都可通过公式计算。

#include <stdio.h>

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

int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fact(n);
	printf("%d\n", ret);
	return 0;
}

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

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

分析和代码实现：n是一位数，n的每一位就是n自己；n超过一位数，就得拆分；可以发现数的最低位最容易得到，通过%10（得余数）就能得到，所以可以分成两步，通过/10拆分，再通过%10得到最后一位。

#include <stdio.h>

void Print(int n)
{
	if (n > 9)
	{
		Print(n / 10);
	}
	printf("%d ", n % 10);
}

int main()
{
	int m = 0;
	scanf("%d", &m);
	Print(m);
	return 0;
}

3. 递归与迭代

递归有时会被无用，比如上面的举例中求n的阶乘一样，看到推导的公式，很容易写成递归形式。这的确可以得到正确结果，但是在递归函数调用的过程中设计一些运行时的开销。

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

• 函数不返回，函数对应的栈帧空间就⼀直占用，所以如果函数调用中存在递归调用的话，每⼀次递归函数调用都会开辟属于自己的栈帧空间，直到函数递归不再继续，开始回归，才逐层释放栈帧空间。
• 所以如果采用函数递归的方式完成代码，递归层次太深，就会浪费太多的栈帧空间，也可能引起栈溢出（stack overflow）的问题。

所以不想使用递归就得想其他方法，通常就是迭代（通常就是循环的方式）

比如：计算n的阶乘，使用循环。 

int Fact(int n)
{
 int i = 0;
 int ret = 1;
 for(i=1; i<=n; i++)
 {
 ret *= i;
 }
 return ret;
}