RECURSION Flashcards
(23 cards)
Can recursion be used in tree traversals
Yessssssss
Def recursion
When an algorithm calls itself from within the function, until it satisfies the base case.
examples of where recursion can be used
factorials
fibonaccccci
sorting algos
3 essential characteristics of recursion
Must have base case - when met the algorithm will stop calling itself and will start to ‘unwind’
When base case not satisfied, func must call itself
Base case must be reached after finite number of calls
Why is infinite num of calls in recursion bad
Program will never run
Items will forever be added onto the call stack
recursive vs iterative - stack overflow
recursive can cause it
iterative cant
Which is faster - iterative or recursive
iterative for less items
recursion for more
Why is iterative faster for less items
Dont have to read and write from call stack
iterative vs recursive - which is easier to follow
iterative
recursives hard to trace through
Which has less lines of code usually - iterative or recursive
recursive
When the recursive routine unwinds, how are values outputted
FILO manner
values returned reverse in order they were first calculated
eg even number 1-10:
returned as: 10, 8 ,6 ,4 ,2
Why are recursive routine outputs in FILO manner
stack operates in FILO manner
Converting iteration to recursion
make function call itself
pass values w/ parameter
set base case
check any other commands
use of the call stack in recursion
everytime subroutine is called, return address, local variables and arguments are put into call stack
recursion vs iteration - termination
recursion - defined in recursive function by base case
iteration - defined in loops definition
recursion vs iteration - size of cdoe
recursion - less
iteration - more
recursion vs iteration - the stack
recursion - requires it
iteration - doesnt
recursion vs iteration - usability
LEAVE
reursion - when size of code small and wont take long
iterative - balance speed with code size
recursion vs iteration - memory
rec - more mem
iter - less mem
recursion vs iteration - overhead
LEAVE
rec - has extended overhead
iter - none
Why do recursion require more mem
accumulation of function calls on call stack
- need to store all the local varialbes
- need to store return address
- need to store parameters
converting recursion to iteration
returns a value - doesnt call itself
change base case to while loop
put commands in the loop
review parameters
why should the recursive algo not take a very long time before base case satisfied
even w/ stop condition, recursive routine can only be called few times else stack overflow
