# 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.