Learn Recursive functions in 7 mins!

Definition

Recursion means a function calls itself in its own description! Visually imagine that you are looking in a mirror in which you see another mirror, in which another one and so on!

It keeps going on and on. Using recursion we can solve many complicated problems easily.

Base Condition in Recursion

This is the final condition where the recursion should break. Otherwise we'll find ourselves in a never ending loop and our computer will run out of memory. See the code below

def factorial(n):

  """ Calculates the factorial of a number 'n'using recursion"""
  if n <= 1: # This is our base condition
     return 1

  else: 
     return n * factorial(n-1) # This is the recursive function     

When to use recursion?

See any problem repetitive in nature? Try to find the repetitiveness and solve it recursively.

For example,

1. Every tree is made up of sub tree which are also trees!
2. Mathematical series, progressions which are adding or multiplying numbers - like factorial, Arithmetic series, Geometric series
3. Traversing Graphs. Say you design an algorithm which visits all cities of a country. Visiting one city is being repeated.

Types of Recursion

1. Direct Recursion

The function calls itself in its own description.

def direct_recursion(n):
  
  """ This function calls it ownself"""
  # Base condition
  if n == 1:
      print("Thank You")

  else: 
      print("Big ")
      direct_recursion(n-1)
       

2. Indirect Recursion

A function-1 calls another function-2 which in turn calls function-1.

# Example of indirect recursion

def function1(n):

  // Base condition

    function2()


def function2():

    function1()
  

Recursive over iterative?

• Both recursive and iterative programming methods have the same problem solving powers and each can be written in others form.
• Recursive has higher space requirements than iterative
• Recursive has higher time requirements than iterative
• Recursive is simpler and cleaner to write than iterative
• In recursive functions will remain in stack until base condition is reached else we get a stack overflow

Recursive Application

Calculation of Fibonacci Series

def fibonacci(n):
  """Calculates the fibonacci sequence till n"""

  if n <= 1:
      return n

  else:
      return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(7))

Recursion is the art of breaking a large problem into smaller parts which are similar