Glossary
Base case
A condition within a recursive method that terminates the recursion, providing a direct solution for the smallest problem instance and preventing an infinite loop.
Example:
In a factorial function, the base case is when n equals 1, returning 1 directly without further recursive calls.
Binary search
An efficient search algorithm for finding an element in a sorted array by repeatedly dividing the search interval in half.
Example:
To find the number 25 in a sorted array [5, 10, 15, 20, 25, 30], binary search would first check the middle (20), then narrow the search to the upper half.
Conquer step
The phase of the merge sort algorithm where the sorted sub-arrays are merged back together in a sorted manner to produce the final sorted array.
Example:
After the divide step creates single-element arrays, the conquer step in merge sort would merge [2] and [5] to [2, 5], and [1] and [8] to [1, 8], then [2, 5] and [1, 8] to [1, 2, 5, 8].
Divide step
The initial phase of the merge sort algorithm where the unsorted array is recursively broken down into smaller sub-arrays until each sub-array contains only one element.
Example:
In merge sort, the divide step would take an array [5, 2, 8, 1] and split it into [5, 2] and [8, 1], then further into [5], [2], [8], [1].
Infinite loop
A programming error in recursion where the base case is never met, causing the function to call itself indefinitely, leading to a stack overflow error.
Example:
If a recursive function designed to count down from n forgets its base case and keeps calling count(n+1), it will result in an infinite loop.
Iteration
A programming technique that involves repeatedly executing a block of code using loops (like `for` or `while`) until a certain condition is met.
Example:
Calculating the sum of numbers from 1 to 10 using a for loop is an example of iteration, as it repeatedly adds numbers.
Merge sort
An efficient, comparison-based sorting algorithm that works by dividing an array into halves, recursively sorting each half, and then merging the sorted halves.
Example:
To sort [38, 27, 43, 3, 9, 82, 10], merge sort would split it, sort the smaller parts, and then combine them in order.
Pre-sorted
A condition where an array or list must be arranged in a specific order (e.g., ascending or descending) before a particular algorithm, like binary search, can be applied effectively.
Example:
Before performing a binary search on a list of student IDs, the list must be pre-sorted numerically for the algorithm to work correctly.
Recursion
A method of solving a problem where the solution depends on solutions to smaller instances of the same problem, involving a function calling itself.
Example:
Calculating the factorial of a number, like 5!, can be done using recursion where factorial(n) calls factorial(n-1) until it reaches the base case.
Recursive call
The statement within a recursive method where the function invokes itself with a modified, typically smaller, version of the original problem.
Example:
In factorial(n), the line return n * factorial(n-1); contains the recursive call to factorial(n-1).
Recursive methods
Functions or methods that solve a problem by calling themselves with smaller versions of the original problem until a base case is reached.
Example:
A method to calculate Fibonacci numbers, fib(n), is a recursive method because it calls fib(n-1) and fib(n-2) to build up the sequence.