Recursion V\S Iteration

Recursion V\S Iteration

1) Recursive function – is a function that is partially defined by itself whereas Iterative functions are loop based imperative repetitions of a process

2) Recursion Uses selection structure whereas Iteration uses repitation structure

3) An infinite loop occurs with iteration if the loop-continuation test never becomes false whereas infinite recursion occurs if the recursion step does not reduce the problem in a manner that converges on the base case.

4) Iteration terminates when the loop-continuation condition fails whereas recursion terminates when a base case is recognized

5) When using recursion multiple activation records are created on stack for each call when in iteration everything is done in one activation record

6) Recursion is usually slower then iteration due to overhead of maintaining stack whereas iteration does not use stack so it's faster than recursion

7) Recursion uses more memory than iteration
8) Infinite recursion can crash the system whereas infinite looping uses cpu cycles repeatedly

9) Recursion makes code smaller and iteration makes code longer.

Blog Author: Vijay Kumar

Go to: Coding Problem Solutions, Java Aptitude

Recursion Completely Explained

Recursion: 

The programming language allows you to divide your program into the functions. Using functions, your program becomes easier to understand and to debug. Also the functions can be shared among various programs. We can call a function inside a function, it is known as nesting of functions. The programming language C even allows calling a function itself. When a function calls itself then it is known as recursive function. The process of a function calling itself is known as Recursion. Here is the example to calculate the factorial of a number:

 int factorial(int a)

 {

   if (a == 1)

   return 1;

   else

    {

      a *= factorial(a-1);

      return a;

   }

 }

let a=4
4 != 1 so the if portion is skipped for now.
4*=factorial(3)
3 != 1
3*=factorial(2)
2 != 1
2*=factorial(1)
1==1 so 1 is returned
2*1=2 so 2 is returned
2*3=6 so 6 is returned
6*4=24 so 24 is returned
The function doesn't get to the 'return a' until the factorial(a-1) returns a number which doesn't happen until a==1.
Recursive functions should be avoided at all costs because they get very complex. Large numbers would consume a lot of memory to do something as simple as a factorial.

Blog Author: Vijay Kumar

Go to: Coding Problem Solutions, Java Aptitude