QUESTION 37 · Recursion

What are the two essential parts of a terminating recursive solution?

2 marks

Answer

A base case supplies an answer without another recursive call; a recursive case reduces the problem towards that base case.

Each call must receive suitable input and make progress.
A missing or unreachable base case can cause uncontrolled calls.

Explain recursion, its base case and recursive case.

5 marks

Answer in brief

Recursion occurs when a function calls itself directly or through other functions. A useful recursive solution solves a smaller related problem and eventually reaches a base case.

Base case

The base case is a condition whose answer is known without another recursive call. In a countdown, n <= 0 can be the stopping case. In factorial, n <= 1 returns 1 for the supported non-negative inputs.

Recursive case

The recursive case calls the function with a smaller or otherwise simpler input. countdown(n - 1) moves a positive integer closer to zero. Merely writing a self-call is not enough: it must move towards termination for every supported input.

Example trace

countdown(3) prints 3 and calls countdown(2). That call prints 2 and calls countdown(1). The next call prints 1 and calls countdown(0). At zero the function returns immediately. The earlier calls then finish in reverse order. Each call has its own parameter object.

Advantages and limitations

It can express naturally recursive problems clearly, such as tree traversal and divide-and-conquer algorithms.
The base case and smaller subproblem can make the reasoning easy to state.
Active calls require execution resources; very deep recursion can exhaust the available call capacity.
Repeatedly solving the same subproblem can make a naive recursive algorithm slow.

Complexity

For a countdown from n, there are n printing calls and one base-case call. Time is O(n). With the usual model of one active call record per unfinished call, auxiliary space is O(n). C does not guarantee tail-call optimisation, so do not assume it removes the call depth.

Flowchart

Control flow for recursion with labelled true and false paths. — Explain recursion, its base case and recursive case. · Download diagram

C program and output

Download .c Open compiler

/* CodeBhavya | PPS AR25 | Learning example */
#include <stdio.h>
void countdown(int n)
{
    if (n <= 0) { return; }
    printf("%d\n", n);
    countdown(n - 1);
}
int main(void)
{
    countdown(3);
    return 0;
}

Sample input and output

This example uses values already written in the program.

Output

3
2
1