Recursion

Recursion is a technique by which a function makes one or more calls to itself during execution.

Real life Examples of Recursion are:

Programming Examples of Recursion are:

Factorial function

Product of integers from 1 to n.

1 if n=1 <= Base Case

n! = {

n X (n-1)! if n>=1 <= Recursive Case

For example: 5! = 5 X 4 X 3 X 2 X 1 = 120

Factorial is used to get the permutations of n items. That means, the number of ways in which n distinct items can be arranged into a sequence.

For example a,b,c can be arranged in 3! = 3 X 2 X 1 = 6 ways: abc, acb, bac, bca, cab, cba.

Factorial implementation in Python:

def fact(n):

if n in [0, 1]:

return 1

else:

return n * fact(n-1)

An example illustration of fact(n):

fact(5) = 5 X fact(5-1) = 5 X fact(4)

= 5 X 4 X fact(4-1) = 5 X 4 X fact(3)

= 5 X 4 X 3 X fact(3-1) = 5 X 4 X 3 X fact(2)

= 5 X 4 X 3 X 2 X fact(2-1) = 5 X 4 X 3 X 2 X fact(1)

= 5 X 4 X 3 X 2 X 1

= 120

Same representation in pictorial form:

fact(5)

fact(4)

fact(3)

fact(2)

fact(1)

return 1 <= Base Case

return 2 X 1 = 2

return 3 X 2 = 6

return 4 X 6 = 24

return 5 X 24 = 120 <= Final Value

In Python, each time a function is executed an activation record or frame is created to store information about the invocation.
The activation record includes a namespace for storing the function call's parameters and local variables.
When the function execution leads to nested function call, the former function call is suspended until the later function execution is completed or returns a value.