How Recursion Works: Simple Explanation

Recursion means a way of solving problem where the function calls itself. These problem could be done through iteration also.

- Performing the same operation multiple times with different input

- In every step we try smaller inputs to make the problem smaller

- Base condition is needed to stop the recursion, otherwise infinite loop will occur

Why we need Recursion?

1. Concept of recursion is really important in programming to break down bug problems into smaller ones.

   - When to use Recursion? If you can divide the problem into similar problems, then you can use recursion. The subproblems must be similar, otherwise recursion is not a choice. How to identify if the subproblems are similar in nature?

   • Design an algorithm to compute nth...

   • Write code to list the n....

   • Implement a method to compute all

   • Practice

2. The prominent usage of recursion in data structures like trees and graphs (when using trees, recursion is almost mandatory)

3. Interviews

4. Recursion is used in many algorithms (divide and conquer, greedy and dynamic programming)

How Recursion works?

First of all, we have to keep two things in mind - a condition where a method calls itself with smaller values, and second condition is an exit from infinite loop. Stack memory is used by the system for managing recursive calls (LIFO).

Syntax:

def recursionMethod(params): 
    if exit from condition satisfied: 
        return some value 
    else: 
        recursionMethod(modified params)

def recursionMethod(n): 
    if n<1: 
        print("n is less than 1") 
    else: 
        recursionMethod(n-1) 
        print(n)

An example: (Last in-First out strategy)

def firstMethod(): 
    secondMethod() 
    print("I'm the 1st method") 
def secondMethod(): 
    thirdMethod() 
    print("I'm the 2nd method") 
def thirdMethod(): 
    fourthMethod() 
    print("I'm the 3rd method") 
def fourthMethod(): 
    print("I'm the 4th method")

Recursive vs Iterative Solutions

All recursive algorithms can be implemented iteratively, although it can be more complex. We gonna look at them now

Recursive solution:

def powerOfTwo(n): 
    if n == 0: 
        return 1 
    else: 
        power = powerOfTwo(n-1)
        return power * 2

Here, we have an if condition which is meant to be an exit condition from infinite loop. Then, if the condition is not satisfied, the function calls itself recursively and return power.

Iterative solution:

def powerOfTwoIt(n): 
    i = 0
    power = 1 
    while i < n: 
        power = power * 2 
        i = i + 1 
    return power

Recursive solution is easy to write and it's simple. In recursive function, infinite recursion might lead to system crash, whereas in iterative function, infinite iteration consumes CPU cycles.

• Space efficient?

  Recursion : No Iteration: Yes

  [No stack memory requires in case of iteration]

• Time efficient?

  Recursion : No Iteration : Yes

  [In case of recursion, system needs more time for pop and push elements to stack memory which makes recursion less time efficient]

• Easy to Code?

  Recursion : Yes Iteration : No

  [ We use recursion specially in the cases we know that a problem can be divided into sub problems]

When to use/avoid Recursion?

When to use :

• When we can easily breakdown a problem into similar subproblem

• When we are fine with extra overhead (both time and space) that comes with it

• When we need a quick working solution instead of efficient one

• Traversing a tree

• When we use memoization in recursion (advance topic)

When to avoid :

• If time and space complexity matters for us

• Recursion uses more memory. If er use embedded memory, for example an application that takes more memory in the phone is not efficient

• Recursion can be slow

Write recursion in 3 steps

A recursion function calls itself repeatedly until base condition is satisfied. It could through some runtime errors, or maybe even bug. But, I'll show you how to write a recursion for any kind of problem. Let's solve a factorial problem.

Step 1 : Recursive case - the flow

We need to identify the recursive case. In our case which is a factorial function is defined using factorial functions. We know that, n! = n * (n-1)!

def factorial(n): 
    return n * factorial(n-1)
factorial(3)

Step 2: Base case - the stopping criterion

We need a base case to prevent infinity loop. We know, 0! = 1 and 1! = 1, we can use this to make our base case.

def factorial(n): 
    if n in [0,1]: 
        return 1 
    else: 
        return n * factorial(n-1)
print(factorial(3))

Step 3 : Unintentional case - the constraint

The most important thing to consider when write a recursive function is making sure that function stops for every possible argument. So, here we need to identify in which case it doesn't stop.

We have base condition for our function, which is for when n equals to zero and when equals to to one. And our recursive case calls the function itself with an argument (n-1). It is for the positive numbers. What will happen if we run our function for -1 and 1.1? We will get an error which is maximum recursion that exceeded in comparison.

def factorial(n): 
    assert n >= 0 and int(n) == n,'Number must be positive integer only'
    if n in [0,1]: 
        return 1 
    else: 
        return n * factorial(n-1)
print(factorial(-1))

By asserting, we are forcing our number to be non=negative and integer. Now our code is ready.

Hopefully, everything is clear now.

Find Fibonacci numbers using recursion

Fibonacci sequence us a sequence of numbers in which each number is the sum of the two preceding ones and the sequence starts from 0 and 1. A typical Fibonacci series looks like : 0,1,1,2,3,5,8,13,21,34,55,89.....

1st step : Recursive case - the flow

Look at the sequence and take a number from this sequence and define a recursive case. For example, 5

5 = 3+2 f(n) = f(n-1) + f(n-2) [f(n-1) points to 3, f(n-2) points to 2]

def fibonacci(n): 
    return fibonacci(n-1) + fibonacci(n-2)
fibonacci(5) #it'll go into inf loop

2nd step : Base case - stopping criterion

As the series starts from 0,1 - we can use zero and one as base case. If we reach these case, we will return them itself.

def fibonacci(n): 
    if n in [0,1]:
        return n 
    else: 
        return fibonacci(n-1) + fibonacci(n-2)
fibonacci(5)
fibonacci(0)

3rd step : Unintentional case - the constraint

The series contains all positive numbers. So we need to beware of how to handle the code if negative, non-integer numbers are given.

def fibonacci(n): 
    assert n >= 0 and int(n) == n, "Number must be positive integer"
    if n in [0,1]:
        return n 
    else: 
        return fibonacci(n-1) + fibonacci(n-2)

fibonacci(1.5)
fibonacci(-7)
fibonacci(18)

End.