AP Computer Science a Flashcards: Recursion

What this deck covers

This deck focuses on Recursion, giving you a quick way to review the definitions, rules, and examples that matter most for AP Computer Science a.

How to use these flashcards

Work through these flashcards in short sessions. Try to answer each prompt before flipping the card, then revisit any cards you miss until the explanation feels automatic.

Flashcard 1: What is the term for the part of a recursive function where it calls itself?

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

Flashcard 2: State the recursive formula for calculating Fibonacci numbers.

Answer: $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.

Flashcard 3: Which option best describes tail recursion?

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

Flashcard 4: Which option best describes the stack overflow error in recursion?

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

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

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

Flashcard 6: Which option best describes a recursive backtracking approach?

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

Flashcard 7: What is a recursive algorithm?

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

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

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

Flashcard 9: What is the purpose of using a helper method in recursion?

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

Flashcard 10: What is recursion in computer science?

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

Flashcard 11: What is the role of the call stack in recursion?

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

Flashcard 12: What is a recursive data structure?

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

Flashcard 13: What is the primary risk of improper recursion?

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

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

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

Flashcard 15: Which option best describes tail recursion?

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

Flashcard 16: State the recursive formula for calculating Fibonacci numbers.

Answer: $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.

Flashcard 17: What is a recursive helper function?

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

Flashcard 18: What is the main advantage of recursion?

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

Flashcard 19: What is the importance of a well-defined base case in recursion?

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

Flashcard 20: 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); }

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

Flashcard 21: Which option best describes the concept of divide and conquer?

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

Flashcard 22: Which option best describes a recursive backtracking approach?

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

Flashcard 23: What is a common disadvantage of recursion?

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

Flashcard 24: What is the difference between recursion and iteration?

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

Flashcard 25: What is the primary challenge when debugging recursive functions?

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

Flashcard 26: What is the purpose of a base case in recursion?

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

Flashcard 27: What does the stack frame contain in a recursive call?

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

Flashcard 28: Which option best describes the concept of divide and conquer?

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

Flashcard 29: 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); }

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

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

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

Flashcard 31: Which type of problems are best suited for recursion?

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

Flashcard 32: What is the primary risk of improper recursion?

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

Flashcard 33: State the recursive formula for calculating factorial.

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

Flashcard 34: What is a recursive descent parser?

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

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

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

Flashcard 36: What is the difference between recursion and iteration?

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

Flashcard 37: What is a recursive data structure?

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

Flashcard 38: 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); }

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

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

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

Flashcard 40: What is the typical reason for using recursion over iteration?

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

Flashcard 41: Which option best describes the stack overflow error in recursion?

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

Flashcard 42: Which option correctly describes mutual recursion?

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

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

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

Flashcard 44: What is the term for the maximum depth of recursion a program can handle?

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

Flashcard 45: What is a common disadvantage of recursion?

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

Flashcard 46: What is a recursive algorithm?

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

Flashcard 47: What is a recursive helper function?

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

Flashcard 48: What is a recursive descent parser?

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

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

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

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

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

Flashcard 51: What is the purpose of a base case in recursion?

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

Flashcard 52: What is the importance of a well-defined base case in recursion?

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

Flashcard 53: Which type of problems are best suited for recursion?

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

Flashcard 54: What does the stack frame contain in a recursive call?

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

Flashcard 55: What is the primary challenge when debugging recursive functions?

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

Flashcard 56: What is a recursive tree?

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

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

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

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

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

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

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

Flashcard 60: What is the term for the part of a recursive function where it calls itself?

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

Flashcard 61: What is the term for the maximum depth of recursion a program can handle?

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

Flashcard 62: What is a recursive tree?

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

Flashcard 63: What is memoization in the context of recursion?

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

Flashcard 64: What is the main advantage of recursion?

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

Flashcard 65: 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); }

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

Flashcard 66: Which option correctly describes mutual recursion?

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

Flashcard 67: 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); }

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

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

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

Flashcard 69: What is the typical reason for using recursion over iteration?

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

Flashcard 70: What is the difference between direct and indirect recursion?

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

Flashcard 71: What is memoization in the context of recursion?

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

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

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

Flashcard 73: What is the difference between direct and indirect recursion?

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

Flashcard 74: What is recursion in computer science?

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

Flashcard 75: What is the purpose of using a helper method in recursion?

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

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

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

Flashcard 77: 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); }

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

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

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

Flashcard 79: State the recursive formula for calculating factorial.

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

Flashcard 80: What is the role of the call stack in recursion?

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