• Base Case: The condition under which the recursive function stops calling itself. This is crucial to prevent infinite recursion and stack overflow errors.
• Recursive Case: The part of the function where it calls itself with a modified argument, moving towards the base case.

Copy Yourself to Do the Rest

Recursion is a powerful technique in programming where a function calls itself to solve smaller instances of the same problem. This approach is particularly useful for problems that exhibit self-similarity, meaning the problem can be broken down into smaller, similar sub-problems.

Example 1: Summing a List of Numbers

Consider the task of summing a list of numbers using recursion. Here is a step-by-step breakdown of how the recursive function recsum works:

1. Base Case: The simplest instance of the problem, where no further recursion is needed. In this case, when the index reaches the length of the list, there are no more elements to sum, so the function returns 0.
2. Recursive Case: The function performs a small part of the work (adding the current element to the sum of the remaining elements) and then calls itself with a smaller instance of the problem (the next index in the list).

def recsum(number_list, index):     if index == len(number_list):         return 0     return number_list[index] + recsum(number_list, index + 1) num_list = [4, 6, 3] print(f"The sum of the numbers in {num_list}: {recsum(num_list, 0)}")

The output will be:

The sum of the numbers in [4, 6, 3]: 13

 

Example 2: Factorial Calculation

The factorial of a non-negative integer num is the product of all positive integers less than or equal to num. The recursive definition of factorial is:

• Base Case: 0! = 1
• Recursive Case: num! = num × (num−1)!

Here is the recursive function to calculate factorial:

def factorial(num):     if num == 0:         return 1     return num * factorial(num - 1) num = 5 print(f"The factorial of {num} is {factorial(num)}")

The output will be:

The factorial of 5 is 120

 

Visualizing the Recursive Process

To better understand how recursion works, let's trace the execution of factorial(3):

• factorial(3) calls factorial(2)
• factorial(2) calls factorial(1)
• factorial(1) calls factorial(0)
• factorial(0) returns 1 (i.e., base case)
• factorial(1) returns 1 × 1 = 11
• factorial(2) returns 2 × 1 = 22
• factorial(3) returns 3 × 2 = 63

 

Example 3: Fibonacci Numbers

The Fibonacci sequence is a classic example to illustrate recursion. The sequence starts with 0 and 1, and each subsequent number is the sum of the two preceding ones.

Mathematically, it is defined as:

F(0)=0

F(1)=1

F(n)=F(n-1)+F(n-2) for n>1

• Base Cases: When n is 0, the function returns 0. When n is 1, the function returns 1.
• Recursive Case: The function returns the sum of the Fibonacci numbers of n-1 and n-2, breaking the problem into smaller sub-problems until reaching the base cases.

# This program uses recursion to print numbers from the Fibonacci series. def main():     # Display the first 10 numbers in the Fibonacci series     print("The first 10 numbers in the Fibonacci series are:")     for number in range(10):         print(fib(number)) # The fib function returns the nth number in the Fibonacci series. def fib(n):     if n == 0:         return 0 # Base case: The 0th Fibonacci number is 0     elif n == 1:         return 1 # Base case: The 1st Fibonacci number is 1     else:         return fib(n - 1) + fib(n - 2) # Recursive case: Sum of the two preceding numbers # Call the main function. if __name__ == '__main__':     main()

(Explanation)

• Main Function:

• The main function is the entry point of the program. It prints a message and then uses a for loop to print the first 10 Fibonacci numbers by calling the fib function.

• Fib Function:

• Base Cases:
  • When n is 0, the function returns 0.
  • When n is 1, the function returns 1.
• Recursive Case:
  • For any n greater than 1, the function returns the sum of fib(n-1) and fib(n-2). This is where the function calls itself with smaller values of n.

Example 4: Greatest Common Divisor (GCD)

To further illustrate recursion, let's add an example of calculating the greatest common divisor (GCD) using the Euclidean algorithm.

# This program uses recursion to find the GCD of two numbers. def main():     # Get two numbers from the user     num1 = int(input("Enter an integer: "))     num2 = int(input("Enter another integer: "))     # Display the GCD     print(f"The greatest common divisor of {num1} and {num2} is {gcd(num1, num2)}") # The gcd function returns the greatest common divisor of two numbers. def gcd(x, y):     if y == 0:         return x # Base case: If y is 0, x is the GCD     else:         return gcd(y, x % y) # Recursive case: Call gcd with (y, x % y) # Call the main function. if __name__ == '__main__':     main()

(Explanation)

• Main Function:

• • The main function prompts the user to enter two integers and then calls the gcd function to calculate and print their GCD.

• GCD Function:

• • Base Case: If y is 0, the function returns x as the GCD.
  • Recursive Case: The function calls itself with y and x % y (the remainder when x is divided by y), gradually reducing the problem size until the base case is reached.