[C++知识库]C语言：函数递归详解（建议收藏）

一.基础概念

1.1函数递归的定义

程序调用自身的编程技巧称为递归（ recursion）。
递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接
调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。

1.2函数递归的优缺点

优点：函数递归只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的主要思考方式在于：把大事化小（这种思考方式十分重要）。
缺点：①如果函数递归使用不恰当，会导致栈溢出，因为每一次函数调用都会在栈区上申请内存空间。②每一次函数递归（函数调用）都会在函数栈帧上开辟一块空间，所谓的压栈。这样会大大降低我们代码的执行效率（这会在函数递归例题详解：斐波那系数中解释）。

1.3函数递归的两个必要条件

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

二. 入门级函数递归例题

2.1函数递归之死循环

我们了解了函数递归的基础概念后，来看看这段有趣而危险的代码。

#include <stdio.h>
int main()
{
	printf("cc\n");
	main();   //重复调用main函数
	return 0;
}

可想而知，程序最终会崩溃。因为每一次函数调用都会在栈上开辟一块空间，这种死循环的代码会一直开辟空间，直至栈溢出，正如上面的缺点②。

2.2输入输出1234

题目描述:

接受一个整型值（无符号），按照顺序打印它的每一位。
例如：
输入：1234，输出 1234

解题思路：这种输入输出数字的题，我们一定要想到取模和取余的方法,并且要有限制条件，每次函数递归后，都会越来越接近这个值。
所以先函数递推1234%10=4,123%10=3,12%10=2,1%10=1，给定限制条件n>9,直到n=1，打印出最后值（1），最后函数回归打印出1234。

设n为1234
print(1234/10) + 1234%10 (=4)
print(123/10) + 123%10（=3）
print(12/10) + 12%10（=2）
当n最后为1时，不满足我们给定的限制条件n>9时，即打印1%10（=1）

代码实现：

void print(unsigned int n) 
{
	if (n > 9)     //限定条件
	{
		print(n / 10);  //取模
	}
	printf("%d ", n % 10);  //取余
}
int main()
{
	unsigned int n = 0;
	scanf("%u",&n);
	//按顺序打印1234
	print(n);
	return 0;
}

三. 函数递归典型例题的实现

3.1求n的阶乘

题目描述:

用递归的方法求n的阶乘（不考虑溢出问题）
例如：
输入：4，输出 24

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

JC(n)
n * JC(n-1)
n * JC(n-1) * JC(n-2)
n * JC(n-1) * JC(n-2) * JC(n-3)
…
n * JC(n-1) * JC(n-2) * JC(n-3)…JC(1)
当满足我们的限制条件n=1时，返回1，然后回归

代码实现：

int JC (int n)
{ 
	if (n == 1) 
		return 1;
	else
		return n * JC(n - 1);         //阶乘的递归实现方式        
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = JC(n);
	printf("n的阶乘为：%d", ret);
	return 0;
}

3.2strlen函数的模拟实现

题目描述:

用递归的方法模拟实现strlen函数
例如：
输入：abc，输出 3

解题思路：strlen函数遇到’\0’才会停止，所以我们以’\0’为限制条件，我们每调用一次我们自己实现的my_strlen函数，次数就加一，直到遇到’\0’停止。

my_strlen(abc)--------------这里是指针在移动
1+my_strlen(bc)
1+my_strlen(b)
1+my_strlen(‘\0’)
当满足我们的**限制条件’\0’**时，返回0，然后回归

代码实现：

int my_strlen(char* str)
{

	if (*str != '\0')
	{
		return 1 + my_strlen(str + 1);     //strlen函数的模拟实现方式
	}
	return 0;
}
int main()
{
	char arr[] = "abc";
	int ret = my_strlen(arr);
	printf("%d", ret);
	return 0;
}

3.3求n的k次幂

题目描述:

用递归的方法实现n的k次幂
例如：
输入：3,3，输出 27

解题思路：以k>0和k=0为限制条件，每一次递推就乘以n，并且k都减一次1，直到不满足限定条件，然后回归，即为27。

n=3,k=3
Pow(n,3)
n * Pow(n,3-1)
n * Pow(n,2-1)
n * Pow(n,1-1)
以k>0和k=0为限制条件，当k=0时，直接返回1，然后回归

代码实现：

double Pow(int n, int k)
{
	if (k > 0)
		return n * Pow(n, k - 1);  //①    
	else if (k == 0)
		return 1;
	else
		return 1.0 / Pow(n, -k); //k是负数的时候---------------可以去步骤①,因为k大于零了 
}
int main()
{
	int k = 0;
	int n = 0;
	scanf("%d %d", &n,&k);
	double ret = Pow(n, k);
	printf("%.1lf\n", ret);
	return 0;
}

3.4字符串逆序

题目描述:

用递归的方法实现字符串逆序
例如：
输入：abcdef，输出 fedcba

解题思路：这题我们要以字符串长度为限制条件，先用临时变量tmp把a存起来，然后把f赋值给a,再把f置为’\0’（便于之后用strlen函数求字符串长度），每一次递推后面都要带有把tmp赋值给’\0’。之后再用临时变量tmp把存b起来,然后把e赋值给b,再把e置为’\0’…依次递推，直到字符串长度不大于1**时，回归回去，即可得到fedcba。

递推：
f b c d e \0
f e c d \0 \0
f e d \0 \0 \0
回归：
f e d c \0 \0
f e d c b \0
f e d c b a

代码实现：

void reverse_string(char* string)                      
{
	int len = strlen(string);
	char tmp = *string; 
	*string = *(string + len - 1);
	*(string + len - 1) = '\0';
	if(strlen(string+1) > 1 )           
		reverse_string(string + 1);
	*(string + len - 1) = tmp;             //这一步才能赋值，把tmp 赋值为'\0'
}
int main()
{
	char arr[] = "abcdef";
	reverse_string(arr);
	return 0;
}

3.5斐波那契数（递归实现和非递归实现）

3.5.1递归的实现

题目描述:

计算斐波那契数递归实现求第n个斐波那契数
例如：
输入：5 输出：5
输入：10， 输出：55
输入：2， 输出：1

解题思路：斐波那系数是前两项加起来等于后一项：1，1，2，3，5，8，13…,所以我们可以以n<=2为限制条件，当n=1或2时，返回1，然后到n=3项时就是n=1项和n=2项之和，然后依次往后推，即Fib(n)就是Fib(n-1)和Fib(n-2)之和。

Fib(n)
Fib(n-1) + Fib(n-2)
Fib(n-2)+Fib(n-3) , Fib(n-3)+Fib(n-4)
…
一直递推下去，直至到Fib(1)和Fib(2)返回值为1，然后回归，得到第n个斐波那契数

代码实现：

long Fib(int n)
{
	if (n <= 2)
		return 1;
	else
		return Fib(n-1) + Fib(n-2);   //前两项加起来等于后一项
}
int main()
{
	int n = 0;
	scanf("%d",&n);
	long ret = Fib(n);
	printf("%ld", ret);
	return 0;
}

3.5.2非递归的实现

题目描述:

计算斐波那契数递归实现求第n个斐波那契数
例如：
输入：5 输出：5
输入：10， 输出：55
输入：2， 输出：1

解题思路：也可以参考上面递归实现的思路，我们可以用三个变量相互替换来解决，n1为第一项，n2为第二项，tmp为第三项，运用while()循环，每一次循环n就减1，直到n=2，最后输出tmp。

n=5
n1=1,n2=1 ,tmp=n1+n2=2
n1=n2=1,n2=tmp=2,tmp=n1+n2=3
…
依次类推直到n为2停下，即可得第n个斐波那契数

代码实现：

int main()
{
	int n = 0;
	scanf("%d",&n);
	int i = 0;
	int n1 = 1;
	int n2 = 1;
	long tmp = 0;
	if (n == 1)
		printf("%d", 1);
	if (n == 2)
		printf("%d", 1);
	while (n>2)
	{
		tmp = n1 + n2;    //三项互相替换
		n1 = n2;
		n2 = tmp;
		n--;
	}
	printf("%1d", tmp);
	return 0;
}

3.5.3斐波那契数的非递归的实现优于递归实现的原因

①.函数递归的原则是大事化小”，对于很多问题的求解上是很遍历，而且非常迅速。但是他也是有缺点的，世界上没有完美的“事物”，函数递归也不例外。因为每一次函数递归（函数调用）都会在函数栈帧上开辟一块空间，所谓的压栈。这样会大大降低我们代码的执行效率。

②.这题用递归法实现的斐波那契数正对应了其缺点，因为它的递推时会有很多分支，一个分支下面又有很多分支，每一个小分支都是函数的调用，然而还有回归，函数栈帧需要销毁，这会大大降低代码的执行效率，如果n=50，则代码执行时间都要1个多小时（这里会涉及到数据结构中时间复杂度和空间复杂度的概念），所以用递归法实现的斐波那系数其实是不实用的。

③.而用非递归的方法实现，可以大大提高代码的运行效率。只是每一次循环，n1,n2,tmp会被赋值，代码执行次数大大减少，所以斐波那契数的非递归的实现优于递归实现的。

3.6经典问题之《青蛙跳台阶》

题目描述:

青蛙一次可以跳一级台阶，也可以跳两级台阶。求该青蛙跳n级台阶共有多少种跳法？
例如：
输入：5 输出：8

解题思路：青蛙跳台阶的思路是和斐波那系数的思路是完全等价的,只不过有了个主人公青蛙而已。因为青蛙跳1级台阶有一种走法，跳2级台阶有两种走法，而跳3级台阶有三种走法，所以跳3级台阶的走法是前面跳1级台阶和2级台阶之和，所以依次类推青蛙跳级台阶有一种走法等于跳n-1级台阶和n-2级台阶之和,所以问题就转变为求解第n个斐波那系数了。

walk(n)
walk(n-1) + walk(n-2)
walk(n-2)+walk(n-3) , walk(n-3)+walk(n-4)
…
一直递推下去，直至到walk(1)和walk(2)分别返回值为1和2，然后回归，得到青蛙跳n级台阶的跳法

代码实现：

long walk(int n)
{
	if (n ==1)
		return 1;
	if (n ==2)
		return 2;
	else
		return walk(n-1) + walk(n-2);   //前两项加起来等于后一项
}
int main()
{
	int n = 0;
	scanf("%d",&n);
	long ret = walk(n);
	printf("%ld", ret);
	return 0;
}

3.7经典问题之《汉诺塔问题》

题目描述:

总共有三个柱子，在一根柱子上，从下往上按照大小顺序摞着n片圆盘。我们需要按大小顺序重新摆放在另一根柱子上。并且规定，在移动过程，小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

解题思路：我们需要把圆盘看做一个一个的整体，而且需要有大事化小的思想。假设我们有三根柱子：A,B,C（A:表示起始位置，B:表示中转站
，C:表示目标位置）

• 如果A柱有n=1个盘子，我们只要把它移动到C柱上就可以了。对应过程演示（1）。
• 如果A柱有n=2个盘子，则需先把A柱上第一个盘子放到B柱上 -> 再把A柱上第二个盘子（这时n=1）放到C柱上。对应过程演示（2）。
• 如果A柱有n=3个盘子，①.第一步：则需先把A柱上第一个盘子放到C柱上 -> 再把A柱上第二个盘子放到B柱上 -> 然后把C柱上的盘子放到B柱上面 -> 然后把A柱上第三个盘子（这时n=1）放到C柱上。②.第二步：再想办法把B柱上的圆盘移动到A柱上,先把B柱上第一个圆盘放到A柱上 -> 再把B柱上的圆盘放到C柱上 -> 最后再把A柱上的圆盘放到C柱上。对应过程演示（3）。
• …
• 如果A柱有n个盘子，步骤是一样的，肯定是先想办法把A柱上n-1个圆盘移动到B柱上 -> 之后才能想办法把第n个圆盘从A柱放到C柱上面（即n=1的时候，递归的限制条件） -> 最后想办法把B柱上的圆盘移动到C柱上面。对应过程演示（4）。

这里递归的限制条件是n=1
并且一定要注意：我们在解决汉诺塔问题时，一定不能太过于深究里面圆盘移动的过程，因为比较复杂，很容易让人绕进去。所以我们这里不考虑上述中的“想办法”（即移动的过程）
我们只要懂其中的原理就可以把汉诺塔实现出来，运用大事化小的思想

代码实现：

void Move(char src, char dest)
{
	// src表示的是起始位置，dest表示的是目标位置
	printf("盘子从%c柱子->%c柱子\n",src,dest);
}
void Plate_Move(int n, char A, char B, char C)
{
	if (n == 1)
	{
		Move(A, C);   //这里即递归停下来的地方，把最底下一层的盘子（n），移动到C柱上
	}
	else //这里下面都是在递归ing!!! （下面这三条语句其实都是在同步进行的）
	{
		Plate_Move(n-1,A,C,B);//当不只一个圆盘时，我们先将上面 （n -1）个圆盘 借助 C柱子  从 A 柱子移动到 B 柱子
		
		Move(A, C);      //A柱剩余一个圆盘，将剩下的一个圆盘从 A 移动到 C
		
		Plate_Move(n - 1, B, A, C);  //以A柱为中转站，把B柱上的圆盘放在C上。
	}

}
int main()
{
	int n = 0;
	scanf("%d", &n);
	Plate_Move(n, 'A', 'B', 'C');  //n为几个圆盘，A,B,C分别对应A，B，C三个柱子
	return 0;
}

过程演示

（1）A柱上有1个圆盘：

（2）A柱上有2个圆盘：

（3）A柱上有3个圆盘：

（4）A柱上有n个圆盘：