C语言函数递归习题

每天进步一点点，坚持带来大改变！！！

 

目录

1.什么是函数递归?

2.函数递归的核心什么？

3.如何学好函数递归？

练习习题+画图

练习1：

画图详解：

 练习2

画图详解：

练习3

练习4 

练习5 

练习6 

练习7 

4.函数递归应该注意什么？ 

1.考虑时间复杂度会不会过高。

2.必须有限制条件，并且每次调用的时候越来越接近这个限制条件

---

1.什么是函数递归?

递归：将大事化小，用简单的代码解决复杂的问题。

2.函数递归的核心什么？

核心：一个"递"和一个"归"，首先是不断调用自身——“递”，当不满足条件后，不断返回——“归”。

3.如何学好函数递归？ 练习习题+画图 练习1：

题目：接受一个值，然后按顺序打印它的每一位

例：输入1314，输出1  3  1  4

实现思路： 

1.递：print(131) 归：打印1314%10

2.递：print(13)   归：打印131%10  4

3.递：print(1)     归： 打印13%10  1  4

4.归：打印1%10 3  1  4

#include

void print(int n)
{
	if (n > 9)
	{
		print(n / 10);
	}
	printf("%d ", n%10);
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	print(n);

	return 0;
}

 

画图详解：

红色表示调用（递），蓝色表示归

 练习2

题目：用递归求字符串的长度

实现思路： 

如果=='\0'则返回0

如果！='\0';

1.my_strlen("abc")

2.1+my_strlen("bc")

3.1+my_strlen("c")

4.1+my_strlen("")

#include
int my_strlen(char* str)
{
	if (*str == '\0')
		return 0;
	else
		return 1 + my_strlen(str + 1);
}
int main()
{
	char ch[] = "abc";
	int len = my_strlen(ch);
	printf("%d\n", len);

	return 0;
}

画图详解：

 

练习3

题目：求n的阶乘

实现思路：

假设求5的阶乘：5*4*3*2*1 <==>5*4!

#include
int fac(int n)
{
	if (n <= 1)
		return 1;
	else
		return n * fac(n - 1);
}
int main()
{

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

	return 0;
}

 

练习4 

传一个参数：

题目：

编写一个函数 reverse_string(char * string)

实现：将参数字符串中的字符反向排列

思路实现：

第一步：用临时变量存放第一个字符。

第二步：将最后一个字符放到第一个字符的位置。

第三步：最后一个字符的位置放‘\0’.

第四步：逆序中间的字符（递归调用函数）。

第五步：将临时变量的值放到最后一个字符的位置。

 递归的条件：如果中间的元素>=2的时候继续递归

#include
#include
void reverse_string(char* str)
{
	char tmp = *str;
	int len = strlen(str);
	*str = *(str + len - 1);
	*(str + len - 1) = '\0';
	if (strlen(str + 1) >= 2)
	{
		reverse_string(str + 1);
	}
	*(str + len - 1) = tmp;

}
int main()
{
	char ch[] = "abcdef";
	reverse_string(ch);
	printf("%s\n", ch);

	return 0;
}

 

传多个参数：

实现思路：

第一步：将第一个字符存放到临时变量。

第二步：将最后一个字符存放到第一个字符的位置。

第三步：将临时变量的值存放到最后一个字符的位置。

第四步：调用递归函数。

递归条件：中间只剩一个元素的时候不交换。

#include
#include

void reverse_string(char* str,int left,int right)
{
	if (left < right)
	{
		char tmp = str[left];
		str[left] = str[right];
		str[right] = tmp;
		reverse_string(str, left + 1, right - 1);

	}
}
int main()
{
	char ch[] = "abcdef";
	int left = 0;
	int right = strlen(ch) - 1;
	reverse_string(ch, left, right);
	printf("%s\n", ch);

	return 0;
}

 

 

练习5 

题目：编写一个函数实现n的开次方

实现思路：

举例：2的3次方，可以简化为2*2的2次方（递归调用函数）

三种情况：

k=0     1;

k<0     n^-k;

k>0     n*n^k;      

 

#include

double Pow(int n, int k)
{
	if (k < 0)
	{
		return (1.0 / Pow(n, -k));
	}
	else if (k == 0)
	{
		return 1;
	}
	else 
	{
		return n * Pow(n, k - 1);
	}

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

 

练习6 

题目：青蛙一次可以跳一个台阶或两个台阶，请问有个n个台阶时有多少种跳法？

思路实现：

第一种情况：当台阶数<=2 的时候  跳法就等于台阶数。

第二种情况：当台阶数>2的是时候，如果第一次跳一阶台阶，跳法数目就等于剩下的n-1级台阶的数目；如果第一次跳两阶台阶，跳法数目就等于剩下的n-2级台阶的数目。

本质上可以理解为斐波那契数列的问题。

#include

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

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

 

练习7 

汉诺塔问题：

题目：假设有三个命名为X,Y,Z的塔座，在塔座上插有n个直径大小各不相同，依小到大编号为1，2，……n的圆盘。先将X塔座上的n个圆盘移至到Z塔上，按照同样的顺序叠排，圆盘移动时必须遵循以下原则：

1.每次只能移动一个圆盘；

2.圆盘可以插在X,Y，Z中的任何一个塔座上；

3.任何时候都不能将一个较大的圆盘压在较小的圆盘上。

 思路实现：

第一种情况：当只有一个圆盘的时候，直接从X塔移动到Z塔。

第二种情况：当>=两个圆盘的时候，先将n-1个圆盘借助Z移动到Y上，然后再将剩下的一个圆盘直接从X塔移动到Z塔上，再将n-1个圆盘借助X移动到Z上。

代码说明：pos1——>X:起始位置；

pos2——>Y:中转位置；

pos3——>Z:目的位置

本质上:圆盘移动的次数：(2^n)-1;

#include
void move(char pos1, char pos2)
{
	printf("%c->%c ", pos1, pos2);
}
void Hanoi(int n, char pos1, char pos2, char pos3)
{
	if (n == 1)
	{
		move(pos1, pos2);
	}
	else
	{
		Hanoi(n - 1, pos1, pos3, pos2);
		move(pos1, pos3);
		Hanoi(n - 1, pos2, pos1, pos3);
	}
}
int main()
{
	Hanoi(1, 'X', 'Y', 'Z');
	printf("\n");
	Hanoi(2, 'X', 'Y', 'Z');
	printf("\n");
	Hanoi(3, 'X', 'Y', 'Z');


	return 0;
}

 

4.函数递归应该注意什么？  1.考虑时间复杂度会不会过高。

求第n个斐波那契数列的值：

实现思路：1 1 2 3 5 8 13 21 34 55 89……

当n>3时：前两个数之和等于后一个数 

求第十个斐波那契数的值：相当与求第9个的值+第8个的值

#include

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("ret = %d\n", ret);

	return 0;
}

 

存在问题：当求第50个斐波那契数的值的时候计算速度会很慢

原因：时间复杂度高，不适合用递归求解

可以用迭代的方式：

#include

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

	int n = 0;
	scanf("%d", &n);
	int ret = Fib(n);
	printf("ret = %d\n", ret);

	return 0;
}

 当用迭代解决的时候速度非常快，负值的原因时因为溢出了。

总结：当用递归解决问题的时候如果复杂度过高，递归就不适用了，可以用迭代。

2.必须有限制条件，并且每次调用的时候越来越接近这个限制条件

解释：当不存在限制条件的时候造成死递归——栈溢出