Recursion and Iteration Flashcards
what is the call stack
s stack maintained by the java runtime system
what does each call stack frame contain
all information necessary to execute the method eg
parameter values and local objects, return addresses etc
where are objects stored in memory
heap
every time a new method is called, what happens to the stack
a new stack frame is pushed on
every time a method returns, what happens in the stack
the topmost stack frame is popped
what is recursion
when something is defined in terms of itself
when is a method recursive
when it calls itself
how does the stack decide how much memory is needed for a method
uses largest case
why can a stack not handle infinite recursion
impossible to fix a memory amount to this
what happens when the stack recognises infinite recursion
exception thrown
how to calculate the asymptotic worst case running time of a recursive algorithm
recursive calls * cost of each call
how to calculate memory needed for a recursive algorithm
max # of active frames on call stack at the one time
what is an accumulator in recursion
a way of communicating a partial result down through the recursive call chain
what is tail recursion
needs value from the previous recursion to continue
does tail recursion use more or less stack frames
less
as every function returns, not lots of active frames at once
