Recursion In Python

Recursion

In programming world recursion is a fundamental concept. In most of the Python interview it could be asked. Whether you are a programmer or data scientist, everyone should know this concept. Not only search and sort algorithms are recursive, but every Python interview will include some recursion-based questions. This makes recursion a key concept to revise before any coding interview.

Here I will try to explain recursion in most possible simple way by dividing recursion in steps:

• What is recursion?
• Why we use recursion?
• Recursion in Python.
• Examples of recursion.

What is recursion?

Recursion is a concept in mathematics which we use in programming as well. Recursion is the process of defining a problem in terms of itself. This is the simplest definition of recursion.

In programming, recursion is The process in which a function calls itself directly or indirectly and the corresponding function is called as recursive function.

So conclusion is recursion is define new one by using itself.

Why we use recursion?

Most problems are solvable without recursion. So, strictly speaking, recursion usually isn’t necessary. Recursion is made for solving problems that can be broken down into smaller, repetitive problems. It is especially good for working on things that have many possible branches and are too complex for an iterative approach.

Pros :

• Faster when optimised.
• Less Code. You can write recursive code faster, and for debugging you have less code as compare than iterative code
• Declarative.
• Efficient sort and search

Cons :

• Maximum recursion depth.
• By mistake or unintentionally use recursion without base condition.
• More memory consumption.

Recursion in Python

When you call a function in Python, the interpreter creates a new local namespace, so that names defined within that function don’t collide with identical names defined elsewhere.

def recurse():
    x = 5
recurse()

when recurse()executes first time, it will create local namespace in python and 10 is assigned to x. After this recurse() call itself recursively. The second time recurse() runs, the interpreter creates a second namespace and assigns 10 to x there as well. These two instances of the name x are distinct from each another and can coexist without clashing because they are in separate namespaces.

After running recurse() , it will call itself again and again but python will show traceback because it is not possible to run it forever.

RecursionError: maximum recursion depth exceeded

Because there is limit for recursion according to your system.

In theory it will go forever running but practically nothing is truly forever because of memory limitation. Python doesn’t allow that to happen. The interpreter limits the maximum number of times a function can call itself recursively, and when it reaches that limit, it raises a RecursionError exception.

So to stop our function being run for forever, there must be a base condition.

Base case.

Base condition will help to terminate the recursion process or stop the function by calling itself again and again. There are one or more base cases that are directly solvable without the need for further recursion.

Recursive Case.

Where the desired state has not been reached and the function enters another recursive step. Each recursive call moves the solution progressively closer to a base case.

Examples of recursion

Count Down to Zero

In the above example, it will ask to user to enter the number. The base case would be when n = zero and recursion would stop there. In the recursive case, one less than the current value of n is passed as argument, and like this recursion moves closer to the base case.

Calculate factorial

The next example involves the mathematical concept of factorial. The factorial of a positive integer n, denoted as n! and calculated as:

n! = n*(n-1)*(n-2)...3*2*1

In other words, n! is the product of all integers from 1 to n, inclusive.

There can be so many examples of recursion but the question is ‘Is it really required to implement recursion?’. Because these above two code can be write with for loop as well. Second thing is execution speed. There can be significant performance differences between recursive and non-recursive solutions(iterative).

These were the one of the few simple examples of recursion.

I am listing more examples on which you can practice or learn recursion to achieve expertise. I am not explaining these examples because may be any beginner will read this article, then he or she will get confused when they see these advance examples of recursion in data structure. To make this article simple, I am just writing the name of examples.