遞歸c語言例子,遞歸 C語言

本文目錄一覽：

• 1、講一下c語言中遞歸函數的使用方法
• 2、c語言中的遞歸
• 3、c語言 函數遞歸調用的簡單例子

講一下c語言中遞歸函數的使用方法

遞歸函數有三點要求：

1，遞歸的終止點，即遞歸函數的出口

2，不斷的遞歸調用自身

3，遞歸函數主體內容，即遞歸函數需要做的事情

ps：3一般可以放在2的前面或者後面，一般1放最前面。另外，2和3可以根據不同的需要合併，比如，有時候遞歸函數的主體就是返回調用下層函數所得到的結果。

具體例子如下：

void fun(int n)

{

   if(n=0) return;   //1 這是遞歸的終點，即出口

    fun(n-1);        //2、遞歸函數自身的調用

    coutnendl;     //3 遞歸函數的主體內容

}

2,3合併的情況

int fun(int n)

{

   if(n=0) return 0;

    return fun(n-1)+fun(n-2);  //2 3合併

}

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)!,當n1時,這樣我們又有了遞歸形式，又可以以遞歸算法設計程序了。（樓上已給出譚老的程序，我就不寫了）。

我給出一種優化的遞歸算法—尾遞歸。

從我給出的第一算法可以看出，先進棧再出棧，遞歸的效率是很低的。速度上完全比不上迭代（循環）。但是尾遞歸引入了一個新的函數參數，用這個新的函數參數來記錄中間值.

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

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

//#include “stdafx.h”//If the vc++6.0, with this line.

#include “stdio.h”

int fact(int n){

    if(n==1 || n==0) return 1;

    else return n*fact(n-1);

}

int main(void){

    int x;

    while(1){

        printf(“Input x(int 12=x=0)…\nx=”);

        if(scanf(“%d”,x),x=0  x=12)//x12時會使結果溢出

            break;

        printf(“Error,redo: “);

    }

    printf(“%d! = %d\n”,x,fact(x));

    return 0;

}