Recursive Problems

Problem as similar subproblems

In the case of a problem that can be solved by breaking it down into similar subproblems, the computation of a function is described in terms of the function itself.

Suppose we want to calculate the factorial value of $n$: $\qquad \qquad \qquad \qquad \qquad \qquad n! = n * (n - 1) * (n - 2) * (n - 3) * ... * 2 * 1$

We can write this as:

$\qquad \qquad \qquad \qquad \qquad \qquad n! = \begin{cases}1 & \text{\textbf{if} \textit{n} = 0} \\ n * (n-1)! & \text{\textbf{if} \textit{n} > 0}\end{cases}$

In terms of function, this can be written as:

$factorial(n) = \begin{cases}1 & \text{\textbf{if} \textit{n} = 0 (base case)} \\ n * factorial(n - 1) & \text{\textbf{if} \textit{n} > 0 (recursive case)}\end{cases}$

If we are to obtain the sum of digits of an integer $n$, the recursive function can be written as:

$sumdig(n) = \begin{cases}0 & \text{\textbf{if} \textit{n} = 0 (base case)} \\ n \% 10 + sumdig(n / 10) & \text{\textbf{if} \textit{n} > 0 (recursive case)}\end{cases}$

The following tips can help us understand recursive functions better:

• A fresh set of variables is born during each function call—normal calls as well as recursive calls.
• Variables created in a function die when control returns from a function.
• Recursive function may or may not have a return statement.
• Typically, many recursive calls happen during the execution of a recursive function, so several sets of variables are created. This increases the space requirement of the function.
• Recursive functions are inherently slow since passing values and control to a function and returning values and control will slow down the execution of the function.
• Recursive calls terminate when the base case condition is satisfied.

Recursive factorial function

A simple program that calculates the factorial of a given number using a recursive function is given below, followed by a brief explanation of its workings.