目录

1、什么是递归？

1.1 递归的思想

1.2 递归的限制条件

2. 递归举例

2.1 举例1：求n的阶乘

2.2 举例2：顺序打印⼀个整数的每⼀位

 3. 递归与迭代

扩展学习：

早上好，下午好，晚上好

1、什么是递归？
 

#include <stdio.h>
int main()
{
 printf("hehe\n");
 main();//main函数中⼜调⽤了main函数
 return 0;
}

 题⽬：计算n的阶乘（不考虑溢出），n的阶乘就是1~n的数字累积相乘。

 n的阶乘的公式： n！ =  n ∗ (n − 1)!

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

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

画图演示：

2.2 举例2：顺序打印⼀个整数的每⼀位

1234%10就能得到4，然后1234/10得到123，这就相当于去掉了4

然后继续对123%10，就得到了3，再除10去掉3，以此类推

不断的 %10 和 /10 操作，直到1234的每⼀位都得到

但是这⾥有个问题就是得到的数字顺序是倒着的

但是我们有了灵感，发现其实⼀个数字的最低位是最容易得到的，通过%10就能得到

那我们假设想写⼀个函数Print来打印n的每⼀位，如下表⽰：

Print(n)
如果n是1234，那表⽰为
Print(1234) //打印1234的每⼀位

其中1234中的4可以通过%10得到，那么
Print(1234)就可以拆分为两步：
1. Print(1234/10) //打印123的每⼀位
2. printf(1234%10) //打印4
完成上述2步，那就完成了1234每⼀位的打印

那么Print(123)⼜可以拆分为Print(123/10) + printf(123%10)

以此类推下去，就有

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

直到被打印的数字变成⼀位数的时候，就不需要再拆分，递归结束。

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

在这个解题的过程中，我们就是使⽤了⼤事化⼩的思路

把Print(1234) 打印1234每⼀位， 拆解为 ⾸先 Print(123) 打印123的每⼀位，再打印得到的4

把Print(123) 打印123每⼀位，拆解为⾸先 Print(12) 打印12的每⼀位，再打印得到的3

直到Print打印的是 ⼀位数 ，直接打印就⾏。

画图推演:

 3. 递归与迭代

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

 看到这公式，很容易诱导

#include <stdio.h>
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("%d\n", ret); 
 return 0;
}

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;
}

 假设总共需要移动n个盘子
1.将A柱上的n-1个盘子借助C柱移向B柱
2.将A柱上仅剩的最后一个盘子移向C柱
3.将B柱上的n-1个盘子借助A柱移向C柱

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

void move(int x, int y)
{
	printf("%c->%c\n", x, y);
}
void hanoi(int n, char a, char b, char c)
{
	if (n == 1)
	{
		move(a, c);
	}
	else
	{
		hanoi(n - 1, a, c, b);//将A座上的n-1个盘子借助C座移向B座
		move(a, c);//将A座上最后一个盘子移向C座
		hanoi(n - 1, b, a, c);//将B座上的n-1个盘子借助A座移向C座
	} 
}
//move中的实参与hanoi函数中的形参相对应，而hanoi函数中形参a，b，c所对应的值也是在有规律的变化
int main()
{
	int n = 0;
	scanf("%d", &n);
	hanoi(n, 'A', 'B', 'C');
	return 0;
}

 感谢观看