详解C语言中的递归原理

函数递归

一、什么是递归

程序调用自身的编程技巧称为递归，递归作为一种算法在程序设计中广泛应用。一个过程或函数在定义或说明中有直接或间接调用自身的一种方法，他通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来解决，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的主要思考方式在于把大事化小

 

二、递归的两个必要条件

• 存在限制条件，当满足这个限制条件的时候，递归便不再继续
• 每次递归调用后越来越接近这个限制条件

 

最简单的递归调用：

#include <stdio.h>
int main()
{	
	printf("hehe\n");
	main();
	
	return 0;
}

这个程序的结果就是死循环的打印 hehe

去运行了的人就会发现，这个循环他跑一会就挂掉了，不会一直循环下去，这是什么原因，下面就来剖析

我这里用的是dev 如果你的是 vs 之类的编译器会提示一个错误

stack overflow : 栈溢出 这是递归常见的错误

栈溢出的原因： 

• 栈区：存放局部变量、函数形参
• 堆区：存放动态开辟的内存
• 静态区：存放全局变量、static修饰的变量

动态开辟的内存：比如说，malloc、calloc这样的函数所开辟的空间都在堆区开辟的

分析上图所代表的意思：任何一次函数调用，都要在栈区里为它分配一个空间，代码中，首先进入main函数中，即第一次调用在栈区中分配一块空间，完了之后会调用printf函数，再一次在栈区中为printf分配一块空间，一直递归调用下去，直到栈空间被消耗完，就会抛出栈溢出这个错误

 

【练习1.】

要求：接收一个整型（无符号），按照顺序打印他的每一位，例如，输入：1234 ； 输出：1 2 3 4

思路：

• 比较普通：1234 % 10 = 4 ；1234 / 10 = 123

                            123 % 10 = 3 ； 123 / 10 = 12

                            12 % 10 = 2 ； 12 / 10 = 1

                            1 % 10 = 1

                            这样就可以得到倒序的 4 3 2 1 了，在把它们一个一个存起来，倒着打印

• 递归：

#include <stdio.h>

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

int main()
{
	unsigned int num = 0;
	scanf("%d",&num);
	print(num);
	
	return 0;
}

代码解析：n > 9 表示 n 的值是个位数，当值为个位数的时候就直接输出就可以了

函数调用完后最终是要返回到主函数的

最简单的递归和这一次的练习作比较：为何那个最简单的递归会发生栈溢出而练习的代码却不会，其实从代码中不难发现，练习中的代码加了条件

if(n > 9)
	{
		print(n/10);
	}

在n > 9 的时候才调用函数，栈区完全够用，所以不会发生栈溢出，而在简单递归里是没有条件的。

 

【练习2.】

要求：编写函数，不允许创建临时变量，求字符串的长度（意思：写一个函数来求字符串长度，但是代码中不能创建临时变量）

 

思路：我们知道字符串的结束标志是 ‘\0’ ,所以就可以定义一个数组来存放字符串，然后在要调用的函数中创建一个临时变量，来计算字符的个数，每遍历一个如果不是 ‘\0’ 那就自增加一，直到遇到 ‘\0’ 时结束调用，返回临时变量的值，就是字符串的长度。单位：字节

数组传参传过去的不是整个数组，而是首元素的地址

 

代码一：创建临时变量

#include <stdio.h>
int arr(char arr2[])
{
	int count = 0;
	int i = 0;
	
	while(1)
	{
		if(arr2[i] == '\0')
		{
			break;
		}
		i++;
		count ++;
	}
	return count;
}

int main()
{
	char arr1[] = "nihao";
	int ret = arr(arr1);
	printf("%d\n",ret);
	
	return 0;
}

运行结果：5

#include <stdio.h>
int arr(char* arr2)
{
	int count = 0;
	
	while(*arr2 != '\0')
	{
		arr2++;
		count ++;
	}
	return count;
}

int main()
{
	char arr1[] = "nihao";
	int ret = arr(arr1);
	printf("%d\n",ret);
	
	return 0;
}

运行结果：5

上面提供了两种创建临时变量的写法
分析：第一种写法的 char arr2[]，相当于第二种写法的 char*arr2 ，都是来接收 arr1 的首元素地址的，对于第二种写法while循环条件中 *arr2 是解引用，简单地说，就是当前地址对应内存中的值，arr2++ 的意思是指向下一个地址，在写法一中我们使用循环变量 i 来代替元素下标，只不过写法二会节省代码。循环每执行一次，值只要不为 ‘\0’ 那 count 就自增加一，当遇到 ‘\0’ 后结束循环，返回 count 的值，即字符串的大小。

 

代码二：不创建临时变量（题目要求）

#include <stdio.h>
int arr(char* arr2)
{
	if(*arr2 != '\0')
		return 1 + arr(arr2 + 1);
	else
		return 0;
}

int main()
{
	char arr1[] = "nihao";
	int ret = arr(arr1);
	printf("%d\n",ret);
	
	return 0;
}

分析：这种是递归的解决方法，arr(arr2 + 1) 中的 arr2 + 1 意思是指向下一个元素的地址，注意这里的 arr2 + 1 与 arr2 ++ 是不一样的，我个人的理解是这样的，之前的代码出现  arr2 ++ 是因为前面没有操作数，所以它最终的结果就是指向下一个指针，而这里的代码 arr2 + 1 前面还调用了一个函数，若果写成 arr2 ++ ，那就是把 arr2 当前值传给下一层函数然后本层函数的地址变为下一个元素的地址，这就使程序乱了，造成错误！ 对于 1 + arr(arr2 + 1)，可以这么理解，从主函数传地址进来，那个地址是首元素地址，解引用后对应的字符是 n ，不等于 '\0' 所以就表示字符大小最少有一个字节，当执行了arr2 + 1后就指向第二个元素，如果第二个元素还是不为 ‘\0’ 就说明该字符串最小有两个字节 ，变成 -> 1 + 1 +arr(arr2 + 1) ，以此类推，直到遇到字符为 ‘\0’ 后返回，这样就可以得到字符串的大小且不使用临时变量，下面就来画图深入剖析递归

（这里为了操作方便我把字符串改成 3 个字节的 bit，原理是一样的）

 

三、递归与迭代

迭代：是循环的一种方式

我们通过练习来了解递归与迭代

 

【练习1.】

要求：求 n 的阶乘（不考虑溢出）

分析：n 的阶乘是怎么回事，假设 n = 3，那 3 的阶乘就是 1 x 2 x 3，若果 n = 4，那 4 的阶乘就是 1 x 2 x 3 x 4  , 1 的阶乘是1 x 1 ，所以 n 的阶乘就是 1 x 2 x 3 x ... x n

代码：

使用递归来解决，由上面的分析我们可以知道，n的阶乘后面每一个数都是前一个数减去一，这样的话，使用递归就会方便很多，n * 函数（n - 1）即可实现 n 的阶乘

#include <stdio.h>
int fac(int n)
{
	if(n <= 1)
		return 1;
	else
		return n*fac(n - 1);
}

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

【练习2.】

要求：求第 n 个斐波那契数（不考虑溢出）

斐波那契数列，又称黄金分割数列

斐波那契数：1、1、2、3、5、8、13、21、34、55......

由此可发现规律：前两个数之和等于第三个是，所以当 n > 2时 n = （n - 1）+（n + 1），且斐波那契数的前两个都是 1 ，所以当 n 小于等于 2 时，直接返回 1 即可

代码：

#include <stdio.h>
int fac(int n)
{
	if(n <= 2)
		return 1;
	else
		return fac(n - 1) + fac(n - 2);
}

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

像这种调用两个函数的在本章中第一次见，接下来画图剖析

下面就来打印某个数在数列中被重复计算的次数

#include <stdio.h>

int count = 0;

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

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

计算第30个斐波那契数时，数字 3 被重复计算了 317811 次

 

使用迭代解决斐波那契数问题

代码：

#include <stdio.h>

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

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

分析：a、b、c 分别代表第一个数第二个数第三个数，对应递归中代码：（n-2）（n-1），有些人不理解循环中的换位是什么意思，下面就来举个例子

假设 n = 4 ，对应的斐波那契数就是 3

斐波那契数的第一个和第二个数都是 1 ，所以 a = 1，b = 1

第一轮循环：

c = a + b (c = 2)

a = b (a = 1)

b = c (b = 2)

n-- (n = 2)

第二轮循环：

c = a + b (c = 3)

a = b (a = 2)

b = c (b = 3)

n-- (n = 1)

不满足条件循环结束 c = 3，返回 c 的值

 

总结：由上面的实例可知，递归和迭代都可以解决问题，那什么时候用递归什么时候用迭代就要看情况了，那种用起来简单就用哪一种，但是有个前提，就是两种写法都必须没有问题，比如说，使用递归写会出现问题，而用迭代不会，那就用迭代，不能用递归；在保证两种都没问题的情况下用递归写能提高程序的运行效率，而迭代不能，那就使用递归

 

注意：递归并不是加了条件就不会发生栈溢出

例如下面代码：

#include <stdio.h>

int test(int n)
{
	if(n < 1000)
	{
		test(n + 1);
	}
}

int main()
{
	test(1);
	
	return 0;
}

这样也会发生栈溢出，条件允许的范围过大，导致栈空间不足