Recursion vs Iteration

For Some these two terms might heard as trivial ...but recursion solves half of the junk puzzles or most of them unless interviewer does not ask the other way probably iterative.  So this can help
the folks feel that they own these two terms and can use as per the demand. Here we go!!


As per computing , recursion is calling the function from same function itself.  so to understand this we need to know what is the function you are dealing with , what is it supposed to do ...believe me
if you dont think these ..it will bring the avalanche to your terminal. same is valid for iteration.

function is going to be a code block with some arguments , locally scoped, member, global variables, task to do and may be a return. So with these many things inside a room it's surely going to some space in the house. that's what stack and heap gonna to take care in the memory.  when there is call to the function in a running program , which will internally gets converted to CALL address at machine level, this address is going to get pointed by the SP - stack pointer..which means calling function pushes the function reference into the STACK , which is going to need some space out of the memory stack . So when there is recursive call, it adds overhead and needs space for each stack frame. This function placing in stack needs to be kept in mind as this forms the basis of problem solving. And to avoid the "avalanche with an end as stack overflow", this recursion must terminates on some condition probably the base condition for the function task.

for ex :
/*Task for the function is to find the factorial of a number */
long fact(int);

int main() {
    long res;
    int n;
    printf("Enter the number to find the factorial\n");
    scanf("%d", &n);
    if  (n < 0 )  return -1 ;
    else {
         res = fact(n);
         printf("factorial of %d is %ld" , n , res);
    }


    return 0;
}

long fact(int n) {
        /*base condition !0 = 1*/
       if (n==0)
          return 1;
      else
          return (n x fact(n-1));
}

the above program is just a trivial factorial program using recursion but from this program onward only , we should start mapping the pictorial representation of recursive function call trace in stack

lets say number is 5 ...then the call from main function will be for 5! ......now this would be first call
for the function

fact(5)->fact(4) ->fact(3) -> fact (2) -> fact(1) -> fact(0) recursive calls i.e every time from the function itself till reaches the base condition <0! = = 1>

but in stack it will lie as

SP->  fact(0)   TOP  /*last call to go to stack as the function returned 1   */
          fact(1)
          fact(2)
          fact(3)
          fact(4)
          fact(5)

and Program Counter has to return back to CALLEE executing address present in the Link Register after the execution of instruction at the CALLED address pointed by Stack Pointer.  So as per LIFO  fact(0) needs to be executed first by  POPing from stack and so on
for every function call from starting the task would be below for every function calls respectively ,
f(5)  = 5 x f(4)
f(4) = 4 x f(3)
f(3) = 3 x f(2)
f(2) = 2 x f(1)
f(1) = 1 x f(0)
f(0) = 0!   /*return 1*/

replacing the function  by its task ..like f(5) = 5 x 4 x f(3) .... so finally it will become f(5) =  5 x4 x 3 x 2 x1 x 1   which is 5!  comes after all the function called address would be POPed from STACK ...or we say its as "STACK UNWINDING" ..unwinding the stack frame one by one.

 res = fact(n)  will be returned at its original calling place  then there is printf to print the final returned value from fact(n) i.e. 5!  = 120 in above example.

Some other interesting problems which use often Recursion are:

Fibonnaci series
Merge Sort
Quick Sort
Binary Searching
Tree Traversal
Pascal's triangle
Tree Ordering
Graph
Tower of Hanoi  etc

we will discuss more problems using Recursion , more likely while dealing with above Algorithms

Iterations :

This is well know : executing the same set of instructions a given number of times until the specified result or condition met.

It should terminate when a condition met. And It does not take any extra space in memory.
Well it also does bring some sort of avalanche but I would rather say that as forever in loop increasing the operation overhead, very high CPU usage but no impact on memory.

simple example could be a for loop for finding the factorial

for (c = 1; c <= n; c++)
    result = result * c;

Now the Question comes Recursion or iteration ?
someone can say iteration for 5! does not have much in background , its simple just be in loop
till 5<=5 and keep on doing 5x4x3x2x1

but how about if we have problem like :
n! + (n/2) ! + (n/4)! + .........
 And many more ....mainly the Trees  where operation will involve both left and right  nodes



More to Compare :

Which one is effective Recursion or Iteration in Multithreading programming or platform?
How about using them in Real time programming?
Which one to prefer while writing android native framework functions?
Which one to use in Kernel programming ?
How about programming environment  with limited Stack size?