Recursion vs. Iteration for Fibonacci

Does a function call itself? It's called recursive.

If the function is computed by a loop or repetition, the procedure is called iterative.

 

Often an iterative approach for the evaluation of a recursively defined sequence requires much less computation than a procedure using recursion.

 

Fibonacci exemplifies the difference between recursion and iteration.

 

# Fibonacci Numbers

Fibonacci numbers form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1.

 

The sequence starts 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

# Recursive Fibonacci

int test(int n)
{
    if (n > 1)
    {
        return test(n - 1) + test(n - 2);
    }
    else
    {
        return n;
    }
}

 

# Iterative Fibonacci

int test(int n)
{
    if (n > 0)
    {
        int x = 0, y = 1, z;
        for (int i = 1; i < n; i++)
        {
            z = (x + y);
            x = y;
            y = z;
        }
        return y;
    }
    return 0;
}