// fibo3.cpp
// Glenn G. Chappell
// 20 Feb 2008
//
// For CS 311 Spring 2008
// Computing Fibonacci Numbers
// Version #3: Recursive (return 2, with wrapper)


#include <iostream>
using std::cout;
using std::endl;
#include <utility>
using std::pair;


// Type ipair: pair of ints. For workshorse Fibonacci function.
typedef pair<int, int> ipair;


// fibo_recurse
// Given n, returns F(n-1), F(n) (the (n-1)th and nth Fibonacci numbers).
// F(-1) = 1. F(0) = 0. F(1) = 1. For n >= 2, F(n) = F(n-2) + F(n-1).
// Recursive.
// Pre:
//     n >= 0.
//     F(n) is a valid int value.
// Note: For 32-bit signed int's, preconditions hold for 0 <= n <= 46.
// Post:
//     Return value is pair<int, int>(F(n-1), F(n)).
// Does not throw.
ipair fibo_recurse(int n)
{

    // BASE CASE
    if (n == 0)
        return ipair(1, 0);

    // RECURSIVE CASE
    ipair prevPair = fibo_recurse(n-1);
    return ipair(prevPair.second, prevPair.first + prevPair.second);
}


// fibo
// Given n, returns F(n) (the nth Fibonacci number).
// F(0) = 0. F(1) = 1. For n >= 2, F(n) = F(n-2) + F(n-1).
// Uses fibo_recurse.
// Pre:
//     n >= 0.
//     F(n) is a valid int value.
// Note: For 32-bit signed int's, preconditions hold for 0 <= n <= 46.
// Post:
//     Return value is F(n).
// Does not throw.
int fibo(int n)
{
    return fibo_recurse(n).second;
}


int main()
{
    cout << "Fibonacci Numbers" << endl;
    cout << endl;
    for (int i = 0; i <= 46; ++i)
    {
        cout << i << ": " << fibo(i) << endl;
    }
}