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
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
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.
—
Python Tutorials
Python Tutorial on this website can be found at:
https://www.testingdocs.com/python-tutorials/
More information on Python is available at the official website: