9--斐波那契数列

/*
斐波那契数列

    本题主要讨论递归和循环的效率问题。
*/

#include <stdio.h>

static int i = 0;
//递归实现
int fibonacci_solution_one(int num)
{
    i++;
    if (num == 0 || num == 1)
        return 1;
    return fibonacci_solution_one(num - 1) + fibonacci_solution_one(num - 2);
}

//循环实现
int fibonacci_solution_two(int num)
{
    if (num == 0 || num == 1)
        return 1;

    i = 1;
    int p1 = 1;
    int p2 = 1;
    int temp = 0;

    for (int j = 2; j <= num; j++)
    {
        i++;
        temp = p1 + p2;
        p1 = p2;
        p2 = temp;
    }

    return temp;
}

void testOne(int num)
{
    i = 0;
    printf("fibonacci_solution_one --  %d
", fibonacci_solution_one(num));
    printf("i = %d
", i);
}

void testTwo(int num)
{
    i = 0;
    printf("fibonacci_solution_two -- %d
", fibonacci_solution_two(num));
    printf("i = %d
", i);
}

int main()
{
    testOne(0);
    testOne(1);
    testOne(2);
    testOne(20);

    testTwo(0);
    testTwo(1);
    testTwo(2);
    testTwo(20);
}