一、背景

    斐波那契數(shù)的定義：

    f0=0

    f1=1

    fi=fi−1+fi−2(i>1)

二、分析

    我引用兩張表，大家一看便懂，

斐波那契數(shù)（C/C++，Scheme）

    1.遞歸

<code class="hljs" lisp="">(factorial 6)(* 6 (factorial 5))(* 6 (* 5 (factorial 4)))(* 6 (* 5 (* 4 (factorial 3))))(* 6 (* 5 (* 4 (* 3 (factorial 2)))))(* 6 (* 5 (* 4 (* 3 (2 (factorial 1))))))(* 6 (* 5 (* 4 (* 3 (* 2 1)))))(* 6 (* 5 (* 4 （* 3 2))))(* 6 (* 5 (* 4 6)))(* 6 (* 5 24))(* 6 120)720</code>

    2.迭代

<code class="hljs" lisp="">(factorial 6)(factorial 1 1 6)(factorial 1 2 6)(factorial 2 3 6)(factorial 6 4 6)(factorial 24 5 6)(factorial 120 6 6)(factorial 720 7 6)720</code>

    遞歸的核心在于：不斷地回到起點。

    迭代的核心在于：不斷地更新參數(shù)。

    在下面的代碼中，遞歸的核心是sum的運算，sum不斷的累乘，雖然運算的數(shù)值不同，但形式和意義一樣。

    而迭代的核心是product和counter的不斷更新。如上表中，product就是factorial的前2個參數(shù)不斷的累乘更新成第一個參數(shù)；而第二個參數(shù)則是counter，其不斷的加1來更新自己。

    product <- counter * product

    counter < - counter + 1

三、代碼

    C語言版

<code class="hljs" perl="">#include<stdio.h>#include<stdlib.h>int factorialRecursive(int n);int factorialIteration(int product, int counter, int max_count);int main(){    int n;    printf(Enter an integer: );    scanf(%d,&n);    printf(%d,factorialRecursive(n));    printf(%d,factorialIteration(1,1,n));    return 0;}int factorialRecursive(int n){    int sum=1;    if(n==1)        sum*=1;    else        sum=n*factorialRecursive(n-1);    return sum;}int factorialIteration(int product, int counter, int max_count){    int sum=1;    if(counter>max_count)        sum*=product;    else        factorialIteration((counter*product),(counter+1),max_count);}</stdlib.h></stdio.h></code>

    C++語言版

<code class="hljs" cpp="">#include<iostream>using namespace std;int factorialRecursive(int n);int factorialIteration(int product, int counter, int max_count);int main(){    int n;    cout<<enter an="" cin="">>n;    cout<<factorialrecursive(n)<<endl; counter="" else="" int="" n="=1)" return="" sum="1;">max_count)        sum*=product;    else        factorialIteration((counter*product),(counter+1),max_count);}</factorialrecursive(n)<<endl;></enter></iostream></code>

四、進(jìn)階

    Scheme語言版

<code class="hljs" clojure="">(define (factorial n)    (if (= n 1)        1        (* n (factorial (- n 1)))))</code>

<code class="hljs" clojure="">(define (factorial n)    (fact-iter 1 1 n))(define (fact-iter product counter max-count)    (if (> counter max-count)        product        (fact-iter (* counter product)                   (+ counter 1)                   max-counter)))</code>