学习日志（十一）

函数递归

递归就是函数自己调用自己，把大事化小的过程

典型递归：求n的阶乘

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

}

汉诺塔问题：

汉诺塔问题的设定是这样的：有三根柱子，标记为A、B和C。初始时，所有的盘子按照从大到小的顺序从柱子 A 上方开始堆叠。目标是将这些盘子按照相同的顺序移动到柱子C上，同时满足以下规则：

1．每次只能移动一个盘子。

2．在移动过程中，任何时刻都不能将大盘子放在小盘子上方。

汉诺塔问题的解决方案是使用递归算法。下面是解决汉诺塔问题的一般步骤：

1．当只有一个盘子时，直接将盘子从源柱子移动到目标柱子。

2. 当有多个盘子时，可以将问题分解为三个子问题：a．将前n-1个盘子从源柱子移动到辅助柱子（利用目标柱子作为辅助）。

b．将最后一个盘子从源柱子移动到目标柱子。

c．将前n-1个盘子从辅助柱子移动到目标柱子（利用源柱子作为辅助）。

3．通过递归地应用上述步骤解决子问题。

#include <iostream>

using namespace std;

void move(int n, char x, char y) {

cout << n << ": " << x << " -> " << y << endl;

}

void hanoi(int n, char one, char two, char three) {

if (n == 1) {

move(n, one, three);

} else {

hanoi(n - 1, one, three, two);move(n, one, three);

hanoi(n - 1, two, one, three);

}

}

int main() {

int m;

char a, b, c;

}