首先，我们来看看什么是汉诺塔吧~记得初知汉诺塔，就是在今年的暑假游览科技馆的时候，里面就有汉诺塔的游戏，当然耐心烦躁的我并没有解决，没想到今日学习c语言还能看见它（捂脸）。
汉诺塔介绍
传说印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。（以上为废话）
在C语言中，可以使用递归算法来实现汉诺塔问题。汉诺塔问题是一个经典的递归问题，规定了三根柱子（A、B、C），其中A柱上有n个圆盘，按照从大到小的顺序堆叠。问题的目标是将这些圆盘从A柱移到C柱，并且在移动过程中要遵循以下规则：
1.每次只能移动一个圆盘。
2.大圆盘不能放在小圆盘上面。
那么，我们如何将64片金片移动到另一根针上呢？要解决这个问题，我们需要了解递归的相关知识。
递归知识点讲解
递归就是栈思想的应用。递归简单来说就是写一个函数，自己调用自己。
例如，一个函数就是它的语句块，在c语言里函数的执行都是从上往下的。当这个函数自己调用自己的时候，代码块从上往下的执行便会中断。代码块会被插入一个代码块，然后再执行这个代码块。以此类推，每次执行这个代码块调用到自身语句都会被插入又一个代码块。
每一个递归函数都有一个临界点，到达这个临界点时停止调用自己，这样函数就能执行被打断调用的语句了。
递归的优点是算法简单、容易理解，代码行数少。
递归的一个缺点就是存在大量的重复计算，运行起来浪费时间也浪费空间。
递归的另一个缺点是递归的层数不能太多（不能递归太深）。那递归得太深了会怎样呢？答案是会爆栈。（以上内容为引用，我并不能理解爆栈的意思，希望有人可以给我解释一下~~）
再看一下递归函数的构成 以n！为例
来个栗子：写一个简单的递归函数
void f(int n)//函数返回类型 函数名（参数） {if(n==1) printf("1"); return; } else { f(n-1); printf("%d",n); } }
这是一个打印出1到n数字的函数。那么，这个递归函数是如何运作起来的呢？
例如输入n=10,第一次执行时执行else中的语句块（n为10的语句块被打断插入n为9的语句块），以此类推，语句块被不断插入，直到n=1。n=1执行if内的语句块，打印1后执行return函数，n=1的函数结束执行。然后程序就会执行被打断的printf语句，然后执行每一次的函数。
斐波那契数列
也可以用递归函数实现斐波那契数列，在利用递归解决这个函数之前，我们先用迭代的思想解决它，并且在最后对比这两种方法：
1迭代利用函数！
#include <stdio.h> // 迭代函数计算斐波那契数列 void fibonacci(int n) { int a = 0, b = 1, c; for (int i = 0; i < n; i++) { printf("%d ", a); c = a + b; a = b; b = c; } } int main() { int n; // 输入要计算的斐波那契数列的项数 printf("输入要计算的斐波那契数列的项数: "); scanf("%d", &n); // 输出斐波那契数列的前 n 项 fibonacci(n); return 0; }
2普通版（老老实实for循环）
#include<stdio.h> int main(){ int n=0; printf("输入你要打印的代码行数:"); scanf("%d",&n); int f1,f2; for(int i=0;i<=n;i++){ f1=f1+f2;//此处的f1为更新前的f1 f2=f1+fn; } printf("%d %d",f1,f2); printf("\n"); return 0; }
3递归函数实现
递归属于逆向思维，我们从最终想要的答案出发，逐步寻找上一层的答案，并且用他们构造当前层的答案。例如上图，我们要求得f（4）的值就要不断向上寻找。
#include<stdio.h> //定义递归函数计算斐波那契数列 int fibonacci(int n){ if(n<=1) { return n;//如果n为0或1，结果为自身 } else { return fibonacci(n-1)+fibonacci(n-2); } } int main() { int n=0; printf("输入你需要计算的斐波那契数列的项数："); scanf("%d",&n); //输入要计算的斐波那契数列的项数 for(int i=0;i<n;i++) { printf("%d",fibonacci(i); } return 0; }
迭代和递归对比
实现方式：
迭代： 通过循环结构，反复执行一组指令，直到满足特定条件为止。迭代通常使用循环语句（如for、while）来实现。
递归： 通过将问题分解为更小的、与原问题相似的子问题，并反复应用这个过程，直到达到基本情况（递归的终止条件）为止。
性能：
迭代： 通常比较直观，有时可能更高效，因为迭代往往不需要维护额外的函数调用栈。
递归： 可能会更简洁、易读，但有时可能导致函数调用栈溢出，尤其是对于大规模问题。
空间复杂度：
迭代： 通常具有较低的空间复杂度，因为循环通常不需要额外的栈空间。
递归： 每次递归调用都需要在内存中维护一个函数调用栈，因此可能占用更多的内存空间。
汉诺塔思路讲解
我们要把第一个杆子以小的在上，大的在下的原则移走，想要把第三个圆盘移走，那么前两个就不能移动，所以我们得把前两个放置到B上。但是要想把前两个放置到B上，就得把最小的圆盘先移走，再把中等大小的圆盘放在B上，最后把最小的圆盘移回B，此时就可以移动最大的圆盘到C上。 
C移动到B
A移动到C，B1移动到A
如果我们要移动的圆盘上没有别的圆盘，那么我们就可以直接对其移动，此时，我们生成三个概念：起始杆，中转杆和目标杆。
我们对于目标不同的盘子，转换的方法不同，那么我们在要生成的函数中定义一个坐标n，表示我们要移动的圆盘的数量，然后我们需要传入三个字符变量start,temp,end，分别对应起始杆，中转杆和结束杆。设置结束点为n=1，但是如果要转移的圆盘数目不止一个呢？我们就需要中转杆来实现目标。
代码实现
这个问题看似复杂，但我们将大问题不断分解，就可以划分为一个圆盘的小问题，而move函数正是负责移走n-1个圆盘，将n变为最上面一个圆盘（即n为1）的问题，而移走n-1个圆盘也正是不断分解为把目标圆盘变为最上面的圆盘移走。 
当我们利用递归函数把n-1个函数都移动到中转杆上时，还需要再执行一次由起始杆到中转杆，再到目标杆的过程。 
。以下是用C语言实现汉诺塔问题的递归代码：
#include <stdio.h> // 函数原型 void hanoi(int n, char start, char temp, char target); int main() { int n; // 输入汉诺塔的圆盘数量 printf("Enter the number of disks: "); scanf("%d", &n); // 调用递归函数解决汉诺塔问题 hanoi(n, 'A', 'B', 'C'); return 0; } // 递归函数实现汉诺塔 void hanoi(int n, char strat, char temp, char target) { // 基本情况：只有一个圆盘 if (n == 1) { printf("Move disk 1 from %c to %c\n", start, target);//如果只有一个圆盘可以直接从起始杆转移到目标杆 return; } // 将n-1个圆盘从起始杆移动到中转杆 hanoi(n - 1, start, target, temp); // 移动最大的圆盘到目标杆 printf("Move disk %d from %c to %c\n", n, start, target); // 将n-1个圆盘从中转杆移动到目标杆 hanoi(n - 1, temp, start, target); }
写这篇博客前前后后花了三天时间，有些内容调试了很久，脑袋还有些晕乎。希望之后自己还能再消化消化，欢迎各位交流！
最近很多地方都下雪了，附一张故宫的雪，希望以后有机会能去看看故宫的雪！也祝大家生活愉快，2023快结束了呀~ 
