Recursion–Fibonacci series

Recursion is made as full fun in many English literature related things. Even search for recursion in a normal dictionary, you get like this,

Recursion

See "Recursion".

In simple terms, recursion is one which goes on-and-on expanding some thing into a bigger and infinite world. Generally, recursion leads to infinity!!

Metaphor

Recursion is a beautiful concept god has given man. It’s around us, all over us. As i said, Recursion leads to infinity. From an artistic term, recursive arts are the below clips [Source: Wikimedia]

So, recursion is a beautiful concept devised by God in everything that matters in this world. Even the universe is recursive. Circles within a circle. Spirals are recursive structures. Even light spreads in a recursive way. If you would have seen the matrix movie clearly, the anomaly created by the architect is the possibility of recursive clones of neo. This anomaly of recursive-ness even made the architect to think in a recursive way and lead neo to get infinite possibilities in a matrix world. To say simply, Matrix is always possible!

Also, check about the Golden Ratio and Fibonacci series relation. Golden ratio is called the magic ratio and its widely spread in all designs of god.

http://en.wikipedia.org/wiki/Golden_ratio

This all gives a metaphor and a warning that, Recursion is for god programmers!! And you should take great care in writing Recursive programs.

There are some programming languages called Functional programming languages. Examples: Lisp, Eel, OCaml etc. which don’t have looping or iterative statements. These languages use pure recursion to represent iterations and known for their trueness in runtime states. Now, you would think why robots use Lisp.

Concepts

In a pure mathematical sense, recursion is any process that repeats itself, that is, any formula that appears more than once in the same schema.

Let me start with the example of Fibonacci series. Its a basic interview question asked in the interviews to test your recursion as well as iteration usage in programs.

   1:  int fib(int n)

   2:  {

   3:      if(n<=1) return n;

   4:      return fib(n-1) + fib(n-2);

   5:  }

   6:   

   7:  int fib_iter(int n)

   8:  {

   9:      int f1=0; // 0

  10:      int f2=1;

  11:      int sum;

  12:      if(n<=1) return n;

  13:      for(int i=2; i<=n; i++)

  14:      {

  15:          sum = f1 + f2;

  16:          f1 = f2;

  17:          f2 = sum;

  18:   

  19:      }

  20:      return sum;

  21:  }

  22:   

  23:  void main()

  24:  {

  25:      int val = fib(15);

  26:      int val1 = fib_iter(15);

  27:  }

I remember mugging up the recursive one and forgot about how actually the Fibonacci works.

As i explained about the God’s ratio, the Golden Ratio. Fibonacci series represents this Golden ratio and it led to invention of a perfect value for it.

It just keeps on adding the numbers in the natural number series. But the important thing is the sum gets propagated. Think about the spiral whenever you think about this series. It starts with 0 and goes on like, 0 1 1 2 3 5 8 13… Negative natural line can create the same series in opposite direction. But the forward starts from 0.

Input: first number = previous sum found so far, second number = next new sum

Initial values: first number = 0, second number = 1

Iterative run: first number & second number can become > 1, but the difference will be –1 always. Since they start with 0 and 1. So, first number –1 and second number –2, represents the exact cycles of numbers to be expanded. so, the series is like 0 + 1 + (fn – r) + (fn –r-1) , where fn is the function which expands and r is a running loop upto n.

Output: (fn-1)+ (fn-2).. which means, usually the expansion of fn-1 & fn-2 will happen until u get 0+1. So, it will be like 0 + 1 + (fn-2) + (fn-3) , this fn-2, fn-3 would also have expanded when u have got 0+1. So, instead of looping with n, we loop by calling the functions.

Some simpler recursive version of summation:

   1:  int summation_iter(int n)

   2:  {

   3:      int sum=0;

   4:      for(int i=1;i<=n; i++)

   5:      {

   6:          sum = sum + i;

   7:      }

   8:      return sum;

   9:  }

  10:   

  11:  int summation(int n)

  12:  {

  13:      if(n <= 1)

  14:          return n;

  15:      else

  16:          return n + summation(n-1);

  17:   

  18:  }

  19:  void main()

  20:  {

  21:      int val = summation_iter(2);

  22:      int val1 = summation(2);

  23:  }

In the above code, note that we have only one recursive call which appends value n on each call.

Important points

• Recursion can only be designed if there is a iterative equivalent for it. Recursion is nothing but a iteration whose control lies on a condition (similar to a while loop). If you design a recursive algorithm without a iterative one, it leads to full chaos.
• We saw 2 examples of recursion: fibonacci, summation. Fibonacci requires 2 values to be stored at each iteration, first number & second number to sum up. But summation just requires one number to be stored in each iteration
• Sometimes you can see the loop invariants to find the recursion needed, in Fibonacci, first number and second number follow each other is a invariant. In summation, the value n is an invariant. If you note, there are 2 invariants, so 2 recursive calls in Fibonacci
• Note that, any loop can be converted to a recursive routine and the variant is what gets expanded while the invariant grows along with it.
• From the code, its noted that, many temporary variables are removed in a recursive routine. The temporary variables become arguments to the functions itself and are stored in the stack. So, recursive routine also has the same memory footprint in the usage of temporaries. Sometimes, its even more and unnecessary.
• Recursion is discouraged, because of the above simple reason of impossibility to optimize. Sometimes it creates unnecessary calls which lies on the stack if not designed exactly like an iterative one. Another reason is, no structural programmer will be able to design it correctly as it needs a functional programmer way of thinking. If a bug comes in a recursive procedure, it takes huge time to repair. It should be designed well at first itself.
• Recursion will be used in many algorithms from now on. Since recursive programs are easy to read. But note that, they are tough to design. Don’t mug up the recursive programs, instead try to think about non-recursive ones to understand how they design recursive ones. It requires some experience.
• Recursion is a basic method used in a divide and conquer approach. As recursion allows you to represent a big set as a single function and further it gets expanded, divide of a big set fits into this category. Conquer is usually done at the return of the each call that is expanded. Like how n+summation(n-1), split summation(n-1) until n<=1, and then combines all of it to create the final summation of all n.