C語言遞歸思想實現漢諾塔詳解
1.遞歸思想簡介
在c語言中，程序調用自身的編程技巧稱為遞歸（ recursion）。
遞歸的定義看上去似乎很抽象，使用代碼描述能夠讓人容易理解，下面是一個函數遞歸的例子。
/* 遞歸求n的階乘 */
int factorial(int n) //定義一個求階乘的函數叫做factorial(),需要一個整形參數，返回一個整形值
{
if (n <= 1) //遞歸結束的條件
{
return 1;
}
else
{
return n * factorial(n - 1);//在factorial()中再次調用自身，隻不過參數由n變成n-1
}
}
在這個例子中，函數 factorial()接收到一個整形數n，如n=5，暫時稱作F(5)，這時n!=F(5)，而函數的功能如下：
判斷5是否小於或等於1，如果是，將1返回；不是，進到else執行語句返回（這裡可以將return看作等於）5× factorial(n – 1)，等價於 F(5)=5×F(4)用上面的方法計算F(4)=4×F(3)….以此類推直到達到限制條件n=1時有，F(1)=1
遞歸算法的實質：是把問題轉化為規模縮小瞭的同類問題的子問題。然後遞歸調用函數(或過程)來表示問題。
由於每個小問題處理起來都有與大問題類似的行為邏輯，因此我們可以“大事化小”，而遞歸說白瞭，就是不斷地在套娃。
但是，計算機的內存是有限的，由於每次調用函數都需要在棧區開辟一個空間，使得遞歸不能無限制地進行下去，沒有遞歸結束的條件，當操作系統為進程分配的虛擬地址空間當中的棧空間被耗盡時，會發生堆棧溢出，產生段錯誤(segmentation fault)。
因此，使用遞歸時應註意：
必須存在限制條件，當滿足這個限制條件的時候，遞歸便不再繼續每次遞歸調用之後越來越接近這個限制條件
遞歸的好處在於：
代碼簡潔在某些特定問題上求解方便
遞歸的缺點在於
消耗大量時間和空間資源——效率較低可能伴隨許多重復計算，工作量大——影響性能
2.漢諾塔問題
以下內容來自維基百科
最早發明這個問題的人是法國數學傢愛德華·盧卡斯。
傳說越南河內某間寺院有三根銀棒，上串 64 個金盤。寺院裡的僧侶依照一個古老的預言，以上述規則移動這些盤子；預言說當這些盤子移動完畢，世界就會滅亡。這個傳說叫做梵天寺之塔問題（Tower of Brahma puzzle）。但不知道是盧卡斯自創的這個傳說，還是他受他人啟發。
若傳說屬實，僧侶們需要
步才能完成這個任務；若他們每秒可完成一個盤子的移動，就需要 5849 億年才能完成。整個宇宙現在也不過 137 億年。
這個傳說有若幹變體：寺院換成修道院、僧侶換成修士等等。寺院的地點眾說紛紜，其中一說是位於越南的河內，所以被命名為“河內塔”。另外亦有“金盤是創世時所造”、“僧侶們每天移動一盤”之類的背景設定
漢諾塔基本的玩法如圖，其規則是：將圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次隻能移動一個圓盤。
當圓盤數量隻有3個的時候，求解的方法顯而易見，但當數量增多時，問題變得有些棘手起來。但不管怎麼移動，核心思想都是遞歸：
先從n塊圓盤中將最大的一塊移動到最後的柱子上接著從剩下n-1找到最大的一塊移到柱子上……
3.漢諾塔遞歸的c語言實現
C語言代碼如下：
/* 漢諾塔問題（遞歸實現） */
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void move(char, char); // 聲明一個函數move，函數定義在下方，用於表示圓盤的交換
void Towers_Of_Hanoi(int n,char a,char b,char c)
{
if (1 == n) //遞歸結束標志：當柱子上隻有一塊圓盤
{
move(a, c); //從a移動到c
}
else
Towers_Of_Hanoi(n - 1, a, c, b); //將最上面n-1個圓盤移動到b柱上
move(a, c); //將a上面最後一塊圓盤移動到c柱上
Towers_Of_Hanoi(n - 1, b, a, c); //將b柱上n-1個圓盤移動到a柱上
}
}
void move(char x, char y)
{
printf("%c-->%c\n", x, y);
}
int main()
{
int n = 0;
scanf("%d", &n);
Towers_Of_Hanoi(n, 'A', 'B', 'C');//n為A柱子上圓盤的數量，A,B,C代表三根柱子
return 0;
}
程序運行結果為：
總結
到此這篇關於C語言遞歸思想實現漢諾塔詳解的文章就介紹到這瞭,更多相關C語言漢諾塔內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！