目录
什么是递归
递归：“递推” + “回归”
在C语言中，函数递归就是：函数自己调用自己
将一件事情 “大事化小”，完成这些小事所用的方法都是相同的，只是参数不一样。
递归的限制条件
- 递归存在限制条件，当满足这个限制条件的时候，递归便不再继续。
- 每次递归调用之后越来越接近这个限制条件。
递归的例子
1、用递归求n的阶乘
//VS2022 x64
#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;
}
递归扩展学习
1、青蛙跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
思路
可以发现发现，跳到第n个台阶，最后一步，只有两种方法：
- 从 第 n-1 个 楼梯跳上一级台阶；
- 从 第 n-2 个 楼梯跳上两级台阶；
代码实现
#include<stdio.h>
int Jump(int n)
{
if (n == 1)
return 1;
else if (n == 2)
return 2;
else
return Jump(n - 1) + Jump(n - 2);
}
int main()
{
int n = 0;
scanf("%d", &n);
int sum = Jump(n);
printf("小青蛙有 %d 种跳法到第 %d 台阶", sum, n);
return 0;
}2、汉诺塔问题
给定三根柱子，记为 A,B,C，其中 A 柱子上有 n 个盘子，从上到下编号为 0 到 n−1 ，且上面的盘子一定比下面的盘子小。问：将 A 柱上的盘子经由 B 柱移动到 C 柱最少需要多少次？打印出每个步骤
移动时应注意：
- 一次只能移动一个盘子
- 大的盘子不能压在小盘子上
思路
先从简单的三个盘子试试，可以先不看答案自己画一画，挺好玩的，注意规则噢
（1）n个盘子从A柱到C柱最少移动次数
（2）打印出每个步骤
代码实现
#include<stdio.h>
void Move(char pos1, char pos2) //打印步骤
{
printf(" %c->%c ", pos1, pos2);
}
//pos1 起点
//pos2 中转站
//pos3 目的地
void Hannoi(int n, char pos1, char pos2, char pos3)
{
if (n == 1)
Move(pos1, pos3);
else
{
Hannoi(n - 1, pos1, pos3, pos2); //n-1个盘子借助 pow3 从 pow1->pow2
Move(pos1, pos3); //第n个盘子从 pos1 -> pos3
Hannoi(n - 1, pos2, pos1, pos3); //n-1个盘子借助 pos1 从 pos2->pos3
}
}
int main()
{
int n = 0; //需要移动的盘子数量
scanf("%d", &n);
Hannoi(n, 'A', 'B', 'C');
return 0;
}
总结
函数递归对于我这种初学者比较困难，一直在思考怎么才能把递归讲的通俗易懂，很显然，目前的我还很难做到， 对于青蛙跳台阶、特别是汉诺塔问题，我还很难熟练掌握其思想。虽然现在不太行，但我相信在日后的不断学习，绝对能够把这些知识稳稳收入囊中为我所用，所以各位也不必着急，相信自己，一定可以！
完
