Unit 10 - Recursion

Tanav K, Sri S, Srinivas N | Period 1 ______________________________________________

Important Notes

  • AP Exam Weighting 5 - 7.5%
  • You will be tested on what recursive methods return/print
  • Some FRQ’s do have recursive solutions that can work, but you are not required to answer using recursive
  • ONLY RECURSIVE QUESTIONS ARE ON THE MULTIPLE CHOICE.
  • YOU WILL NOT BE ASKED TO WRITE RECURSIVE PROGRAMS ON FRQS!!!. ______________________________________________

What is Recursion?

Recursion is a programming technique where a function calls itself to solve smaller instances of the same problem. It continues until a base case is reached, which stops the recursive calls.

Example: Calculating factorial using recursion: 


int factorial(int n) {
    if (n == 0) return 1; // Base Case
    return n * factorial(n - 1); // Recursive Case
}

Difference Between Iterative and Recursive

rgb(145, 72, 72) #f1f1f1
Aspect Iterative Recursive
Definition Uses loops (for, while) to repeat steps. Function calls itself to solve smaller subproblems.
Memory Uses less memory, no function call overhead. Uses more memory due to call stack.
Code Often longer for complex problems. Shorter and more elegant for problems like trees, backtracking.
Risk No stack overflow. Risk of stack overflow if base case is not defined or recursion depth is too large. 

class Main {
    public static void main(String[] args) {
        // Call the factorial function and print the result for n = 5
        int result = factorial(5);
        System.out.println("Facto #f9f9f9+ result);
    }
    /**
     * Recursive function to calculate the factorial of a number.
     * @param n the number for which the factorial is calculated
     * @return factorial of n
     */
    public static int factorial(int n) {
        // Base Case: If n == 0, the factorial is 1 (this stops the recursion).
        if (n == 0) {
            return 1;
        }

        // Recursive Case: Factorial of n = n * factorial(n-1).
        return n * factorial(n - 1);
    }
}

Problem: Sum of Digits

Write a recursive function sumOfDigits that takes an integer and returns the sum of its digits.

Example:

  • Input: 1234
  • Output: 10 (because 1 + 2 + 3 + 4 = 10)

Code


public class RecursionTraceExample {
    public static void main(String[] args) {
        int number = 1234;
        System.out.println("Sum of digits of " + number + ": " + sumOfDigits(number));
    }

    /**
     * Recursive method to calculate the sum of digits of a number.
     * @param n The number whose digits are to be summed.
     * @return The sum of the digits of n.
     */
    public static int sumOfDigits(int n) {
        // Base Case: If n is a single digit, return n
        if (n < 10) {
            return n;
        }

        // Recursive Case: Add the last digit to the sum of the rest of the digits
        return (n % 10) + sumOfDigits(n / 10);
    }
}

How to Trace the Recursion for sumOfDigits(1234)

  1. Initial Call:
    sumOfDigits(1234) → (1234 % 10) + sumOfDigits(1234 / 10)
    4 + sumOfDigits(123 #f9f9f9lation paused. </li>
  2. Next Call:
    sumOfDigits(123) → (123 % 10) + sumOfDigits(123 / 10)
    3 + sumOfDigits(12) → Calculation paused.
  3. Next Call:
    sumOfDigits(12) → (12 % 10) + sumOfDigits(12 / 10)
    2 + sumOfDigits(1) → Calculation paused.
  4. Base Case:
    sumOfDigits(1) → Since 1 < 10, return 1.
  5. Unwinding the Stack:
    sumOfDigits(12) → 2 + 1 = 3
    sumOfDigits(123) → 3 + 3 = 6
    sumOfDigits(1234) → 4 + 6 = 10.
    6. </ol>

    Visualization of Recursive Calls (Stack)

    Call Stack (Top to Bottom) Value Returned
    sumOfDigits(1234) 10
    sumOfDigits(123) 6
    sumOfDigits(12) 3
    sumOfDigits(1) 1

    Question 1

    Consider the following method:

    
public int sum(int n)
{
    if (n == 0)
        return 0;
    else
        return n + sum(n - 1);
}
 #f1f1f1

    What will be returned by the call sum(4)?

    1. 4
    2. 6
    3. 10
    4. 15
    5. 20

    Answer: C. 10

    Explanation:

    • The method calculates the sum of all integers from n down to 0 recursively.
    • Recursive breakdown:
      • sum(4) = 4 + sum(3)
      • sum(3) = 3 + sum(2)
      • sum(2) = 2 + sum(1)
      • sum(1) = 1 + sum(0)
      • sum(0) = 0 (base case)
    • Adding them together:
      • sum(1) = 1
      • sum(2) = 2 + 1 = 3
      • sum(3) = 3 + 3 = 6
      • sum(4) = 4 #f9f9f9/li> </ul> </li> </ul>

        Question 2

        Consider the following method:

        
public int multiply(int a, int b)
{
    if (b == 0)
        return 0;
    else
        return a + multiply(a, b - 1);
}

        What will be returned by the call multiply(3, 4)?

        1. 7
        2. 9
        3. 12
        4. 15
        5. 20

        Answer: C. 12

        Explanation:

        • The method recursively multiplies a and b using repeated addition.
        • Recursive breakdown:
          • multiply(3, 4) = 3 + multiply(3, 3)
          • multiply(3, 3) = 3 + multiply(3, 2)
          • multiply(3, 2) = 3 + multiply(3, 1)
          • multiply(3, 1) = 3 + multiply(3, 0)
          • multiply(3, 0) = 0 (base case)
        • Adding them together:
          • multiply(3, 1) = 3
          • multiply(3, 2) = 3 + 3 = 6
          • multiply(3, 3) = 3 + 6 = 9
          • multiply(3, 4) = 3 + 9 = 12