Recursion Flashcards
Define Recursion:
(Think textbook version)
The process a procedure goes through, when one of the steps of the procedure involves rerunning the entire procedure!
(A call to self!)
Stack Stores…
Methods and local variables
Why is fibonacci sooo slow if we ask it to find fib() of a high number?
Redundant calls
Heap Stores…
Data structures (like arrays/arraylists!)
Fill in the blanks:
Recursion solves _____ problems by _____ them into _____ problems of the ______________.
LARGER
REDUCING
SMALLER
SAME FORM
5 steps recursive strat:
- Make sure you understand the LARGE problem
- Find SMALLER version of the problem (just by guessing)
- Confirm the guess is actually smaller
- Determine a terminating condition
- Code!
What must coders decide between when picking to use recursion?
High performance
vs.
Good software engineering
Pros of Recursion
Nice to look at
Some solutions are just naturally recursive
- less writing can lead to better understanding
Cons of Recursion
Takes up memory + CPU time!
T or F
some problems can ONLY be solved recursively; not through iterations.
False
T or F
problems that can be solved recursively can be solved through iterations.
True
T or F
A recursive method will never terminate unless it has a return statement.
False
