Python Recursion

Table of Contents

Overview

In this tutorial, we will discuss Python Recursion. It’s often used to solve problems that can be broken down into simple and similar sub-problems.

Python Recursion

Let’s first understand the concept of recursion. Python Recursion is a programming concept where a function calls itself directly or indirectly.

Recursive Function

When a Python function calls itself from within its function code, it is called a recursive function. A recursive function calls itself to solve a smaller part of the problem until it reaches a base case, which is a condition under which the function stops calling itself.

The programmer must consider some points while using recursion. The key points are as follows:

Python Recursion	Description
Base Case	The base case is a condition under which the function stops calling itself. This prevents infinite loops by stopping the recursion when a condition is met.
Recursive Case	The part where the function calls itself to perform a smaller sub-task.

Example

The classic example of recursion is to compute the factorial of a number. The factorial of n (denoted as n!) is the product of all positive integers less than or equal to n.

For example,

6! = 6*5*4*3*2*1

We can compute 6! as:

6! = 6* 5!

i.e.

f(n) = n * f(n-1)

Similarly, we can compute 5! as:

5! = 5* 4!

Replacing 5! in the above equation to compute 6! as:

6! = 6*5*4!

We can repeat the same steps for further computations:

6! = 6*5*4*3!

6! = 6*5*4*3*2!

6! = 6*5*4*3*2*1!

6! = 6*5*4*3*2*1*0!

Now, we have reached the base case since 0! = 1.

6! = 6*5*4*3*2*1*1

i.e.

6! = 6*5*4*3*2*1

We can also stop the recursion at 1!

In the next section, we will compute the factorial using recursion.

Code

Let’s understand the concept of recursion with the help of an example. Python Program to compute the factorial of a number using recursion.

# This program computes the factorial of a number
# Python Tutorials - www.TestingDocs.com
# Recursive Function Definition
def factorial(n):
 'This funtion computes factorial using recursion'
 if n == 0:
 return 1 # Base case
 else:
 return n * factorial(n - 1) # Recursive case


number = input('Enter a number:=') # Prompt user for input
number = int(number) # convert to integer
result = factorial(number) # initial function call
print('Factorial of the number =', result) # Print the result

Python Recursion

When writing a Python program that calculates the factorial of a number, the function factorial(number) is called with the user’s input. Within the function definition, recursive calls are made to the factorial() function with the value of n decreasing by 1 in each recursive call. This process continues until the value of n becomes 1. At this point, the factorial() function computes the factorial by returning the values recursively.

Output

Let’s test the program with a simple test case.

Enter a number:=6
Factorial of the number = 720

Python Recursion Output

Recursion is a powerful programming tool, as the recursive code looks precise and clean when compared to code that uses loops. It’s important to ensure that each recursive call progresses toward the base case and that it is correctly defined to stop the recursion.

Recursion can simplify code and make it more readable for naturally recursive problems, like tree traversals.

—