c遞歸演算法經典實例
演算法思想：層次遍歷目前最普遍用的就是隊列的那種方式，不是遞歸，但是用到while循環，既然題目要求用遞歸，可以用遞歸實現該while循環功能。演算法如下：
void TransLevele(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r->ch);
if (r->left != NULL)
{
InsertQueue(r->left);
}
if (r->right != NULL)
{
InsertQueue(r->right);
}
Tree *t = DeleteQueue();
TransLevele(t);
}
//測試程序，創建樹輸入例如ABD##E##C##,根左右創建的方式。
如下代碼是測試通過的。
#include "stdlib.h"
#define MAX 100
typedef int Element;
typedef struct tree
{
Element ch;
struct tree *left;
struct tree *right;
}Tree;
typedef struct queue
{
Tree *a[MAX];
int front;
int rear;
}Queue;
Queue Qu;
void Init();
int InsertQueue(Element ch);
Tree *DeleteQueue();
void CreateTree(Tree **r);
void TransLevele(Tree *r);
void PrintTree(Tree *r);
int main()
{
Tree *r=NULL;
CreateTree(&r);
PrintTree(r);
printf("\n");
TransLevele(r);
return 0;
}
void Init()
{
int i=0;
for (i=0; i<MAX; i++)
{
Qu.a[i] = NULL;
}
Qu.front = 0;
Qu.rear = 0;
}
int InsertQueue(Tree *r)
{
if ( (Qu.rear+1)%MAX == Qu.front)
{
printf("Queue full!");
return 0;
}
Qu.a[Qu.rear] = r;
Qu.rear = (Qu.rear+1)%MAX;
return 1;
}
Tree *DeleteQueue()
{
if (Qu.front == Qu.rear)
{
printf("Queue empty");
return NULL;
}
Tree *t=NULL;
t = Qu.a[Qu.front];
Qu.front = (Qu.front+1)%MAX;
return t;
}
void CreateTree(Tree **r)
{
Element ch;
ch=getchar();
if (ch=='#')
{
(*r)=NULL;
return ;
}
*r = (Tree *)malloc(sizeof(Tree));
(*r)->ch = ch;
CreateTree(&((*r)->left));
CreateTree(&((*r)->right));
}
void PrintTree(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r->ch);
PrintTree(r->left);
PrintTree(r->right);
}
void TransLevele(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r->ch);
if (r->left != NULL)
{
InsertQueue(r->left);
}
if (r->right != NULL)
{
InsertQueue(r->right);
}
Tree *t = DeleteQueue();
TransLevele(t);
}
㈡ 關於c語言遞歸調用的經典例題，求跪大神詳解 ！
這是漢諾塔吧。
原理：(總共n個盤子)
1、將第一個位置（起始位置）上的n-1個盤子移到第二個位置上，此時第一個位置只剩第n個盤子
2、將第一個位置上的最後一個盤子（第n個盤子）移到第三個位置（目標位置）上，再將第二個位置上的n-1個盤子移到第三個位置上。
你不需要曉得n-1個盤子如何從一個位置移到另一個位置，讓程序做。n-->n-1-->n-2......1，問題不斷的小化，當n=1時，直接從第一個位置移到第三個位置，再倒過來推1-->2-->3......-->n。最終問題就會被解決。
hanoi()函數就是將問題小化，使n-->1
move()函數中char x是起始位置,char y是目標位置，即x-->y.用A、B、C來顯示盤子是如何移動的
㈢ c語言算n的階乘的遞歸演算法
思路：遞歸求階乘函數，如果輸入的參數等於1則返回1，否則返回n乘以該函數下次遞歸。
參考代碼：
#include<stdio.h>
intfun(intn)
{
if(n==1||n==0)return1;//如果參數是0或者1返回1
returnn*fun(n-1);//否則返回n和下次遞歸的積
}
intmain()
{
intn;
scanf("%d",&n);
printf("%d ",fun(n));
return0;
}
/*
5
120
*/
㈣ c語言遞歸函數
首先要理解遞歸的概念，先遞後歸
開始遞
get(1) n=1不成立，執行else
get(2) n=2不成立，執行else
get(3) n=3不成立，執行else
get(4) n=4不成立，執行else
get(5) n=5不成立，執行else
get(6) n=6不成立, 執行else
get(7) n=7不成立, 執行else
get(8) n=8不成立, 執行else
get(9) n=9不成立 執行else
get(10) n=10成立，返回值1
開始歸！
get(10) num=1
get(9) get(n+1)*2+2 = 1*2+2=4 //這里說下為什麼不在遞的時候計算else呢？因為在遞的時候我們並不知道他們上一次的值，所以是沒辦法計算的，這里get(n+1)已經知道了上一次的值get(10)是1。
get(8) get(n+1)*2+2 = 4*2+2 =10
get(7) get(n+1)*2+2 = 10*2+2 = 22
get(6) get(n+1)*2+2 = 22*2+2 = 46
get(5) get(n+1)*2+2 = 46*2+2 = 94
get(4) get(n+1)*2+2 = 94*2+2 = 190
get(3) get(n+1)*2+2 = 190*2+2 = 382
get(2) get(n+1)*2+2 = 382*2+2 = 766
get(1) get(n+1)*2+2 = 766*2+2 = 1534
至此遞歸條件結束
㈤ c語言實現二叉樹的先序,中序,後序的遞歸和非遞歸演算法和層次遍歷演算法
#include<malloc.h> // malloc()等
#include<stdio.h> // 標准輸入輸出頭文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h> // atoi()，exit()
#include<math.h> // 數學函數頭文件，包括floor()，ceil()，abs()等
#define ClearBiTree DestroyBiTree // 清空二叉樹和銷毀二叉樹的操作一樣
typedef struct BiTNode
{
int data; // 結點的值
BiTNode *lchild,*rchild; // 左右孩子指針
}BiTNode,*BiTree;
int Nil=0; // 設整型以0為空
void visit(int e)
{ printf("%d ",e); // 以整型格式輸出
}
void InitBiTree(BiTree &T)
{ // 操作結果：構造空二叉樹T
T=NULL;
}
void CreateBiTree(BiTree &T)
{ // 演算法6.4：按先序次序輸入二叉樹中結點的值(可為字元型或整型，在主程中定義)，
// 構造二叉鏈表表示的二叉樹T。變數Nil表示空(子)樹。修改
int number;
scanf("%d",&number); // 輸入結點的值
if(number==Nil) // 結點的值為空
T=NULL;
else // 結點的值不為空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根結點
if(!T)
exit(OVERFLOW);
T->data=number; // 將值賦給T所指結點
CreateBiTree(T->lchild); // 遞歸構造左子樹
CreateBiTree(T->rchild); // 遞歸構造右子樹
}
}
void DestroyBiTree(BiTree &T)
{ // 初始條件：二叉樹T存在。操作結果：銷毀二叉樹T
if(T) // 非空樹
{ DestroyBiTree(T->lchild); // 遞歸銷毀左子樹，如無左子樹，則不執行任何操作
DestroyBiTree(T->rchild); // 遞歸銷毀右子樹，如無右子樹，則不執行任何操作
free(T); // 釋放根結點
T=NULL; // 空指針賦0
}
}
void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始條件：二叉樹T存在，Visit是對結點操作的應用函數。修改演算法6.1
// 操作結果：先序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次
if(T) // T不空
{ Visit(T->data); // 先訪問根結點
PreOrderTraverse(T->lchild,Visit); // 再先序遍歷左子樹
PreOrderTraverse(T->rchild,Visit); // 最後先序遍歷右子樹
}
}
void InOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始條件：二叉樹T存在，Visit是對結點操作的應用函數
// 操作結果：中序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍歷左子樹
Visit(T->data); // 再訪問根結點
InOrderTraverse(T->rchild,Visit); // 最後中序遍歷右子樹
}
}
void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始條件：二叉樹T存在，Visit是對結點操作的應用函數
// 操作結果：後序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先後序遍歷左子樹
PostOrderTraverse(T->rchild,Visit); // 再後序遍歷右子樹
Visit(T->data); // 最後訪問根結點
}
}
void main()
{
BiTree T;
InitBiTree(T); // 初始化二叉樹T
printf("按先序次序輸入二叉樹中結點的值,輸入0表示節點為空，輸入範例：1 2 0 0 3 0 0\n");
CreateBiTree(T); // 建立二叉樹T
printf("先序遞歸遍歷二叉樹：\n");
PreOrderTraverse(T,visit); // 先序遞歸遍歷二叉樹T
printf("\n中序遞歸遍歷二叉樹：\n");
InOrderTraverse(T,visit); // 中序遞歸遍歷二叉樹T
printf("\n後序遞歸遍歷二叉樹：\n");
PostOrderTraverse(T,visit); // 後序遞歸遍歷二叉樹T
}
㈥ c語言經典遞歸法演算法的疑問：（必須用遞歸演算法做出來哦） 題目請看問題補充
#include<stdio.h>
int jos(int n, int k); // n表示總共有多少人， k表示報數的第幾個數退出
int main(void)
{
int n,k,s;
printf("請輸入總人數和間隔數（中間以空格隔開）\n");
scanf("%d %d", &n, &k);
s = jos(n, k);
printf("獲勝者是：%d\n", s);
return 0;
}
int jos(int n,int k)
{// 每次運行都返回當前淘汰出來的位置
int x;
if(n==1) // 當剩下最後一個的時候他就是獲勝者
x=1;
else
{// 如果多餘一個
x=(jos(n-1,k)+k)%n; // 繼續從剩餘的這些人中進行選取獲勝（%n達到了循環的目的）（這里利用n-1時的淘汰位置加上k是下一個淘汰位置， 此時n又被減少）
if(x==0)
x=n;
}
return x;
}
/*
請輸入總人數和間隔數（中間以空格隔開）
37 5
獲勝者是：1
Press any key to continue
*/
㈦ C語言遞歸演算法
本人學c++，c的語法已經淡忘了，但是遞歸不管什麼語言都是一個原理
其實簡單一點來說就像數學裡面的數列的通項公式：
例如一個數列是2，4，6，8，10......
很容易就可以得到通項公式是a[n]=2*n n是大於0的整數
你肯定學過這個數列的另外一種表示方式就是： a[1]=2, a[n]=a[n-1]+2 n是大於1的整數
其實這就是一個遞歸的形式，只要你知道初始項的值，未知項和前幾項之間的關系就可以知道整個數列。
程序例子：比如你要得到第x項的值
普通循環：
for(int i=1; i<=n; i++)
if (i == x)
cout << 2*i; /*cout 相當於 c裡面的printf,就是輸出.*/
遞歸：
int a(int x) {
if (x = 1)
return 2; /* 第一項那肯定是2了，這個也是遞歸的終止條件！ */
else return a(x-1)+2; /* 函數自身調用自身是遞歸的一個特色 */
比如x=4,那麼用數學表示就是a(4)=a(3)+2=(a(2)+2)+2=((a(1)+2)+2)+2
其實遞歸方法最接近自然，也是最好思考的一個方法，難點就是把對象建模成遞歸形式，但是好多問題本身就是以遞歸形式出現的。
普通遞歸就是數據結構上的堆棧，先進後出。
例如上面x=4,把a(4)放入棧底，然後放入a(3),然後a(2),a(1),a(1)的值已知，出棧，a(1)=2,a(2)出棧a(2)=a(1)+2=2+2=4,a(3)出棧a(3)=a(2)+2=(a(1)+2)+2=6,a(4)出棧a(4)=a(3)+2=(a(2)+2)+2=((a(1)+2)+2)+2=8
再比如樓上的階乘例子，當n=0 或 1時,0!=1,1!=1,這個是階乘的初始值，也是遞歸的終止條件。然後我們知道n!=n*(n-1)!,當n>1時,這樣我們又有了遞歸形式，又可以以遞歸演算法設計程序了。（樓上已給出譚老的程序，我就不寫了）。
我給出一種優化的遞歸演算法---尾遞歸。
從我給出的第一演算法可以看出，先進棧再出棧，遞歸的效率是很低的。速度上完全比不上迭代（循環）。但是尾遞歸引入了一個新的函數參數，用這個新的函數參數來記錄中間值.
普通遞歸階乘fac(x),就1個x而已，尾遞歸用2個參數fac(x,y),y存放階乘值。
所以譚老的程序就變成
// zysable's tail recursive algorithm of factorial.
int fac(int x, int y) {
if (x == 1)
return y;
else return fac(x-1, y*x);}
int ff(int x) {
if (x == 0)
return 1;
else return fac(x,1);}
對於這個程序我們先看函數ff，函數ff其實是對fac的一個封裝函數，純粹是為了輸入方便設計的，通過調用ff(x)來調用fac(x,1),這里常數1就是當x=1的時候階乘值了，我通過走一遍當x=3時的值即為3!來說明一下。
首先ff(3),x!=0,執行fac(3,1).第一次調用fac，x=3,y=1,x!=1,調用fac(x-1,y*x),新的x=2,y=3*1=3,這里可以看到，y已經累計了一次階乘值了，然後x還是!=1,繼續第三次調用fac(x-1,y*x),新的x=1,y=2*3=6,然後x=1了，返回y的值是6，也就是3！.你會發現這個遞歸更類似於迭代了。事實上我們用了y記錄了普通遞歸時候，出棧的乘積，所以減少了出棧後的步驟，而且現在世界上很多程序員都在倡議用尾遞歸取消循環，因為有些在很多解釋器上尾遞歸比迭代稍微效率一點.
基本所有普通遞歸的問題都可以用尾遞歸來解決。
一個問題以遞歸來解決重要的是你能抽象出問題的遞歸公式，只要遞歸公式有了，你就可以放心大膽的在程序中使用，另外一個重點就是遞歸的終止條件；
其實這個終止條件也是包含在遞歸公式裡面的，就是初始值的定義。英文叫define initial value. 用普通遞歸的時候不要刻意讓自己去人工追蹤程序，查看運行過程，有些時候你會發現你越看越不明白，只要遞歸公式轉化成程序語言正確了，結果必然是正確的。學遞歸的初學者總是想用追蹤程序運行來讓自己來了解遞歸，結果越弄越糊塗。
如果想很清楚的了解遞歸，有種計算機語言叫scheme,完全遞歸的語言，因為沒有循環語句和賦值語句。但是國內人知道的很少，大部分知道是的lisp。
好了，就給你說到這里了，希望你能學好遞歸。
PS:遞歸不要濫用，否則程序極其無效率，要用也用尾遞歸。by 一名在美國的中國程序員zysable。
㈧ 求c語言的字元串逆序輸出的遞歸演算法
1．創建一個新的項目和。c文件，輸入頭和主要功能。
