函数的递归调用(零基础理解递归)

正文开始

一. 什么是递归

什么是递归?

递归是c语言学习中一个绕不开的话题, 那什么是递归呢? 递归其实就是一种解决问题的方法, 在c语言中, 递归就是函数自己调自己. 写一个史上最简单的C语言递归代码:

#include<stdio.h>

int main(){
printf("hehe\n");
main();//这里main函数又调用自己
return 0;
}

上述代码就是一个简单的递归程序, 只不过上面的递归只是为了演示递归的基本形式, 不是为了解决问题, 代码最终也会陷入死循环, 导致栈溢出 (Stack overflow).

二. 递归的限制条件

1. 递归的思想: 把一个大模型复杂问题层层转化为一个与原问题相似, 但规模较小的问题来求解, 直到子问题不能再被拆分, 所以递归的思考方式是把大问题化小的过程. 递归中的递就是递推的意思, 归就是回归的意思, 接下来请读者来体会.
2. 递归的限制条件: 递归在书写的时候, 有两个必要条件:

• 递归存在限制条件, 当满足这个限制条件的时候, 递归便不再继续.
• 每次递归调用之后越来越接近这个限制条件. 在下面的举例中, 我们会逐步体会到这两个限制条件

三. 递归的举例

• 举例1: 求n的阶乘 一个正整数的阶乘(factorial)是所有小于及等于该数的正整数的积, 并且0的阶乘为1. 自然数n的阶乘写作n!

题目:计算n的阶乘(不考虑溢出), n的阶层就是1~n的数字积累相乘.

• 分析和代码实现 我们知道n的阶乘的公式: n! = n * (n-1) !

举例:
5!=5*4*3*2*1
4!=4*3*2*1
所以5!=5*4!

这样的思路就是把一个较大的问题, 转化成一个与原问题相似, 但规模较小的问题来求解的. 当n==0的时候,n的阶乘是1, 其余的n的阶乘都是可以通过公式计算. n的阶乘的递归公式如下:

那我们就可以写出函数Fact求n的阶乘, 假设Fact(n)就是用来求n的阶乘, 那么Fact(n-1)就是求n-1的阶乘, 函数如下:

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

测试:

#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 result = Fact(n);
	printf("%d\n", result);
	return 0;
}

运行结果:

画图推演:

• 举例2: 顺序打印一个整数的每一位 题目: 输入一个整数m, 按照顺序打印整数的每一位 比如: 输入:1234 输出:1 2 3 4 输入:520 输出:5 2 0

分析和代码 这个题目, 放在我们面前, 首先想到的是, 怎么得到这个数的每一位呢? 如果n是一位的话, n的每一位就是n自己 n如果超过1位的话, 就拆分每一位

1234%10就能得到4, 然后1234/123, 这就相当于去掉了4, 以此类推, 不断的%10和/10的操作, 直到1234的每一位都得到; 但是这里有个问题就是得到的数字顺序是倒着的. 但是我们有了灵感, 我们发现其实一个数字的最低为是最容易得到的, 通过%10就得到, 那我们假设写一个函数Print来打印n的每一位,如下所示:

Print(n)
如果n是1234,那么表示
print(1234) 打印1234的每一位
其中1234中4可以通过%10得到,那么
print(1234)就可以拆分成为两步:
1.print(1234/10)
2.printf(1234%10)
完成上述2步,那就完成了1234每一位的打印
那么print(123)又可以拆分为printf(123/10)+printf(123%10)

以此类推下去, 就有

   Print(1234)
==>Print(123)						+printf(4)
==>print(12)			+printf(3)
==>print(1) + printf(2)
==>printf(1)

直到被打印的数字变成一位数的时候, 就不需要拆分, 递归结束 那么代码完成也就比较清楚:

#include<stdio.h>

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

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

输入输出结果:

画图推演:

四. 递归与迭代

递归是一种很好的编程技巧, 但是和很多技巧一样, 也是可能被误用的, 就像举例1一样, 看到推导的公式, 很容易写出递归的形式:

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

Fact函数是可以产生正确的结果, 但是在递归函数调用的过程中涉及一些运行时的开销. 所以如果不想使用递归就想得到其它的方法, 通常就是迭代的方式(通常就是循环的方式). 比如:计算n的阶乘,也是可以产生1~n的数字累计乘在一起的

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

事实上，我们看到的许多问题是以递归的形式进⾏解释的，这只是因为它⽐⾮递归的形式更加清晰， 但是这些问题的迭代实现往往⽐递归实现效率更⾼。 当⼀个问题⾮常复杂，难以使⽤迭代的⽅式实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销。

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

看到这公式，很容易诱导我们将代码写成递归的形式，如下所⽰：

int Fib(int n)
{
 if(n<=2)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}

测试代码：

#include <stdio.h>
int main()
{
 int n = 0;
 scanf("%d", &n);
 int ret = Fib(n);
 printf("%d\n", ret); 
 return 0;
 }

当我们n输⼊为50的时候，需要很⻓时间才能算出结果，这个计算所花费的时间，是我们很难接受的， 这也说明递归的写法是⾮常低效的，那是为什么呢？

其实递归程序会不断的展开，在展开的过程中，我们很容易就能发现，在递归的过程中会有重复计 算，⽽且递归层次越深，冗余计算就会越多。我们可以作业测试:

#include <stdio.h>
int count = 0;
int Fib(int n)
{
 if(n == 3)
 count++;//统计第3个斐波那契数被计算的次数
 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\n", ret); 
 printf("\ncount = %d\n", count);
 return 0;
}

在计算第40个斐波那契数的时候，使⽤递归⽅式，第3个斐波那契数就被重复计算了 39088169次，这些计算是⾮常冗余的。所以斐波那契数的计算，使⽤递归是⾮常不明智的，我们就得 想迭代的⽅式解决。

我们知道斐波那契数的前2个数都1，然后前2个数相加就是第3个数，那么我们从前往后，从⼩到⼤计 算就⾏了。 这样就有下⾯的代码：

int Fib(int n)
{
 int a = 1;
 int b = 1;
 int c = 1;
 while(n>2)
 {
 c = a+b;
 a = b;
 b = c;
 n--;
 }
 return c;
}

迭代的⽅式去实现这个代码，效率就要⾼出很多了。 有时候，递归虽好，但是也会引⼊⼀些问题，所以我们⼀定不要迷恋递归，适可⽽⽌就好。