导读

我们在利用编程解决实际问题时总会遇到这样一种问题，即分解后的子问题与原问题类似，能用原来的方法解决问题，且最终的子问题是已知解或易于解，通常我们可以使用一种特殊的解决问题的方法——递归

递归

其基本思想是：将要解决的问题分解成比原问题规模小的子问题，当解决这个子问题时，又可以用到原问题的解决方法，按照这个原则逐步递推，最终将原问题转换成较小且已知的解的子问题。

递归一般分为两个阶段：

递推

将原问题不断地转化成子问题， 逐渐从未知向己知推进， 最终到达已知解的问题，即递推阶段结束。

回归

从已知解的问题出发，按照递推的逆过程，逐一求值回归， 最后到达递归的开始处，即结束回归阶段，获得问题的解。

问题一般形式

诺可将求解问题逐步转化成与原问题类似的子问题，且最终子问题有明确的解，则可采用递归函数，实现问题的求解。

注：由于在递归函数中存在着调用自身的过程，因此要控制反复进入自身的函数体调用，必须在函数体中设置终止条件，当条件成立时，终止调用自身，并使控制逐步返回到主调函数。

爬楼梯问题：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。

解释：有两种⽅法可以爬到楼顶。

输⼊：n = 2

输出：2

第⼀种：1 阶 + 1 阶

第⼆种： 2 阶

题解：这是一道非常经典的例题，通过分析我们不难发现一个这样的规律，当我们第一步只爬一个台阶剩下的n-1个台阶有它的爬法个数，当我们第一步爬两个台阶剩下的n-2个台阶就有它的爬法。以此类推最终我们就可以得到这样一个函数关系式：

这明显符合我们递归问题，因此我们可以写出代码：

#include<stdio.h>
int Class(int n) {
  int i = 0;
  if (n == 1)
  return 1;
  if (n == 2)
  return 2;
  return Class(n - 1) + Class(n - 2);
}
int main()
{
  int n = 0;
  scanf("%d", &n);
  printf("%d", Class(n));
}

在我们运算过程中我们会发现总有那么几个数我们需要重复计算，大大的增加了我们的运算量，这里我们可以创造一张记忆表去记录我们已有的n：

#include<stdio.h>
int a[100] = { 0 };//创造记忆体
int b = 0;
int Class(int n)
{
  int i = 0;
  if (n == 1)
  return 1;
  if (n == 2)
  return 2;
  while (i <= b)
  {
  if (n == a[i])
    return a[i];
  }//判断楼梯阶数是否在记忆体中保留过
  int c = Class(n - 1) + Class(n - 2);
  a[b] = c;
  return c;
}
int main()
{
  int n;
  scanf("%d", &n);
  printf("需要爬%d", Class(n));
}```
当然这道题我们同样也可以使用一般循环的解法：
```c
#include<stdio.h>
int Class(int n)
{
  if (n == 1)
  return 1;
  if (n == 2)
  return 2;
  int c = 0;
  int i = 0;
  int pre = 2;
  int prepor = 1;
  for (i = 3;i <= n;i++)
  {
  c = pre + prepor;
  prepor = pre;
  pre = c;
  }
  return c;
}
int main()
{
  int n = 0;
  scanf("%d", &n);
  printf("需要爬%d", Class(n));
}

汉诺塔问题

古代有一个梵塔，塔内有3个座A、B、C,开始时A座上有64个盘子，盘子大小不等，大的在下，小的在上，有一个老和尚想把这64个盘子从A座移到C座，但每次只允许移动一个盘，且移动过程中在3个座上都始终保持大盘在下、小盘在上的状态。在移动过程中可以利用B座，要求编写程序并打印出移动的步骤。

题解：将n个盘子从A座移到C座可以分解为以下三个步骤:

将A座上n-1个盘子借助C座先移到B座上。

将A座上剩下的一个盘子移到C座上。

将n-1个盘子从B座借助A座移到C座上。

如果想将A座上3个盘子移到C座上，可以分解为以下三个步骤:

将A座上2个盘子借助C座移到B座上

将A座上1个盘子移到C座上;

将B座上2个盘子借助A座移到C座上。

其中第(2)步可以直接实现。第(1)步又可用递归方法分解为:

将A座上1个盘子从A座移到C座

将A座上1个盘子从A座移到B座

将C座上1个盘子从C座移到B座

将B座上1个盘子从B座移到A座上

将B座上1个盘子从B座移到C座上

将A座上1个盘子从A座移到C座上。

综合以上情况，可得到移动3个盘子的步骤为:

A→C, A→B，C→B，A→C，B→A，B→C，A→C

代码如下：

#include<stdio.h>
void Hanoi(int n, char A, char B, char C)
{
  if (n == 1)
  printf("%c->%c\n", A, C);
  else
  {
  Hanoi(n - 1, A, C, B);
  printf("%c->%c\n", A, C);
  Hanoi(n - 1, B, A, C);
  }
}
int main()
{
  int n = 0;
  scanf("%d", &n);
  Hanoi(n, 'A', 'B', 'C');
  return 0;
}

运行结果如下：