B2.4.5 Constructing and Tracing Recursive Algorithms in a Programming Language (HL only) Notes

Recursive Algorithms

1. Recursive algorithms are a fundamental concept in computer science, allowing problems to be solved by breaking them down into smaller, more manageable subproblems.
2. In this section, we will focus on constructing and tracing simple, non-branching recursive algorithms in a programming language.

Key Principles of Recursion

1. Base Case:
   1. The condition that stops the recursion.
   2. Without a base case, the recursion would continue indefinitely, leading to a stack overflow error.
2. Recursive Case:
   1. The part of the function where it calls itself with a modified argument, moving closer to the base case.

Constructing a Simple Recursive Algorithm

1. Let's start with a classic example: calculating the factorial of a number.
2. Factorial is the product of all positive integers up to a given number $n$, denoted as $n!$.

Recursive Factorial Function

Consider the mathematical definition of factorial:

$$n! = n \times (n-1)!$$

With the base case:

$$1! = 1$$

def factorial(n):
    # Base case
    if n == 1 or n == 0:
        return 1
    # Recursive case
    else:
        return n * factorial(n - 1)

# Example usage
print(factorial(5))  # Output: 120

Tracing a Recursive Algorithm

Tracing a recursive algorithm involves following the sequence of function calls and returns. Let's trace factorial(4):

1. Call: factorial(4)
   1. Recursive Case: Returns 4 * factorial(3)
2. Call: factorial(3)
   1. Recursive Case: Returns 3 * factorial(2)
3. Call: factorial(2)
   1. Recursive Case: Returns 2 * factorial(1)
4. Call: factorial(1)
   1. Base Case: Returns 1

Now, the function returns start to resolve:

1. factorial(2) returns 2 * 1 = 2
2. factorial(3) returns 3 * 2 = 6
3. factorial(4) returns 4 * 6 = 24

Constructing Another Recursive Algorithm: Sum of Natural Numbers

Let's construct a recursive function to calculate the sum of the first n natural numbers.

def sum_natural(n):
    # Base case
    if n == 1:
        return 1
    # Recursive case
    else:
        return n + sum_natural(n - 1)

# Example usage
print(sum_natural(5))  # Output: 15 (1+2+3+4+5)

Tracing the Sum of Natural Numbers

Let's trace sum_natural(4):

1. Call: sum_natural(4)
   1. Recursive Case: Returns 4 + sum_natural(3)
2. Call: sum_natural(3)
   1. Recursive Case: Returns 3 + sum_natural(2)
3. Call: sum_natural(2)
   1. Recursive Case: Returns 2 + sum_natural(1)
4. Call: sum_natural(1)
   1. Base Case: Returns 1

The function returns are resolved as follows:

1. sum_natural(2) returns 2 + 1 = 3
2. sum_natural(3) returns 3 + 3 = 6
3. sum_natural(4) returns 4 + 6 = 10