2.2 Programming Elements and Constructs

Question 1

State what is meant by recursion.

Answer 1

Recursion involves a function that calls itself and each recursive call divides the problem into smaller subproblems until it reaches a base case which can be solved directly, then backtracks and solves the problem.

Question 2

State one advantage and disadvantage of recursive implementations.

Answer 2

Advantage: Recursive implementations allow the task to be divided among many threads.

Disadvantage: Recursive implementations have higher overhead as each function call remains in the call stack until the base case is reached.

Question 3

State 3 features of a successful recursive function.

Answer 3

A successful recursive function
1. calls itself
2. handles a base case withour further processing
3. each recursive call reduces the size of the problem and brings it closer to the base case.

Question 4

Explain the use of a stack when a recursive function executes.

Answer 4

When a recursive function is called, its memory will allocated into a frame.

With each new function call, its frame will be pushed onto the call stack and control is passed to the new frame.

When the recursive function reaches its base case, its frame will be popped from the call stack and control is passed to the frame that is at the top of the call stack.

Question 5

Describe an error that might be returned by a recursive function which calls itself too many times.

Answer 5

The recursive function might return a stack overflow error if the call stack runs out of memory and maximum recursion depth is exceeded.