Glossary
Base case
The condition within a recursive method that stops the recursion, providing a direct solution without further recursive calls. It prevents infinite loops.
Example:
In a recursive Fibonacci sequence calculation, the base case would be fib(0) returning 0 and fib(1) returning 1.
Call stack
A data structure that keeps track of all active function calls, including recursive ones, storing their individual parameters and local variables.
Example:
When calculating factorial(3), the call stack would hold frames for factorial(3), then factorial(2), then factorial(1), and finally factorial(0).
Iterative
A programming approach that solves a problem using loops (like `for` or `while`) to repeat a block of code until a condition is met, without a method calling itself.
Example:
Calculating the sum of numbers from 1 to n using a for loop is an iterative solution, as opposed to a recursive one.
Recursion
A programming technique where a problem is solved by breaking it down into smaller, similar subproblems, with a method calling itself repeatedly until a base case is reached.
Example:
Calculating factorial n! can use recursion, where factorial(n) calls factorial(n-1) until n is 0 or 1.
Recursive call
The statement within a recursive method where the method invokes itself, usually with different parameters, to work towards the base case.
Example:
In a method that sums numbers from 1 to n, sum(n-1) would be the recursive call that brings the problem closer to sum(0).
Recursive method
A method that solves a problem by calling itself, typically with modified parameters, until a specific base case is met.
Example:
A countDown recursive method might print numbers from n down to 1, calling countDown(n-1) in each step.
Recursive traversal
The process of visiting each element in a data structure (like an ArrayList or String) by using a recursive method, typically by processing one element and then making a recursive call for the rest.
Example:
Printing all elements of an ArrayList by printing the first element and then making a recursive traversal call on the rest of the list.