Recursion

Question 1

Explain how stacks is used for recursive programs

Answer 1

1. When function is called, a function frame containing data of the variables is allocated for the call
2. The function frame is pushed to the call stack
3. When the function calls itself again, a new function frame is allocated for the new call and is pushed onto the call stack.
4. The active function frame is the frame on the top of the stack.
5. When the function terminates, function frame is popped off and the return value is passed to the previously active function frame
6. When all the last function frame terminates, the return value is outputted to the user.

Question 2

What is a recursive function?

Answer 2

1. Function which calls itself
2. Function which has a base case which proceeds without any processing
3. Each successive function call brings the problem closer to the base case

Question 3

Advantage of recursive implementations over linear implementations

Answer 3

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

Question 4

Disadvantage of using recursive implementations over linear implementations

Answer 4

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

Question 5

Name an error that might be returned if recursive function requires large overhead, what’s this type of error?

Answer 5

Max recursion depth error
*must include word error
Type: runtime error