AP Computer Science Exam Question

Consider the following problem:

You are given a positive integer n. Write a recursive function recursiveSum(n: int) -> int that finds the sum of all positive integers from 1 to n, inclusive.

For example, if n = 5, the function should return 15, as 1 + 2 + 3 + 4 + 5 equals 15.

Implement the recursiveSum function and provide its step-by-step explanation of solving the problem.

def recursiveSum(n: int) -> int:
    # Base case: if n is 1, return 1
    if n == 1:
        return 1
    
    # Recursive case: add n to the sum of numbers from 1 to n-1
    return n + recursiveSum(n-1)

Explanation:

1. The function recursiveSum takes an integer n as input and returns an integer as output.
2. The base case of the recursive function is when n is equal to 1. In this case, we return 1 as the sum of integers from 1 to 1 is just 1.
3. In the recursive case, we add n to the sum of numbers from 1 to n-1 by making a recursive call to recursiveSum with n-1 as the argument. This continues until the base case is reached.
4. Finally, the function returns the sum of all numbers from 1 to n.

Let's consider an example to understand the recursion and how the function works.

Example:

print(recursiveSum(5))

Output:

15

Step-by-step calculation:

1. recursiveSum(5) calls recursiveSum(4) and waits for the result.
2. recursiveSum(4) calls recursiveSum(3) and waits for the result.
3. recursiveSum(3) calls recursiveSum(2) and waits for the result.
4. recursiveSum(2) calls recursiveSum(1) and waits for the result.
5. recursiveSum(1) reaches the base case and returns 1.
6. recursiveSum(2) receives the result of recursiveSum(1) (which is 1) and returns 2 + 1 = 3.
7. recursiveSum(3) receives the result of recursiveSum(2) (which is 3) and returns 3 + 3 = 6.
8. recursiveSum(4) receives the result of recursiveSum(3) (which is 6) and returns 4 + 6 = 10.
9. recursiveSum(5) receives the result of recursiveSum(4) (which is 10) and returns 5 + 10 = 15.

Therefore, recursiveSum(5) returns 15, showing that the function correctly calculates the sum of integers from 1 to n.