Understanding recursion

Recursion is the process of solving a problem, by reducing the problem to a smaller(or simpler) version of the same problem and keep it reducing until you reach a case where you can solve it directly. This simple case is called base case.

Factorial:

n! = n*(n-1)*(n-2)*.......*1

Base Case: If n=1 then return 1
Recursive Case: return n*(n-1)!

Python Code:

def factorial(n):
    if(n==1):
        return 1
    else:
        return n*factorial(n-1)

Towers of Hanoi:

We have 3 towers: FromTower, ToTower and SpareTower

Base case: If no of disks =1, move FromTower> ToTower
Recursive Case: Move (n-1) FromTower> SpareTower, then move 1 disk FromTower>ToTower, then move (n-1) disks SpareTower>ToTower

Python Code:

def move(from,to):
    print("Move from "+ str(from)+" to "+str(to)

def TowersofHanoi(n,from,to,spare):
    if(n==1):
        move(from,to)
    else:
        TowersofHanoi(n-1,from,spare,to)
        TowersofHanoi(1,from,to,spare)
        TowersofHanoi(n-1,spare,to,from)