Recursion

Question 1

What are the features of a successful recursive function?

Answer 1

1. The function calls itself
2. The function handles a base case without any further processing
3. Each successive function call brings the problem closer to the base case

Question 2

What are the disadvantages and advantages of a recursion implementation over a linear implementation?

Answer 2

Advantage: A recursive implementation allows the task to be divided among many threads (if there are multiple calls within the function)
Disadvantage: A recursive implementation has higher overhead (due to the need to push/pop function frames from the call stack)

Question 3

What are the disadvantages and advantages of a linear implementation over a recursive implementation?

Answer 3

Advantage: A linear implementation has lower overhead
Disadvantage: A linear implementation cannot be divided among many threads

Question 4

How is a stack used in recursive calls?

Answer 4

When a function is called:
1. A function frame is allocated for the function call.
2. The function frame is pushed onto the call stack. The previously active function call is paused while the newly active function call executes.
When a function call terminates (reaches a return statement or finishes executing all statements):
3. The function frame is popped off the call stack. The return value is passed to the previously active function frame.