前言
上一篇寫了關于數學歸納法的一些概念，那么這一篇就該帶大家去體會一下遞歸了雪标。
正文
這一篇主要通過一個小游戲帶領大家走入遞歸的世界，這個游戲叫做漢諾塔 溉跃，先說下游戲規(guī)則村刨，如下圖所示，有三根柱子撰茎，我們需要把套在 A 柱子上的圓環(huán)全部移動到 B 上嵌牺，一次只能移動一個圓環(huán)，當然圓環(huán)的順序也得一樣龄糊。那么 C 柱則起到了中轉的作用逆粹。
下面是最終需要達到的結果
有點人可能會說，一開始就讓我們接觸這么多的圓環(huán)绎签，怎么也會搞混啊枯饿，那么我們就先從簡單一點的開始吧酝锅。先從只有三個的圓環(huán)入手诡必。
這里我們需要把 A 上的三個圓環(huán)借助 C 全部移動到 B 柱上。首先開始之前我們應該思考下搔扁，要想把三個全部移動到 B 柱上爸舒，則先需要把上面兩個拿到 C 柱，然后把最大的那個拿到 B 柱稿蹲，最后把上面的兩個放到最大的上面扭勉。當我們把兩個環(huán)拿到 C 的時候，勢必需要借助 B 柱作為一個臨時中轉苛聘，這樣我們就完成了移動的過程涂炎。寫成規(guī)范一點的步驟就是：
步驟一： 把兩個環(huán)從 A 柱經過 B 柱進行中轉移動到 C 柱忠聚。
步驟二： 把第三個環(huán)拿到 B 柱。
步驟三： 把兩個環(huán)從 C 柱經過 A 柱進行中轉移動到 B 柱唱捣。
經過這三個步驟我們就實現了三個圓環(huán)的移動两蟀。這時候我們就可以結合上一篇講過的數學歸納法進行遞推到如果有 n 個圓環(huán)怎么移動的問題了。
首先震缭，如果 n = 0 赂毯，不做任何移動。
其次拣宰，如果 n > 0 党涕，做三個步驟：
步驟一： 把 n - 1 個環(huán)從 A 柱經過 B 柱進行中轉移動到 C 柱。
步驟二： 把第 n 個環(huán)拿到 B 柱巡社。
步驟三： 把 n - 1 個環(huán)從 C 柱經過 A 柱進行中轉移動到 B 柱膛堤。
至于如何把 n - 1 個圓環(huán)移動，上面通過兩個環(huán)的例子已經給大家進行了簡單的說明重贺，這就是遞歸和數學歸納法的不同之處了骑祟，數學歸納法是先知道簡單的怎么做去推導出一般的結論，而遞歸則是知道一般的要求气笙，通過把一般的問題化成簡單的問題來解決次企。如果大家光聽理論有些混亂的話，可以去玩玩漢諾塔的小游戲體會下
當然最后我們得從程序員的角度去實現一下漢諾塔的解法
#include<stdio.h>
#include<stdlib.h>
void hanoi(int n,char x,char y,char z);
int main()
{
hanoi(6,'A','B','C');
getchar();
return 0;
}
void hanoi(int n,char x,char y,char z)
{
if(n == 0)
{
//不做任何動作
}
else
{
hanoi(n-1,x,z,y);
printf("%c -> %c\t",x,y);
hanoi(n-1,z,y,x);
}
}
我們可以通過游戲對程序的結果進行驗證潜圃，在下一篇中會對這個游戲有個簡短的總結缸棵。
這一篇通過一個小游戲帶大家粗略了解了遞歸的概念，后面還將有兩個例子和一個總結對遞歸進行了解谭期。
