AP CSA recursion flashcards

What is recursion?

A method where the solution to a problem depends on solutions to smaller instances of the same problem.

Base case in recursion?

The condition under which a recursive function stops calling itself.

Difference between recursion and iteration

Recursion solves problems by calling itself, while iteration uses looping constructs.

Fill in the blank: A recursive function must have a _____ case.

base

True or false: Recursion can always replace loops.

False, because recursion can lead to greater memory usage and stack overflow.

What is a recursive call?

A call to the same function within its own definition.

Example of a recursive function:

A function to calculate factorial: $\displaystyle factorial(n) = n * factorial(n-1)$.

What is infinite recursion?

Occurs when a recursive function does not reach a base case and calls itself indefinitely.

True or false: Recursive algorithms are always less efficient than iterative ones.

False, because some problems are more naturally solved with recursion.

When to use recursion?

Use recursion for problems with overlapping subproblems or when the problem size is unknown.

What is a stack overflow?

An error that occurs when the call stack pointer exceeds the stack bound, often due to deep recursion.

Difference between direct and indirect recursion

Direct recursion calls itself, while indirect recursion involves multiple functions calling each other.

Example of a simple recursive function?

Fibonacci sequence: $\displaystyle f(n) = f(n-1) + f(n-2)$.

What is tail recursion?

A type of recursion where the recursive call is the last operation in the function.

True or false: Tail recursion can be optimized by the compiler.

True, because it can be transformed into iteration to save stack space.

Fill in the blank: The time complexity of a simple recursive Fibonacci is _____

exponential, O(2^n)

What does ‘divide and conquer’ mean in recursion?

A strategy of breaking problems into smaller, manageable subproblems.

What is memoization?

A technique to store results of expensive function calls and reuse them to improve efficiency.

Difference between depth-first and breadth-first search

DFS uses a stack (recursive), while BFS uses a queue (iterative).