Recursion Flashcards
Explain how stacks is used for recursive programs
- When function is called, a function frame containing data of the variables is allocated for the call
- The function frame is pushed to the call stack
- When the function calls itself again, a new function frame is allocated for the new call and is pushed onto the call stack.
- The active function frame is the frame on the top of the stack.
- When the function terminates, function frame is popped off and the return value is passed to the previously active function frame
- When all the last function frame terminates, the return value is outputted to the user.
What is a recursive function?
- Function which calls itself
- Function which has a base case which proceeds without any processing
- Each successive function call brings the problem closer to the base case
Advantage of recursive implementations over linear implementations
Feature: Recursion splits tasks up into multiple threads
A: Can carry out task more efficiently on computers with multi core processor
R: Recursive function able to utilise the multiple threads on the system, breaks down task into smaller sub tasks which can be executed at the same time, thus faster execution
Disadvantage of using recursive implementations over linear implementations
Feature: Recursive functions involves call stacks known as overhead
D: Could cause the system to run out of memory, causing other processes to fail and crash
R: Recursive implementations requires large overhead, as more memory is used to store the function frames pushed onto the call stack
Name an error that might be returned if recursive function requires large overhead, what’s this type of error?
Max recursion depth error
*must include word error
Type: runtime error