本文實例講述了C++基于遞歸算法解決漢諾塔問題與樹的遍歷功能。分享給大家供大家參考，具體如下：

遞歸是把問題轉化為規?？s小的同類問題，然后迭代調用函數（或過程）求得問題的解。遞歸函數就是直接或間接調用自身的函數。

遞歸兩要素：遞歸關系和遞歸邊界(終止條件)，遞歸關系確定了迭代的層次結構，需要深入了解并分解問題；終止條件保證了程序的有窮性。

遞歸的應用有很多，常見的包括：階乘運算、斐波那契數列、漢諾塔、數的遍歷，還有大名鼎鼎的快排等等。理論上，遞歸問題都可以由多層循環來實現。遞歸的每次調用都會消耗一定的?？臻g，效率要稍低于循環實現，但遞歸使函數更加簡潔，極大地增加了程序的可讀性。這里介紹漢諾塔和樹的遍歷兩種應用。

漢諾塔（hanoi）

有三根相鄰的柱子，標號為A,B,C，A柱子上從下到上按金字塔狀疊放著n個不同大小的圓盤，要把所有盤子一個一個移動到柱子C上，并且每次移動同一根柱子上都不能出現大盤子在小盤子上方。

遞歸規則：先把a上的n-1個搬到b上，再把a上第n個搬到c，然后把b上的n-1個搬到c上；終止條件是n=0。

/* *作者：侯凱 *說明：目標：把n個盤子從a往c搬 */void hanoi(int n, char a,char b,char c){  if(n>0)  {    hanoi(n-1,a,c,b);    cout<<a<<"->"<<c<<endl;    hanoi(n-1,b,a,c);  }}void main(){  hanoi(4,'A','B','C');}

這樣程序便十分簡潔的實現了看似復雜的功能，下面再看一個經典的問題：

遍歷二叉樹

二叉樹的遍歷是指從根節點出發，按照某種次序依次訪問二叉樹中的所有結點，使得每個結點被訪問一次且僅被訪問一次。遍歷方法有四種：前序遍歷（先訪問根節點，然后前序遍歷左子樹，最后前序遍歷右子樹）、中序遍歷（左子樹->根節點->右子樹）、后序遍歷（左子樹->右子樹->根節點）和層序遍歷（每一層自左向右，各層自上向下訪問）。

可見前三種遍歷方法的定義就體現了遞歸的思想，算法實現如下：

//前序遍歷void PreorderTra(BiTree T){  if(T == NULL)  {    return;  }  printf("%c",T->data);//輸出結點數據，可更改為其他對結點的操作  PreorderTra(T->lchild);//前序遍歷左子樹  PreorderTra(T->rchild);//前序遍歷右子樹}//中序遍歷void InorderTra(BiTree T){  if(T == NULL)  {    return;  }  InorderTra(T->lchild);//中序遍歷左子樹  printf("%c",T->data);//輸出結點數據，可更改為其他對結點的操作  InorderTra(T->rchild);//中序遍歷右子樹}//后序遍歷void PostorderTra(BiTree T){  if(T == NULL)  {    return;  }  PostorderTra(T->lchild);//后序遍歷左子樹  PostorderTra(T->rchild);//后序遍歷右子樹  printf("%c",T->data);//輸出結點數據，可更改為其他對結點的操作}

其中二叉樹的結構如下：

typedef struct BiTNode{  ElemType data;  struct BiTNode *lchild,*rchild;}BitNode,*BiTree;

希望本文所述對大家C++程序設計有所幫助。