2 Recursion Free Online FlashCards

What is recursion?

Recursion solves a problem by having a function call itself on a smaller or simpler version of that problem.

What is a base case?

A base case is a condition whose answer is known directly and that stops further recursive calls.

What is a recursive case?

A recursive case reduces the problem and calls the same function on a smaller instance.

What does progress mean in recursion?

Each recursive call must move closer to a base case, usually by reducing the input or advancing through a structure.

How does recursion use the call stack?

The call stack stores active function calls in last-in, first-out order, so the most recent recursive call returns first.

What is recursion depth?

Recursion depth is the maximum number of simultaneously active recursive calls. It determines the stack space used by the recursion.

What is the cost of decrease-by-one recursion?

A decrease-by-one recurrence has the form $T(n) = T(n-1) + O(1)$, giving $O(n)$ running time and typically $O(n)$ call depth.

Why is recursive binary search $O(\log n)$?

Binary search follows $T(n) = T(n/2) + O(1)$, so its running time and recursion depth are both $O(\log n)$.

Why is naive recursive Fibonacci inefficient?

Naive recursive Fibonacci recomputes the same subproblems many times, producing exponential running time. Memoization reduces the running time to $O(n)$.

What recurrence describes merge sort?

Merge sort divides the array, recursively sorts both halves, and merges them. Its recurrence is $T(n) = 2T(n/2) + O(n)$, giving $O(n \log n)$ time.

Why is binary-tree traversal $O(n)$?

A tree traversal uses the empty tree as its base case and recursively processes child subtrees. Visiting each node once gives $O(n)$ running time.

What is backtracking?

Backtracking recursively explores a choice, then undoes it before trying another choice. Pruning invalid partial solutions can reduce the search.