05 Recursion Free Online FlashCards

What is recursion?

Recursion is a technique in which a function calls itself on a smaller or simpler version of the original problem.

What is the purpose of a base case?

The base case gives an answer directly and prevents further recursive calls.

What does a recursive case do?

The recursive case reduces the problem, calls the function on the smaller instance, and combines the returned result when necessary.

What does a recursive call add to the call stack?

Each active recursive call creates a stack frame containing parameters, local state, and a return location.

In what order do recursive calls return?

Recursive calls return in last-in, first-out order: the most recent call returns before its caller resumes.

What is factorial recursion's call-stack space?

For the recursive factorial implementation, the maximum call-stack depth is $n+1$, so its call-stack space is $O(n)$.

What is decrease-and-conquer?

Decrease-and-conquer makes one recursive call on a smaller problem, often of size $n-1$ or $n/2$.

What are binary search's recursive time and stack bounds?

Binary search has recurrence $T(n)=T(n/2)+O(1)$, giving $O(\log n)$ time and $O(\log n)$ recursive stack space.

What is the complexity of recursive tree traversal?

A recursive tree traversal processes each node once, taking $O(n)$ time and $O(h)$ stack space, where $h$ is tree height.

What is the core cycle of backtracking?

Backtracking applies a choice, recursively explores the resulting state, then undoes the choice before trying another option.

Why is naive recursive Fibonacci exponential?

Naive recursive Fibonacci takes commonly expressed exponential time, $O(2^n)$, because it repeatedly recomputes overlapping subproblems.

How does memoization improve recursive Fibonacci?

Memoization stores computed subproblem results. For Fibonacci, it reduces time to $O(n)$ and uses $O(n)$ additional storage.