遞歸
遞歸就是程序自己調(diào)用自己的過程再膳。
本身理解遞歸的思想比較容易扶檐，舉一個(gè)求階乘的例子：
def fact(n):
if n==1:
return 1
return n * fact(n - 1)
測試：
>>> fact(1)
1
>>> fact(5)
120
實(shí)際上遞歸程序不可能一直遞歸循環(huán)下去空免，需要利用其它條件來結(jié)束遞歸循環(huán)。這里求階乘的例子漾岳，就是當(dāng)n==1時(shí)就結(jié)束遞歸循環(huán)。
這里以fact(5)為例粉寞，看程序是如何進(jìn)行遞歸運(yùn)行的
===> fact(5)
===> 5 * fact(4)
===> 5 * (4 * fact(3))
===> 5 * (4 * (3 * fact(2)))
===> 5 * (4 * (3 * (2 * fact(1))))
===> 5 * (4 * (3 * (2 * 1)))
===> 5 * (4 * (3 * 2))
===> 5 * (4 * 6)
===> 5 * 24
===> 120
可以看出程序從fact(5)遞歸到fact(1)結(jié)束蝗羊。從上到下遞歸至結(jié)束，然后從下至上依次計(jì)算仁锯。
漢諾塔游戲
上面這個(gè)遞歸求階乘很好理解耀找。但是將遞歸的思想放到漢諾塔中，就不是那么容易明白了业崖。（關(guān)于漢諾塔的文章野芒，其實(shí)網(wǎng)上很多了，這里不會很詳細(xì)解說双炕。）簡單說下漢諾塔游戲的規(guī)則和玩法：
- 有三個(gè)柱子: a, b, c;
- a 上有數(shù)量為N個(gè)的圓盤狞悲；
- 從a柱將數(shù)量為N個(gè)的圓盤拿到 c 柱上；
- 一次只能拿一個(gè)圓盤妇斤，a,b,c 柱都可以利用摇锋；
- 無論在哪根柱子上丹拯，都是較大的圓盤永遠(yuǎn)在較小圓盤下面。
為了方便后面的理解荸恕，這里先說明幾個(gè)字母含義：
N：一個(gè)標(biāo)量乖酬，在下文中表示，第N個(gè)圓盤融求，N-1咬像，第N-1個(gè)圓盤
n: 代表前n個(gè)圓盤， n-1 代表前n-1個(gè)圓盤生宛；
a,b,c：分別表示三根柱子县昂；
—>: 箭頭表示從...移動到...
玩漢諾塔游戲可以分為三步：
- 將n-1個(gè)圓盤從 a 移到 b上；
- 將N圓盤從a 移到 c 上陷舅；
- 將n-1 個(gè)圓盤倒彰，從b 移到c 上。
玩漢諾塔就是不斷重復(fù)那三步莱睁，直到n-1=1待讳。
要將 n 個(gè)圓盤從 a 移到 c ，
則先將n-1個(gè)從a移到b缩赛，然后將N從a移動c耙箍，再將n-1從b移到c;
要將n-1個(gè)從a移到b，
則先將n-2個(gè)從a移到c酥馍，然后將N-1從a移動b辩昆，再將n-2從c移到b;
要將n-2個(gè)從a移到c，
則先將n-3個(gè)從a移到b旨袒，然后將N-2從a移動c汁针，再將n-3從b移到c;
要將n-3個(gè)從a移到b，
則先將n-4個(gè)從a移到c砚尽，然后將N-3從a移動b施无，再將n-4從c移到b;
......
在遞歸到最后一層，n- (n-1)=1, 也就是 a 柱第一個(gè)圓盤移向 b 還是 c 取決于N是奇數(shù)還是偶數(shù)必孤。（代幾個(gè)數(shù)測試下就知道了）
注：要將n-k個(gè)從一個(gè)柱子移到另一個(gè)柱子猾骡，需要借助第三個(gè)空閑柱子
紅色部分遞歸路徑，假設(shè)其為遞歸1號路線敷搪，在其下面還有其它遞歸分支（綠色表示）兴想。等紅色的從上往下遞歸到底后，程序從底下赡勘，往上開始計(jì)算嫂便，遇到綠色則開始遞歸，等綠色遞歸完后繼續(xù)計(jì)算上一層的闸与。
程序一開始的遞歸沿著紅色一直遞歸到最后一層（實(shí)際圓盤中最上面的那個(gè)）不再進(jìn)行遞歸毙替，直接開始搬運(yùn)圓盤岸售。然后運(yùn)行最后一層的剩余步驟（黑色，紅色）厂画，最后一層運(yùn)行完凸丸，
等計(jì)算完，紅色部分遞歸1號路線木羹，
程序運(yùn)行N(a)->c甲雅，
然后開始藍(lán)色部分的遞歸路徑（稱其遞歸2號路線）解孙，遞歸2號路線同1號路線一樣也有許多遞歸支路坑填。
為幫助理解，下面是一個(gè)路線圖弛姜，挺丑的脐瑰，湊合看。廷臼。
如果單純值拿紅色遞歸1號路線（不包括其遞歸支線）苍在，其實(shí)其和上面的遞歸階乘的例子是一樣的。但是漢諾塔這個(gè)有了許多遞歸支線荠商，就感覺復(fù)雜了許多寂恬。同時(shí)也可能因?yàn)閺腶->b, a->c, b->c, a->c,a-b...這三個(gè)字母混去混來的，腦袋記不住它們關(guān)系了莱没，容易犯渾初肉。但是你像圖片那樣將遞歸推導(dǎo)列出來就容易明白了。
代碼
# Python
def move(n, a, b, c): #從a將n個(gè)圓盤到c
if n == 1:
print(f"{a} --> {c}")
else:
move(n-1, a, c, b) #先將n-1圓盤從a移動到b
print(f"{a} --> {c}") #然后將a移到c
move(n-1, b, a, c) #再將n-1圓盤從b移動到c
move(4,'a', 'b', 'c')
#include <stdio.h>
// C
void move(int, char, char, char);
void move(int n, char x, char y, char z)
{
if (n == 1)
{
printf("%c --> %c\n", x, z);
}
else
{
move(n-1, x, z, y);
printf("%c --> %c\n", x, z);
move(n-1, y, x, z);
}
}
int main()
{
int n;
scanf("%d", &n);
move(n, 'a', 'b', 'c');
return 0;
}
參考：
原文: 漢諾塔游戲的遞歸解析
相關(guān)文章：
