Your Friendly Neighborhood Recursion.

What is Recursion?

To learn about Recursion let's first recall what is a function.

Python function is created using the def keyword. For example:

def func():
    print("hello world.")
func()      #function call

def func():
    print("Hello world.")
func()      #printing hello world 3 times
func()
func()

Now instead of calling the function every time we can make our job a little bit easier by using Recursion. So,

Recursion is a function that calls itself. Thats it!!

For ex. printing the first 5 natural numbers

def number(n):
    if n==6:
        return
    print(n)
    number(n+1)
number(1)

When to Use Recursion

Iterative code becomes a little bit tricky when solving complex problems. To make yourself good at programming try both iterative as well as recursive solutions. Recursion thus helps to tackle some complex problems with ease and hence convert the problem into iteration afterwards.

However, recursion is not the best way to solve a particular problem because:

They are a little slower than iterations because of function calls.
If the stack limit is too restrictive, iteration will be preferred over recursion.
They are hard to debug

How to Implement Recursion Effectively?

TRY TO BREAK THE PROBLEM INTO A SIMPLER SET OF EQUATIONS:

Try to make the problem simpler by making simple calculations and making equations out of it. for example, to print the Fibonacci numbers we add the two previous numbers so by this

$$0+1=1, 1+1=2, 2+1=3, 3+2=5, 5+3=8,$$

So the seventh Fibonacci number is 8 That is the sum of 5 and 3.

To make a simple equation in

Fib(n)=Fib(n-1)+Fib(n-2)

So recursive code for the Fibonacci number is

def fib(n):
    if n<=2:
        return n #if its less than 2 return the number
    return fib(n-1)+fib(n-2)
print(fib(5)) #output is 8

BASE CASE:

The base case is a condition to stop the recursion otherwise the recursion will keep going on.

For example, to print the first 5 natural numbers in the example above, we made a condition" if n==6:" this made the recursion stop and we got our desired output.

In another new example: Suppose we want to produce the product of the first 10 natural numbers

def recursion(n):
    if n<0 or n==1: #this is our base case 
        return 1
    else:
        return n*recursion(n-1)
print(recursion(10))

RECURSION TREE:

A recursion tree is a visualisation of what happens when recurrence is iterated.

For example the picture below of how Fibonacci problem tree looks like.

Some basic questions on recursion. [</>]

Factorial of a number.

 def recursive_factorial(n):
    if n == 1:   #base case 
        return n #to stop n from getting 0 
    else:
        return n*recursive_factorial(n-1)

The sum of first n natural numbers

 def sum_n(n):
     if n== 0:
         return 0
     else:
         return n + sum_n(n-1)
 print(sum_n(3))

Multiple of 3 (Table of 3).

 def mult3(n):
     if n == 1:
         return 3
     else:
         return mult3(n-1) + 3
 
 for i in range(1,11):
         print(mult3(i))

Conclusion

So this article is just an introduction to recursion and not much about it. The main idea is to give a basic idea of recursion and how it works.

Blogs