函数递归经典题目——汉诺塔，青蛙跳台阶

时间：2024-01-24 17:40:40

函数递归(recursion)


函数递归(recursion)

程序调用自身的编程技巧。


只需要少量程序就可以描述除解题过程所需要的多次重复运算，大大减少了代码量


递归---把大事化小


必要条件 * 2

1存在限制条件，当满足这个限制条件时，递归便不再继续

2每次递归调用之后越来越接近这个限制条件


递归常见错误：

栈溢出（stack overflow）

任何一次函数调用都会在栈区占用一块空间，最后栈区无空间，就溢出 

int main()
{
	printf("hehe\12");
	main();//死循环

	return 0;
}
/※e.g.输入无符号数字1234，然后得到输出1 2 3 4
//※e.g.输入无符号数字1234，然后得到输出1 2 3 4(nb)
void print(int num)
{
	if (num > 9) {	//1234		12	
		print(num / 10);//123	1
	}
	printf("%d ", num  % 10);//1 
}

int main()
{
	unsigned int num = 0;
	printf("请输入一个大于9的数字:>");
	scanf("%d", &num);

	print(num);

	return 0;
}

递归与迭代

求n的阶乘
//求n的阶乘
int Fac1(int n)
{
	int i = 0;
	int ret = 1;
	for (i = 1; i <= n; i++)
		ret *= i;
	return ret;
}

int Fac2(int n)
{
	if (n <= 1)
		return n;
	else
		return Fac2(n - 1) * n;//nb
}

int main()
{
	int n = 0;
	printf("输入n，求n的阶乘:>");
	scanf("%d", &n);

	printf("%d! = %d\12", n, Fac1(n));
	printf("%d! = %d\12", n, Fac2(n));
	
	return 0;
}
e.g.2 编写函数，不允许创建临时变量，求字符串长度
#include<string.h>

int my_strlen(char* str)
{
	int count = 0;//用了临时变量
	while (*str != '\0')
	{
		count++;
		str++;
	}

	return count;
}

//函数1会影响函数2，用2时屏蔽掉!
int my2_strlen(char* str)
{
	if (*str != '\0')
		return 1 + my2_strlen(str + 1);
	else
		return 0;
}

int main()
{
	char arr[] = "I lost myself";

	//int len = strlen(arr);
	//int len = my_strlen(arr);

	int len = my2_strlen(arr);

	printf("%d", len);
	return 0;
}
e.g.求第n个斐波那契数（不考虑溢出）

斐波那契数列-->前两个数之和等于第三个数

Fib(n) = 1, n <= 2;

Fib(n) = Fib(n - 1) + Fib(n - 2), n > 2;

1 1 2 3 5 6 13 21 34 55 89... 

int Fib1(int n)//but 效率低，缺陷大
//算第40个，要跑39,000,000+次？？？
{
	if (n <= 2)
		return 1;
	else
		return Fib1(n - 1) + Fib1(n - 2);
}
//时间复杂度O(2^n)

int Fib2(int n)//迭代循环
{
	int a = 1;
	int b = 1;
	int c = 1;
	if (n <= 2 )
		return 1;
	while (n > 2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}

int Fib3(int n)//数组(易越界)
{
	int fibs[100] = { 0,1,1 };
	int i = 2;
	for (i = 2; i <= n; i++)
	{
		fibs[i] = fibs[i - 1] + fibs[i - 2];
	}
	return fibs[n];
}
//时间复杂度：O(n)


int main()
{
	int n = 0;
	printf("输入n，求第n个斐波那契数;>");
	scanf("%d", &n);
	//TDD-->测试驱动开发
	//先写怎么用，再去具体实现
	printf("%d", Fib3(n));
	return 0;
}

选递归还是选循环？

first of all，保证正确 ，其次可任选

递归满足了两个限制条件，就不会溢出嘛？

Not sure.

//栈溢出
void test(int n)
{
	if (n < 10000)//stack overflow
		test(n + 1);
}

int main()
{
	test(1);

	return 0;
}


函数递归经典题目案例

1.汉诺塔

2.青蛙跳台阶（广联达原题）

   ---《剑指offer》67道笔试题

1.汉诺塔

思路：n个盘子首先以大小顺序依次叠在A柱上，借助B柱实现从A柱平移到C柱上。难点在于每次移动都必须保证每根柱子上的盘子排序是下面的盘子比上面的大。

例：n=3时，A柱从上到下盘子编号为1,2,3，首先1盘-->C，2盘-->B，然后C上的1盘可以-->B，此时A只有3盘，B依次有1、2盘，C没有盘子。所以可以将A的3盘-->C，此时，A柱0盘。再将B柱的1盘-->A，那么B柱的2-->C，A的1-->C，移动结束。

函数递归经典题目——汉诺塔，青蛙跳台阶_i++

借助递归，省略了具体实现细节，从广义上解释移动过程——

将A上前n-1个盘子借助A、C移动到B上

把A上第n个移动到C上

将B上前n-1个盘子借助B、A移动到C上

//汉诺塔
void print(char a, char b)
{
	printf("%c-->%c\n", a, b);//输出移动过程
}
//递归，省略具体实现细节，nb
void Hanoi(int n, char a, char b, char c)
{
	if (n == 1)
		print(a, c);//A-->C
	else
	{
		Hanoi(n - 1, a, c, b);
		//将A上前n-1个盘子借助A、C移动到B上
		print(a, c);
		//把A上第n个移动到C上
		Hanoi(n - 1, b, a, c);
		//将B上前n-1个盘子借助B、A移动到C上
	}
}

int main()
{
	int n = 0;
	printf("请输入盘子的个数:>");
	scanf("%d", &n);

	printf("移动次序为:>\12");
	Hanoi(n, 'A', 'B', 'C');

	return 0;
}

2.青蛙跳台阶

一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。

求该青蛙跳上一个n 级的台阶总共有多少种跳法？

n = 1--->1

n = 2--->2

n = 3--->3

n = 4--->5

n = 5--->8

...

1,2,3,5,8...Fibs?

We can see, 第n次的跳法时第n-1次和第n-2次的和 


int Fib1(int n)
{
	//递归（效率低，运算大量重复）
	if (n <= 2)
		return n;
	else
		return Fib1(n - 1) + Fib1(n - 2);
}

int Fib2(int n)
{
	//循环
	int a = 1;
	int b = 2;
	int c = 0;

	if (n == 1)
		return a;
	else if (n == 2)
		return b;
	else
	{
		int i = 0;
		for (i = 3; i <= n; i++)
		{
			c = a + b;
			a = b;
			b = c;
		}
		return c;
	}
}

int main()
{
	int n = 0;
	printf("请输入台阶数n:>");
	scanf("%d", &n);

	printf("共有%d中跳法\n", Fib2(n));
	return 0;
}



相关文章