- 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:
- 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.
- 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).
The output will be:
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:
The output will be:
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.
(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.
(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.