斐波那契数（C/C++，Scheme） -电脑资料

一、背景

    斐波那契数的定义：

    f0=0

    f1=1

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

二、分析

    我引用两张表，大家一看便懂，

斐波那契数（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>

    递归的核心在于：不断地回到起点。

    迭代的核心在于：不断地更新参数。

    在下面的代码中，递归的核心是sum的运算，sum不断的累乘，虽然运算的数值不同，但形式和意义一样。

    而迭代的核心是product和counter的不断更新。如上表中，product就是factorial的前2个参数不断的累乘更新成第一个参数；而第二个参数则是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>

四、进阶

    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>