Recursive algorithms

A recursive algorithm is a method where a problem is solved by referring to a smaller version of itself. The idea corresponds to recursive definitions in mathematics: we start with a base, and then follow with a recursive step, which repeats the algorithm on a simpler part of the problem.

 

 

From definition to code

When we have a recursive definition, it can often be translated directly into an algorithm. One only needs to translate:

 

• Base: when the algorithm can stop.
• Recursive step: how the problem is reduced and the algorithm calls itself.

 

 

Example: Factorial

The factorial function is defined recursively as

 

$$ \large 0! = 1 $$

$$ \large n! = n \cdot (n-1)!, \quad n \geq 1 $$

 

This can be written as an algorithm in pseudocode:

 

function factorial(n):
    if n = 0:
        return 1        // base
    else:
        return n * factorial(n - 1)   // recursive step

 

 

The algorithm stops when \( \large n = 0 \); otherwise, it calls itself with a smaller number. Finally, all calls fold back into the result.

 

 

Example: Maximum in a list

We can also define an algorithm recursively to find the largest number in a list:

 

• Base: If the list has only one element, this element is the maximum.
• Recursive step: Compare the first element with the maximum of the rest of the list.

 

 

function max(list):
    if list has length 1:
        return list[0]            // base
    else:
        m = max(rest of list)     // recursive step
        return the larger of list[0] and m

 

 

Practical example

 

If we have the list \( \large [7, 2, 9, 4] \):

max([7,2,9,4])

= larger of 7 and max([2,9,4])

= larger of 7 and larger of 2 and max([9,4])

= larger of 7 and larger of 2 and larger of 9 and max([4])

= larger of 7 and larger of 2 and larger of 9 and 4

= larger of 7 and larger of 2 and 9

= larger of 7 and 9

= 9

 

 

Summary

A recursive algorithm translates the idea behind a recursive definition into code. First, a base case is specified where the algorithm stops. Then a recursive step is described, where the algorithm calls itself on a simpler problem. This pattern recurs in many well-known algorithms, such as sorting, searching, and processing data structures.