Page 2 - RECURSION

Recursive method for
Factorial of a number
factorial(n) Recursive Program with output
=n * factorial(n-1)
=n* (n-1) * factorial(n-2)
=n* (n-1) * (n-2) * factorial(n-3)
.
.
.
.
==n* (n-1) * (n-3) * (n-4) * ............... * factorial(1)

Conditions for implementing recursion/
Two cases of recursion

1. There must be a terminating condition for the problem which we want to solve using
recursion. The condition is called the base case(s) for the problem.
2. A recursive case or the more general case using which recursive call has to be made.
For a problem power(x, n), recursive case:
power(x, n) = x * power(x, n-1)
base cases can be:
power(x, n) = x when n = 1
power(x, n) = 1 when n = 0

Recursive Program (x to the power n)

Working of Recursion
 Whenever there is a recursive function call, status of caller function is pushed on to the stack
as long as terminating condition is not encountered.
 Stack allocation is oldest function is at the bottom of the stack.
 As soon as base case is encountered, the recursive calls which were pushed on to the stack
are removed in reverse order and executed one by one.