Recursion - AP Computer Science A

1. State the recursive formula for calculating Fibonacci numbers.

   $F(n) = F(n-1) + F(n-2)$ with base cases $F(0)=0, F(1)=1$. Each term is the sum of the two preceding terms.

2. Which option best describes the stack overflow error in recursion?

   Occurs when recursion exceeds the stack size limit. Runtime error from excessive recursive calls.

3. Identify the recursive call in the function: int sum(int n) { if (n<=0) return 0; else return n+sum(n-1); }

   Recursive call: sum(n-1);. The line where the function invokes itself with modified parameters.

4. Which option best describes a recursive backtracking approach?

   Trying all possibilities via recursion to solve a problem. Systematic exploration with backtracking on failure.

5. What is the role of the call stack in recursion?

   Manages function calls and returns during recursion. LIFO structure tracking function call hierarchy.

6. What is the primary risk of improper recursion?

   Stack overflow due to infinite recursion. Missing base case leads to memory exhaustion.

7. Identify the base case in the function: int fact(int n) { if (n==0) return 1; else return n*fact(n-1); }

   Base case: if (n==0) return 1;. The stopping condition that prevents infinite recursion.

8. Which option best describes tail recursion?

   Recursive call is the last operation in the function. Optimization where recursion is the final operation performed.

9. What is the main advantage of recursion?

   Simplifies code for problems that have recursive structure. Elegant solution for naturally hierarchical problems.

10. Which option best describes the concept of divide and conquer?

    Breaking a problem into smaller subproblems and solving them recursively. Problem-solving strategy using recursive decomposition.

11. What is a common disadvantage of recursion?

    May lead to high memory use due to call stack. Each call adds a frame to the call stack.

12. What is the difference between recursion and iteration?

    Recursion uses self-calling functions; iteration uses loops. Recursion uses function calls; iteration uses loops.

13. What does the stack frame contain in a recursive call?

    Function's local variables, parameters, and return address. Information stored for each recursive call.

14. State the recursive formula for calculating factorial.

    $n! = n \times (n-1)!$ with base case $0! = 1$. Product of all positive integers up to $n$.

15. What is a recursive descent parser?

    A top-down parser built from a set of mutually recursive procedures. Parsing technique using recursive grammar rules.

16. What is a recursive data structure?

    A data structure defined in terms of a smaller version of itself, like linked lists. Self-referential structures like trees and linked lists.

17. Identify the base case in the function: boolean isPalindrome(String s, int start, int end) { if (start >= end) return true; else return s.charAt(start)==s.charAt(end) && isPalindrome(s, start+1, end-1); }

    Base case: if (start >= end) return true;. Condition when string indices meet or cross.

18. Find and correct the error: int fact(int n) { return n*fact(n-1); }

    Add base case: if (n==0) return 1;. Missing termination condition causes infinite recursion.

19. What is the typical reason for using recursion over iteration?

    Recursion can be more intuitive for problems with a recursive nature. Natural mapping to problem structure and readability.

20. Which option correctly describes mutual recursion?

    Two or more functions call each other. Functions form a calling cycle among themselves.

21. Identify the recursive call in the function: double power(double x, int n) { return (n==0) ? 1 : x*power(x, n-1); }

    Recursive call: power(x, n-1);. Exponentiation using recursive multiplication.

22. What is the term for the maximum depth of recursion a program can handle?

    Recursion limit or stack depth limit. System limitation preventing stack overflow errors.

23. What is a recursive algorithm?

    An algorithm that solves a problem by solving smaller instances of the same problem. Breaks problems down into smaller versions of themselves.

24. What is a recursive helper function?

    A function used to simplify recursive calls by handling initial parameters. Auxiliary function that assists the main recursive function.

25. What is the purpose of a base case in recursion?

    To stop recursion and prevent infinite loops. Essential terminating condition for recursive functions.

26. What is the importance of a well-defined base case in recursion?

    Prevents infinite recursion and stack overflow. Ensures recursion terminates properly.

27. Which type of problems are best suited for recursion?

    Problems with a naturally recursive structure, like tree traversals. Hierarchical or self-similar problem structures.

28. What is the primary challenge when debugging recursive functions?

    Understanding the call stack and flow of recursive calls. Complex execution flow makes tracing difficult.

29. What is a recursive tree?

    A visual representation of recursive function calls. Diagram showing recursive call relationships and flow.

30. Identify the error in the function: int sum(int n) { return n + sum(n-1); }

    Missing base case. No terminating condition leads to infinite recursion.

31. Identify the base case in the function: void print(int n) { if (n==0) return; else { print(n-1); System.out.println(n); } }

    Base case: if (n==0) return;. The terminating condition that stops recursion.

32. What is the term for the part of a recursive function where it calls itself?

    Recursive call. The self-referential part of recursive functions.

33. What is memoization in the context of recursion?

    Caching results of expensive function calls to avoid recalculations. Dynamic programming technique to optimize recursive algorithms.

34. Identify the base case in the function: int sumArray(int[] arr, int n) { if (n<=0) return 0; else return arr[n-1]+sumArray(arr, n-1); }

    Base case: if (n<=0) return 0;. Prevents accessing elements beyond array bounds.

35. Identify the recursive call in the function: void reversePrint(int[] arr, int n) { if (n==0) return; System.out.println(arr[n-1]); reversePrint(arr, n-1); }

    Recursive call: reversePrint(arr, n-1);. Self-call that processes remaining array elements.

36. Identify the recursive call in the function: int gcd(int a, int b) { return (b==0) ? a : gcd(b, a%b); }

    Recursive call: gcd(b, a%b);. Euclidean algorithm implementation using recursion.

37. What is the difference between direct and indirect recursion?

    Direct: function calls itself; Indirect: function calls another that calls it. Direct calls itself; indirect calls through other functions.

38. What is recursion in computer science?

    Recursion is a method where a function calls itself. Self-referential programming technique for solving complex problems.

39. What is the purpose of using a helper method in recursion?

    To manage additional parameters or initial setup. Simplifies recursive function interfaces and setup.

40. Identify the base case in the function: int fib(int n) { if (n<=1) return n; else return fib(n-1)+fib(n-2); }

    Base case: if (n<=1) return n;. Handles the terminating conditions for small inputs.

Study these flashcards