遞歸演算法經典實例c語言

㈠ 1-100用c語言的遞歸法求和

1、首先本題的思路已經給出，要求用遞歸演算法。

2、程序源代碼如下：

#include<stdio.h>

int sum(int n);

int main()

{

int i=100;

printf("1~%d的和為： ",i);

printf("%d ",sum(100));

return 0;

}

//下面是一個遞歸求和函數

int sum(int n)

{

if (n==1)

return 1;

else

return n+sum(n-1);

}

3、程序的輸出結果如下：

㈡ C語言二叉樹遞歸演算法怎麼做

#include<stdio.h>
#include<string.h>

structtreenode{
intvalue;
treenode*left;
treenode*right;
};
typedeftreenode*BiTree;

voidvisit(treenode*node)
{
printf("%2d",node->value);
}

//結點總數
intnode(BiTreeT)
{
if(!T){
return0;
}
returnnode(T->left)+node(T->right)+1;
}

//前序
voidpreOrder(BiTreeT)
{
if(T){
visit(T);
preOrder(T->left);
preOrder(T->right);
}
}

//中序
voidinOrder(BiTreeT)
{
if(T){
inOrder(T->left);
visit(T);
inOrder(T->right);
}
}

//後序
voidpostOrder(BiTreeT)
{
if(T){
postOrder(T->left);
postOrder(T->right);
visit(T);
}
}

//葉子節點數
intleafnode(BiTreeT)
{
if(T){
if(!T->left&&!T->right)
return1;
else
leafnode(T->left)+leafnode(T->right);
}else{
return0;
}
}

intheight(BiTreeT)
{
if(T){
intlh=height(T->left);
intrh=height(T->right);
return(lh>rh?lh:rh)+1;
}else{
return0;
}
}

intmain()
{


return0;
}

㈢ 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!+2!+3!+...n!

#include<stdio.h>
float fun(int n)
{
if(n==1) return 1;//如果n=1則直接返回1
return n*fun(n-1);//否則返回n*fun(n-1),以此計算n的階乘，這條語句就是遞歸體
}
void main()
{
int i;
float sum=0;
for(i=1;i<=n;i++){
sum+=fun(i); //循環調用，用sum累計
}
printf("sum=%.2f\n",sum);
}

㈤ 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語言 函數遞歸調用的簡單例子

舉一個用遞歸調用函數求輸入非負整數的階乘的例子，如下：

//#include"stdafx.h"//Ifthevc++6.0,withthisline.
#include"stdio.h"
intfact(intn){
if(n==1||n==0)return1;
elsereturnn*fact(n-1);
}
intmain(void){
intx;
while(1){
printf("Inputx(int12>=x>=0)...
x=");
if(scanf("%d",&x),x>=0&&x<=12)//x>12時會使結果溢出
break;
printf("Error,redo:");
}
printf("%d!=%d
",x,fact(x));
return0;
}

㈦ 求用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語言折半查找之遞歸演算法

T的elem沒初始化，沒有申請內存空間。
而且Create的參數T必須要用引用傳遞，不然main中執行完Create(T,a)後，T的值不會變化 。

void Create(SSTable &T,int a[]){
int j;
T.elem=new ch[len(a)];
for(j=1;j<len(a)+1;j++)T.elem[j].key=a[j];
T.length=len(a);
}

㈨ C語言迭代與遞歸比較（舉例）

我舉個例子：

①斐波那契數列：1，1，2，3，5，8，13，21，34......

迭代：int Fib[N];
Fib[0]=1;Fib[1]=1;
for(i=2;i<N;i++)
Fib[i]=Fib[i-1]+Fib[i-2];
}
遞歸：int Fib(int n)
{ if(n==0||n==1)return 1;
else return (Fib(n-1)+Fib(n-2));
}

㈩ 關於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來顯示盤子是如何移動的