A road named NoNameUno

This theory says, Do the same thing again and again and expect a different results. This is my own experience when it comes to recursion. Many moons ago, I used to derive and check if a graph is recursive or not, and my thesis was to categorize different types of recursion when it comes to graph theory. Now quite often I bumped into implementation of recursive algorithm, and find myself totally confused...

 So I thought that I would discuss a bit about this recursion, and if possible induction. The approach would be to give a famous example Fibonacci sequence, tear it apart. Then the general approach to tackle recursion when it comes to implementing recursive algorithms. 

The general form of the Fibonacci sequence (Fib) is usually defined as -  Fib(n) = Fib(n- 2) + Fib(n-1) when n >= 2. And Fib(0) =0, Fib(1) = 1. The general class of these sequences are called additive sequence, and has rich structure when dealing with advanced level of Finite Mathematics.

As you can see the nature of recursion is too prime the algorithm with Fib(0) and Fib(1) then generate the sequence.  Note that there is a concept of Generating function, but that is not the immediate topic here.

For the iterative, straight forward implementation -

unsigned int Fib_n_2 = 0;

unsigned int Fob_n_1 = 1;

for ( i = 2; i <= n; i++) {

     Fib_n = Fib_n_1 + Fib_n_2;

     Fib_n_2 = Fib_n_1;

     Fib_n_1  = Fib_n;

}

The complexity is O(n).  

Straight forward recursion would be -

unsigned int rec_fib ( unsigned int  n)

{

        if ( n == 0 ) return 0;

        if ( n == 1 ) return 1;

        return (  rec_fib ( n - 1)  + rec_fib(n-2) );

}

This is again O(n). But it has more computation than the first one. You will see it if you draw the recursion tree based on the invokation. Since we are invoking two recursion, it would be a binary tree. But there is lot of redundant computation. For a better view, just draw the invocation graph for n equals, say 4 and see yourself.

Now this Fibonacci sequence is an instance of a class of sequence, usually called additive sequence. It is sometime used for linear extraplolation with history and sometime it is in the larger domain of Finite differences. An aside, Finte Difference is the analog of derivatives in continuous math. Finite difference leads to difference equation that is the discrete analog of differential equation. For our discussion, we can ignore this for now.

So for additive sequences, the first n terms could have initial value and the next term is derived by addition of the previous n terms. So two things are important (1) it is not necessary that first and second term have to be 0 and 1 (2) it does not have to be that the there is only two terms to start with. But for us, lets assume that there are only two terms to being with, just like Fibonacci sequence.

 Now the observation, for Fib(n), if we start from Fib_1 instead of FIb_0, we need to know the value of Fib_1 and and Fib_2, and we have to go only n-1 steps instead of n steps... So we have a function like the following

AddSequence ( int n, int term_0, term_1) and we could do a recrusive computation of Fib(n).

 int AddSequence( int n, int term_0, int term_1)

{

      if ( n == 0 ) return term_0;

      if ( n == 1)  return  term_1;

      return ( AddSequence ( n-1, term_1, term_0 + term_1) );

}

int Fib ( int n )

{

     return AddSequnce(n, 0, 1);

}

Now the recursion tree is really a chain, and there is no redundant computation. So it is at per with the iterative procedure given earlier. Still O(n). Now there are two observations. One is about the matrix representation of the recurrence relation. Which is as follows -

 --

|  Fib(k+2)  |                  |  1    1  |             |  F(k+1) |

|                 |          =      |            |       X    |             |

|  Fib(k+1)  |                  |   1   0  |             |   F(k)     |

where  the left side of the equation is a vector of dimenstion 2 by 1, and it is obtained by multiplying the 2 by 2 matrix on the left of the vector F(k+1), F(k).  Substituting k=0, you can see how the recurrence starts. 

Now if we start the same multiplication, we make forward progess in the sense of finding the next fibonacci number. Hence, finding Fib(n) is nothing but exponentiating the matrix to the nth power, and interpret the result appropriately.

We know that multiplication of a 2 by 2 matrix is constant time with respect to n. 

The second observation is that there is  log(n) bits to represent n in binary. So any n can be represented as a polynomial of base 2 with at most log(n) terms in that polynomial. So that will give you at most log(n) multiplications to raise the matrix to the nth power. Hence we have a O(log(n)) algorithm to produce Fib(n).

Conclusion is that if I try to solve some recursion without touching the topic for six months or longer, I always make stupid mistakes - so that is the theory of insanity.