Chapter 18 Flashcards
To have a method (directly or indirectly) call itself
Examples: Fibonacci, Factorials, Towers of Hanoi, etc
Recursive method
When a recursive method is called to solve a problem, it actually is capable of solving only the _________ case or ______ case
Simplest, base
Recursion: if the method is called with a base case, it returns a _____
Result
Recursion: if it is a complex problem, it divides the problem into ____ pieces: _________
2
1 that the method knows how to do and a piece that it does not know
Recursion: the method calls a ____ _____ to work on the smaller problem. Called a _____ call or _____ step
Fresh copy
Recursive call, recursion step
True or false
The recursive call/recursion step includes a return statement
True
Recursion step executes while the original method call is still ____ (not finished executing)
Active
For the recursion to eventually terminate, each time the method calls itself with a simpler version of the original problem, the sequence of smaller and smaller problems must _____ on a base case
Converge
Recursion: when the method recognizes the base case, it returns to the _____ ____ of the method. A sequence of returns ensues until the original method call returns the final result to the caller.
Previous copy
A recursive method may call another method, which may in turn make a call back to the recursive method
Indirect recursive call or indirect recursion
Common example or recursion on a computer
Explain the base case
File-system directory
Base case occurs when a directory is reached that does not contain any subdirectories
Either omitting the base case or writing the recursion step incorrectly so that it does not converge on the base case can cause a logic error known as _____ ________, where recursive calls are continuously made until memory is exhausted or the method-call stack overflows
Infinite recursion
