Recursion in Data Structures

This set of vocabulary flashcards covers the fundamental concepts of recursion, including verification methods, implementation details, and specific recursive algorithms for data structures like binary search and linked lists.

Recursion

A technique that solves a problem by solving a smaller problem of the same type.

Recursive functions

Functions that call themselves within their own definition.

Factorial (recursive solution)

$n!$ is defined as $1$ if $n = 0$, and $(n-1)! \times n$ if $n > 0$.

Combinations (recursive solution)

$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$ for $1 < k < n$, with base cases $\binom{n}{1} = n$ and $\binom{n}{n} = 1$.

Iteration vs. Recursion constructs

An iterative algorithm uses a looping construct, while a recursive algorithm uses a branching structure.

Recursion efficiency

Recursive solutions are often less efficient in terms of both time and space than iterative solutions, though they can result in shorter and simpler source code.

Base case

The instance within a recursive function for which the answer is known and no further recursion is required to provide a result.

General case

The instance where the problem is expressed as a smaller version of itself through a recursive call.

Size factor

The parameter or condition used to measure the problem size, such as the number of elements remaining in a list during a recursive search.

The Base-Case Question

A step in the Three-Question Verification Method asking if there is a nonrecursive way out of the function and if the routine works correctly for this base case.

The Smaller-Caller Question

A step in the Three-Question Verification Method asking if each recursive call involve a smaller case of the original problem, leading inescapably to the base case.

The General-Case Question

A step in the Three-Question Verification Method asking if the whole function works correctly assuming that the recursive call(s) work correctly.

Recursive binary search base cases

(1) If $first > last$, return false; (2) If $item == info[midPoint]$, return true.

Activation record

A data structure stored into a run-time stack whenever a function is called, containing the return address and local variables.

Run-time stack

The stack used by the computer to store activation records and manage function calls and returns.

Recursive InsertItem base cases

(1) If the list is empty, insert the item; (2) if $item < location \rightarrow info$, insert the item as the first node in the current list.

Recursive DeleteItem base case

If $item == location \rightarrow info$, delete the node pointed to by the location.