Key Points: Recursion

1. Recursion Basics: A method or function calls itself to solve smaller instances of the same problem.
• Base case: Condition under which recursion terminates.
• Recursive case: The function calls itself with a simplified problem.

2. Flow of Recursion:
• The recursive function reduces the size of the problem with each call.
• Each recursive call creates a new function call on the call stack.
• Once the base case is reached, the recursion unwinds by returning values from each call.

3. Stack Behavior:
• Each recursive call adds a new frame to the stack.
• When the base case is met, the frames begin to unwind and return values.

4. Common Recursion Examples:
• Factorial calculation
• Fibonacci sequence
• Tree traversal
• Binary search

5. Recursive vs Iterative:
• Some problems can be solved with both recursion and iteration, but recursion is often more intuitive for problems like tree traversal or divide-and-conquer algorithms.

Sample Code:

20 AP Style Multiple-Choice Questions (MCQs)

1. Which of the following is true about recursion?
• A. A recursive function must have a base case.
• B. Recursion does not require memory for each function call.
• C. Recursion always results in faster execution than iteration.
• D. The recursive case is where the function returns a value.

2. Which of the following is the base case in the recursive factorial method?
• A. return n * factorial(n - 1);
• B. return 1;
• C. if (n == 0)
• D. if (n > 1)

3. In a recursive function, what happens when the base case is not reached?
• A. The function terminates immediately.
• B. The function continues calling itself indefinitely.
• C. The stack memory is released.
• D. The function stops and returns the initial value.

4. What is the result of calling factorial(4) on the following function?
• A. 24
• B. 4
• C. 16
• D. 120

5. Which of the following statements is true about recursive function calls?
• A. Each recursive call replaces the previous call.
• B. Each recursive call adds a new frame to the call stack.
• C. A recursive function cannot have a base case.
• D. The base case is only checked after the recursive calls complete.

6. What is the base case in a recursive function?
• A. The function continues calling itself indefinitely.
• B. The function terminates the recursion when a specific condition is met.
• C. The function calls another function to solve the problem.
• D. The function simplifies the problem by dividing it into smaller parts.

7. What is the output of the following code snippet?
• A. 3
• B. 5
• C. 8
• D. 2

8. What happens if you forget to include a base case in a recursive function?
• A. The program will run forever or until it runs out of memory.
• B. The program will immediately terminate with an error.
• C. The recursion will stop after a fixed number of iterations.
• D. The program will produce the wrong output.

9. In the following code, what is the recursive case?
• A. if (n == 0)
• B. return 1;
• C. return x * power(x, n - 1);
• D. power(x, n - 1)

10. Which of the following is an example of a recursive function?
• A. A function that adds up elements in an array.
• B. A function that calls itself to solve a problem.
• C. A function that iterates over a list using a loop.
• D. A function that executes only once.

11. What is the primary advantage of using recursion over iteration?
• A. Recursion uses less memory.
• B. Recursion is easier to understand and implement for some problems.
• C. Recursion always performs faster than iteration.
• D. Recursion is simpler for all problems.

12. Which of the following is the best choice for problems involving divide-and-conquer strategies?
• A. Iteration
• B. Recursion
• C. Both iteration and recursion are equally efficient.
• D. Neither recursion nor iteration.

13. What is the output of the following code snippet?
• A. 3 2 1 0
• B. 3 2 1
• C. 1 2 3
• D. 0 1 2 3

14. What would happen if the following recursive function did not decrement n?
• A. The function will run forever, resulting in a stack overflow.
• B. The function will eventually terminate normally.
• C. The function will return 0.
• D. The function will return n.

15. Which of the following is the correct recursion for summing the integers from 1 to n?
• A. sum(1) = 1
• B. sum(n) = n + sum(n - 1)
• C. sum(n) = n - sum(n + 1)
• D. sum(n) = n * sum(n - 1)

16. Which data structure is commonly used to manage the function calls during recursion?
• A. Queue
• B. Stack
• C. Array
• D. Linked List

17. Which of the following best describes recursion?
• A. A function that performs the same operation multiple times.
• B. A function that calls itself to solve smaller instances of a problem.
• C. A function that runs until a condition is met.
• D. A function that does not return a result.

18. Which of the following statements is true about recursive functions?
• A. Recursive functions are always more efficient than iterative functions.
• B. Recursive functions always use less memory than iterative functions.
• C. Recursive functions can be less efficient due to the overhead of function calls.
• D. Recursive functions are never appropriate for large input sizes.

19. What would the following code output?
• A. 3
• B. 6
• C. 1
• D. 9

20. Which of the following describes the behavior of a recursive function?
• A. A recursive function always results in a runtime error.
• B. A recursive function must always call itself infinitely.
• C. A recursive function must always have a base case.
• D. A recursive function never reaches a base case.