Thinking in recursive way–Loop Invariant

“Even though, we can solve problems using recursion. It is tough to think something in a recursive way without the knowledge of functional programming”

See also

http://analgorithmaday.blogspot.in/2011/02/loop-invariant-to-prove-correctness.html
http://analgorithmaday.blogspot.com/2011/01/recursionfibonacci-series.html
Introduction
  Thinking in recursive way is little bit tough. But if you have programmed with a functional language then, there is no other way to think. :) When even loops are designed with recursion, you cover all the corner cases isn’t it? That’s the reason why robotics uses functional programming languages as it’s pure magic, fun and well defined mathematical entity rather than the program we write day-to-day.
  But why recursion is taught to be tough when it is so simple to implement and code looks so neat? The real application of recursion can only be seen in functional languages like Erlang.
Concept
  From what we have learnt about loop invariant, what is an invariant? variable is used to vary data, when does invariant used?
  In dummies way, invariant is nothing but a stack!! The data will never vary but get logged somewhere and get popped when needed. So, the data once set never changes but get logged.
In a for loop, we have looping variable which will be set once and the operation done for a single loop is constant!!.. The operation can only be the same for the next iteration without affecting what we are up to. otherwise, what we are doing in the loop is of no use. Simply this is called Loop invariant. When recursion is nothing but loops, understanding loops will give an intro to recursion. But Loops are simpler versions of recursion where usually people never think about constant inside the loop.
Example:

//Example of useless for loop with no loop invariant

for(int i=0; i<10;i++);

//Example of storing the values

// loop invariant: at any time a[i-1] will have data upto i-1

int a[20];

for(int i=0;i < 10; i++) { a[i] = i; }

In the above example, for loop incrementing “i” seems like not maintaining anything as invariant. But still we can tell the value of i at any point of time.
If the loop gets to stop in-between then, i’s value is nothing but the time when its stopped. But we don’t have the history.
Next example, array getting set to value of i. History of i is stored. At any point of time, we have data operation for each iteration.
Did you know?
Erlang is a kind of programming language where there is no concept of variables. :) Once we assign a value to the variable using assignment operator, next time it does plain comparison rather than re-assignment. Which means its a invariant variable. It’s not a constant as we see in C++. Don’t confuse with that anyway.
http://learnyousomeerlang.com/starting-out-for-real#invariable-variables