TechVidvan

Python Recursion – A programmer’s most important weapon

Coders often joke, “In order to understand recursion, you must first understand recursion”.

Funny, right?

Well if you didn’t find it funny, scroll back up after reading this entire article on Python Recursion and we know you will like it for sure.

And if you still don’t like it, I have another one for you!

What is Python Recursion?

Recursion occurs when a function or algorithm calls itself. It is a problem-solving method that involves repetitive breaking down of a problem into a smaller instance of the same problem. We keep breaking down until we reach a problem that is small enough to be solved easily.

We usually implement recursion through a recursive function.

Let’s learn the concept of recursion using the classic example of finding factorial of a number.

Factorial of a number is the product of all integers which are greater than 1 and less than or equal to that number.

For instance, the factorial of 4 is 4 * 3 * 2 * 1.

So basically, for any non-negative integer N, the factorial of N = N * factorial of (N – 1)

Python Recursive Function

A recursive function is one that invokes itself as a part of its execution.

So if we have a function for calculating the factorial of a number, say factorial(n), based on the above discussion we can say,

factorial(n) = n * factorial(n – 1)

Cases in Python Recursive Function

  • The base case, which when satisfied, will terminate the recursive process. This is also known as the “exit condition”.
  • The recursive case, which is where the recursion will actually occur. That means this is where the function will call itself.

Finally, let’s put our recursive function for calculating the factorial of a number into code:

def factorial(n):
    # base case
    if n == 1:
        return 1

    # recursive case
    else:
        return n * factorial(n-1)

Run this code and in the Python shell call the function:

>>> factorial(10)
3628800
>>> factorial(5)
120

How does Recursion work in Python?

To get a full understanding of the working process of recursion, we first need to learn about call stack.

  • When you call a function, the system sets aside space in the memory for that function to do its work.
  • Such chunks of memory are called stack frames or function frames.
  • More than one function’s stack frame may exist in the memory at a given time.
  • We know that a function has the ability to call another function.
  • So suppose start() calls move(), which then calls direction(), all 3 functions have open frames in the memory.
  • But only the function which is called recently has an active frame.

These frames are arranged in a stack, called the ‘call stack’. The frame for the most recently called function is always on the top of the stack.

When a new function is called, a new frame is pushed onto the top of the stack and becomes the active frame. When a function finishes its work, its frame is popped off from the stack and the frame immediately below becomes the active frame. This active function picks up immediately where it left off.

When a function calls another function, the caller function is set on hold and the called function becomes active. Now the frame below this active frame has to wait until it again becomes active and resumes its work.

So recalling our factorial code, let’s understand how factorial of 5 is calculated.

Our factorial(n) function states that, if n is 1, the function returns 1. Otherwise, the function returns n * factorial(n – 1).

So if we call factorial(5) it will in turn call factorial(4), which will call factorial(3), which calls factorial(2) and at last we reach factorial(1).

The functions then pop off from the stack one by one as follows:

1. factorial(1) returns 1 to the frame of factorial(2) and pops off.

2. factorial(2) then pops off after returning 2*1 to the frame of factorial(3).

3. factorial(3) then returns 3*2*1 to the factorial(4) frame.

4. factorial(4) returns 4*3*2*1 to the frame of factorial(5)

5. And lastly, factorial(5) returns 5*4*3*2*1 which equates to 120.

Summary

That was all for Python Recursion.

In this article, our aim was to make you understand how to implement recursion in python. And now that you have also learned what actually happens behind the scenes of recursion, I hope you will get that joke we mentioned earlier in the introduction of this article.