Python Program to Implement Recursive Function

Introduction

Recursion is a programming technique where a function calls itself to solve smaller instances of a problem until a base condition is met. Recursive functions are particularly useful for solving problems that can be broken down into smaller, similar sub-problems, such as calculating factorials, generating Fibonacci sequences, and traversing trees.

This tutorial will guide you through creating a Python program that implements a recursive function.

Example:

• Function Name: factorial
• Function Purpose: Calculate the factorial of a given number.
• Program Output:

  Factorial of 5 is 120
  

Problem Statement

Create a Python program that:

• Defines a recursive function named factorial.
• The function takes a single argument, n.
• The function calculates the factorial of n using recursion.
• The program calls the function with a sample value to demonstrate its usage.

Solution Steps

1. Define the Recursive Function: Use the def keyword to define a function named factorial.
2. Add a Base Case: Include a base case to stop the recursion when n equals 1 or 0.
3. Implement the Recursive Case: In the recursive case, call the factorial function itself with n-1.
4. Call the Function: Call the factorial function with a sample value, such as 5.
5. Display the Result: Print the result returned by the function.

Python Program

# Python Program to Implement Recursive Function
# Author: https://www.rameshfadatare.com/

# Step 1: Define the recursive function
def factorial(n):
    # Step 2: Add a base case
    if n == 0 or n == 1:
        return 1
    # Step 3: Implement the recursive case
    else:
        return n * factorial(n - 1)

# Step 4: Call the function with a sample value
result = factorial(5)

# Step 5: Display the result
print(f"Factorial of 5 is {result}")

Explanation

Step 1: Define the Recursive Function

• The function factorial is defined using the def keyword. It takes one parameter, n, which is the number for which the factorial is calculated.

Step 2: Add a Base Case

• The base case checks if n is 0 or 1. If so, the function returns 1 because the factorial of 0 and 1 is 1. The base case is essential to stop the recursion and prevent an infinite loop.

Step 3: Implement the Recursive Case

• If n is not 0 or 1, the function calls itself with n-1. This reduces the problem size and recursively calculates the factorial until the base case is reached.

Step 4: Call the Function

• The factorial function is called with the value 5. This initiates the recursion process.

Step 5: Display the Result

• The result of the function is stored in the result variable, and the print() function is used to display the factorial of 5.

Output Example

Example Output:

Factorial of 5 is 120

Additional Examples

Example 1: Recursive Function to Calculate Fibonacci Sequence

# Recursive function to calculate Fibonacci sequence
def fibonacci(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

# Calling the function for the 7th Fibonacci number
result = fibonacci(7)
print(f"7th Fibonacci number is {result}")

Output:

7th Fibonacci number is 13

Example 2: Recursive Function to Calculate Power of a Number

# Recursive function to calculate power of a number
def power(base, exponent):
    if exponent == 0:
        return 1
    else:
        return base * power(base, exponent - 1)

# Calling the function to calculate 2 raised to the power of 3
result = power(2, 3)
print(f"2 raised to the power of 3 is {result}")

Output:

2 raised to the power of 3 is 8

Example 3: Recursive Function to Reverse a String

# Recursive function to reverse a string
def reverse_string(s):
    if len(s) == 0:
        return s
    else:
        return reverse_string(s[1:]) + s[0]

# Calling the function to reverse a string
result = reverse_string("Python")
print(f"Reversed string is {result}")

Output:

Reversed string is nohtyP

Conclusion

This Python program demonstrates how to implement a recursive function to solve a problem. Recursion is a powerful technique, especially useful for problems that can be broken down into smaller sub-problems. However, it’s important to include a base case to stop the recursion and prevent infinite loops. Understanding recursion is essential for tackling complex problems in Python and other programming languages.