About recursive function

Ch1 What is recursion?

recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem.

Ch2 Example of recursion:

Matryoshka doll is one of the examples of recursion because each doll is the same except for its size and they each open and the doll inside is smaller and smaller until you get to the smallest child which does not open.

Factorial(!) can also be example of recursion as it repeats multiplying.

Ch3 Coding recursive function in different parts(in python)

1.Factorial

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

1. Make a function called factorial
2. if input number becomes 1, then print 1 because 1! = 1
3. else, print N multiplied by facotrial(input num(N)-1) to make a recursion

2.Palindrom

A palindromic number is a number that remains the same when its digits are reversed. EX) 0,1,2,3...11,22,33,44...101,121...

#function that checks if the input is palindrom or not
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))

1.Make a function called factorial

2.if the digit is less than 2, then it is palindrom because even though we reverse 1 digit number, it is still same

3.if the first digit number and the last digit number is same, then check one more time using palindrom function, if the numbers in the middle part are palindrom or not

4.if both requirements above doesn't match then print False

3.Fibonacci

Fibonacci is a number in which each number is the sum of the two preceding ones.
EX)0,1,1,2,3,5,8,13,21,34,55
Therefore, the fibonacci of 10 is '55'

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

1.make a function called fibonacci

2.if input number is 0 or 1, then print 0 or 1

3.if the requirements above doesn't match, then print fibonacci(N-1) and (N-2) for the result

4.Hanoi tower

Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1) Only one disk can be moved 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 i.e. a disk can only be moved if it is the uppermost disk on a 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
Thanks for reading this article!