遞歸和疊代的差別

C++程式中允許函數遞歸調用，在調用一個函數的過程中如果出現直接或間接調用該函數本身，則稱為函數的遞歸調用，這樣的函數稱為遞歸函數，例如：

int fun1()

{

        ···                //函數其它部分

        z=fun1();     //直接調用自身

        ···                //函數其它部分

}

在fun1()函數中又調用了fun1()函數，這種調用稱為直接調用，又如：

int fun2()

{

        x=fun3();

}

int fun3()

{

        y=fun2();

}

函數fun2()調用了fun3()，fun3()中又調用了fun2()，這種調用稱為間接遞歸調用。

可以看到，遞歸是一種特殊的嵌套調用，但是遞歸調用必須要是有限次的，在使用遞歸時，必須有一個明确的結束條件，該條件稱為遞歸出口，否則會進入死循環，常用的辦法是使用條件判斷，如if、while、do while等。

遞歸分為兩個階段：

（1）遞推：将原問題不斷分解為新的子問題，逐漸從未知向已知遞推，最終達到已知的條件，即遞歸結束的條件，這時遞推階段結束；

（2）回歸：從已知條件出發，按照遞推的逆過程，逐一求值回歸，最後到達遞歸的開始處，結束回歸階段，完成遞歸調用。

#include <stdio.h>

int main(void)

int fib(int n);

{

        int n,i;

        scanf("%d",&n);

        printf("%d",fib(n));

}

int fib(int n)

{

        if(0 == n)

               return 0;

        if(1 == n)

               return 1;

        if(n > 1)

               return fib(n-1)+fib(n-2);

}

上面是一個求斐波那契數列的遞歸調用例子，它引起一系列的函數調用，并有可能會有一系列的重複計算，是以遞歸算法的執行效率相對較低。

疊代：利用變量的原值推算出變量的一個新值，如果遞歸是自己調用自己的話，疊代就是A不停的調用B。

遞歸中一定存在疊代，但是疊代中不一定存在遞歸，大部分可以互相轉換，如果能用疊代盡量别用遞歸，遞歸浪費空間效率很低，并且遞歸計算量太大的話容易造成堆棧的溢出。

int funcA(int n)        //這是遞歸

{

    if(n > 1)

       return n+funcA(n-1);

    else

       return 1;

}

int funcB(int n)        //這是疊代

{

    int i,s=0;

    for(i=1;i<n;i++)

       s+=i;

    return s;

}