recfib2.cpp

C++&datastructure书籍源码,以前外教提供现在与大家共享

#include <iostream>
using namespace std;
#include "tvector.h"
#include "prompt.h"

// Illustrates "bad" recursion for computing  Fibonacci numbers
// but made better using a static vector for storing values

int gFibCalls = 0;
const int FIB_LIMIT = 40;

long RecFib(int n)
// precondition: 0 <= n
// postcondition: returns the n-th Fibonacci number
{
    static tvector<int> storage(FIB_LIMIT+1,0);

    gFibCalls++;
    if (0 == n || 1 == n)
    {   return 1;
    }
    else if (storage[n] == 0)
    {   storage[n] = RecFib(n-1) + RecFib(n-2);
        return storage[n];
    }
    else
    {   return storage[n];
    }
}

int main()
{
    int num = PromptRange("compute Fibonacci #",1,FIB_LIMIT);
    cout << "Fibonacci # " << num << " = " << RecFib(num) << endl;
    cout << "total # function calls = " << gFibCalls << endl;    
    return 0;
}