Recursion [Python]

What's Recursion?

Uses functions that call themselves from their own code

Example: Matryoshka doll

Source: Khan Academy

Matryoshka doll is one of the examples of recursion because each doll is the exact same except for the size. Each of them open and the doll inside gets smaller and smaller until you get to the smallest one which cannot open.

Also, Factorial(!) can also be an example of recursion because it repeats multiplying.

Recursive Function Coding

1. Factorial

Code:

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

2. Palindrom

Number that is the same when its digits are reversed.

Examples) 0,1,2,3...11,22,33,44...101,121...

Code to check if it's paalindromic number:

def palindrom(w):
  if len(w) < 2:
    return True
  if w[0] == w[-1]:
    return palindrom(w[1:-1])
  else:
    return False
print(palindrom(w))

3. Fibonacci

Number that each number is the sum of the two preceding ones.

Example)
Numbers: 0,1,1,2,3,5,8,13,21,34,55...
Therefore, the fibonacci of 10 is '55'

Code:

def fibonacci(N):
  if N == 0:
    return 0
  elif N == 1 :
    return 1
  else:
    return fibonacci(N-1)+fibonacci(N-2)
print(fibonacci(6))

Questions using recursion

Hanoi Tower

Mathematical puzzle where there is three rods and n disks. The objective of the puzzle is to get the entire stack to another rod, obeying these rules:

1) Only one disk can move at a time

2) Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack

3) No disk may be placed on top of a smaller disk

Code:

def TowerOfHanoi(n , x, y, z):
    if n==1:
        print ("Move disk 1 from source",x,"to destination",y)
        return
    TowerOfHanoi(n-1, x, z, y)
    print ("Move disk",n,"from source",x,"to destination",y)
    TowerOfHanoi(n-1, z, y, x)
         
# Driver code
n = 4
TowerOfHanoi(n,'A','B','C')
# A, C, B are the name of rods

Source: Geeksforgeeks