Recursion

Simple recursive functions

The notion of recursion

Example: the factorial function, defined in mathematics by

Justification: the computation always ends (with $0!$), so the definition is well founded.

In Caml

Let us translate it directly:

let fact n =
  if n = 0 then 1
  else n * fact (n - 1) ;;

What is the problem? Why?

Static scope and recursive definitions

• In mathematics, you cannot talk about an entity before having given its definition. The same is true in Caml.
• For any occurrence of a name, it is enough to look at the text of the program that comes before to find the binding that defined it. This binding is either a definition (let) or a function parameter.

let x = 1 ;;
let x = x + 1 ;;

In the second line, the x on the right refers to the x defined before, whose value is 1. Likewise, in let f x = x + 1, the x in the body refers to the parameter.

The let rec construct

That is where the trouble was: we were using fact before having defined it. When we write let f = …, an occurrence of f on the right-hand side does not refer to the f being defined, but to a previous definition of f, if there is one. Here, there was none.

So a plain let construct cannot define a recursive function. We use let rec:

let rec fact n =
  if n = 0 then 1
  else n * fact (n - 1) ;;
fact 3 ;;
fact 10 ;;

Simulation: how does it work?

Let us unfold fact 3:

Each call waits for the result of the next one to do its multiplication. The multiplications are only done on the way back, once the case fact 0 has been reached.

The essentials

Definitions

Rules to remember

What happens if we forget the stopping case of the factorial function?

let rec fact_sans_arret n = n * fact_sans_arret (n - 1) ;;
fact_sans_arret 3 ;;

Without a stopping case, the function cannot stop: it does not terminate. This is called infinite recursion. Each pending call takes up a little memory (the stack), and the program eventually runs out of it.

The stopping case is not enough. Let us call the correct fact on a negative number:

fact (-1) ;;

From $-1$, we go to $-2$, $-3$…: we move away from 0 instead of getting closer to it.

For fact, negative numbers should be rejected, for example with if n < 0 then invalid_arg "fact".

General shape of a recursive function

Writing a recursive function will very often follow this pattern:

let rec f x =
  if condition_arret then
    expression_arret
  else
    expression_avec_un_appel_recursif

Pattern matching can of course be used instead of the conditional.

Forwards and backwards

Writing in Caml a function whose mathematical definition is inductive is almost immediate: it is a mere translation. Let us now look at slightly different problems.

The countdown example

We want a function that displays the numbers in decreasing order down to 1, starting from a given limit: for 5, we want to see 5 4 3 2 1 on the screen.

How do we solve this problem recursively? We must find an equivalent of the inductive definition: express the problem in terms of the same problem, on “smaller” data.

How to go about it

1. First, the precise specification of the problem: display in decreasing order the integers between 1 and $n$.
2. Next, the recurrence equation, in terms of “known” problems. Displaying in decreasing order the integers between 1 and $n$ means:
3. displaying $n$;
4. then displaying in decreasing order the integers between 1 and $n - 1$.
5. Finally, the stopping case, without which the definition would not be complete: displaying in decreasing order the integers between 1 and 0 means doing nothing!

The function

let rec countdown n =
  if n = 0 then ()
  else begin
    print_int n ; print_string " " ;
    countdown (n - 1)
  end ;;
countdown 5 ;;

The only difficulty is to consider the problem as already solved for smaller data, so as to be able to use it in the expression of the solution, and thus solve it!

And the other way round?

In countdown, we display the integer, then make the recursive call. What happens if we first make the recursive call, before displaying $n$?

let rec count n =
  if n = 0 then ()
  else begin
    count (n - 1) ;
    print_int n ; print_string " "
  end ;;

What do you think will happen with the call count 5?

count 5 ;;

Why?

Let us unfold count 3: to display 3, count 2 must first finish, which must first finish count 1, which must first finish count 0 (which does nothing). Then count 1 displays 1 and finishes, count 2 displays 2, and finally count 3 displays 3.

Several recursive calls

Functions with several calls

The Fibonacci sequence is defined by:

Its translation into Caml has two recursive calls:

let rec fibo n =
  if n <= 1 then 1
  else fibo (n - 1) + fibo (n - 2) ;;
fibo 10 ;;

Nested calls

The Ackermann function is another example of a function with several calls. It is defined by:

Here, a recursive call is used as an argument of another one:

let rec ackermann m n =
  if m = 0 then n + 1
  else if n = 0 then ackermann (m - 1) 1
  else ackermann (m - 1) (ackermann m (n - 1)) ;;
ackermann 2 3 ;;
ackermann 3 3 ;;

This function always terminates, but it grows extraordinarily fast: $A(4, 2)$ has almost 20,000 digits.

Mutual recursion

Parity can be defined as follows:

• 0 is even;
• $n$ is even if $n - 1$ is odd.

In the same way:

• 0 is not odd;
• $n$ is odd if $n - 1$ is even.

What will the trouble be?

let rec pair n = if n = 0 then true else impair (n - 1) ;;

pair (even) uses impair (odd), which uses pair: neither can be defined before the other. We define them together, with let rec … and …:

let rec pair n = if n = 0 then true else impair (n - 1)
and impair n = if n = 0 then false else pair (n - 1) ;;
pair 10 ;;
impair 7 ;;

Going further

Efficiency

Writing a function that “works” is not necessarily enough to solve a problem: it must also be done efficiently. Finding an efficient solution to a problem means finding a fast algorithm. But how do we evaluate the running time of a function?

A little complexity

• We determine the number of operations performed as a function of the size of the data.
• We could count tests, additions, subtractions… or simply count the recursive calls: the measure obtained is the same, up to a constant factor.

For example, for the sum of the integers from 1 to $n$:

let rec somme n = if n = 0 then 0 else n + somme (n - 1) ;;
somme 100 ;;

How many calls to compute somme n? One per value of $n$, $n - 1$, …, 0: $n + 1$ calls. The complexity is linear in $n$.

Order of magnitude

Whether the complexity is $n$ or $n + 1$ does not matter; but $n$ or $n^2$ does! The usual orders of magnitude, from fastest to slowest:

1. $1$: constant;
2. $\log n$: logarithmic;
3. $n$: linear;
4. $n \log n$;
5. $n^2$: quadratic;
6. $n^a$: polynomial;
7. $2^n$, $e^n$: exponential.

Moreover, complexity often depends on the data themselves, not only on their size. We distinguish best-case, worst-case and average complexity.

A classic example: computing a power

Let us compare

let rec power x n =
  if n = 0 then 1
  else x * power x (n - 1) ;;

and

let rec fast_power x n =
  if n = 0 then 1
  else fast_power (x * x) (n / 2) * (if n mod 2 = 0 then 1 else x) ;;
power 2 10 ;;
fast_power 2 10 ;;

The second relies on $x^{2k} = (x^2)^k$ and $x^{2k+1} = (x^2)^k \times x$.

How many calls in each case? power x n makes $n + 1$ calls: linear complexity. fast_power x n divides $n$ by 2 at each call: for $n = 10$, the calls are made with $n = 10, 5, 2, 1, 0$, that is 5 calls. In general, about $\log_2 n$ calls: logarithmic complexity. For $n = 1\,000\,000$, that is 21 calls instead of a million.

Several calls: Fibonacci

Computing the complexity of a function that has only one recursive call does not seem hard. What about functions with several calls?

let rec fibo = function
  | 0 | 1 -> 1
  | n -> fibo (n - 1) + fibo (n - 2) ;;

Let us draw the call tree of fibo 4: fibo 4 calls fibo 3 and fibo 2; fibo 3 calls fibo 2 and fibo 1; each fibo 2 calls fibo 1 and fibo 0. That is 9 calls, and fibo 2 is computed twice.

Let $R_n$ be the number of calls to fibo needed to compute fibo n. We have $R_0 = R_1 = 1$ and $R_n = 1 + R_{n-1} + R_{n-2}$; one shows by induction that $R_n = 2 \times \mathit{fibo}(n) - 1$. Now $\mathit{fibo}(n)$ grows exponentially (roughly $1.618^n$): the complexity is exponential. fibo 40 requires more than 300 million calls.

Can we do better?

How would you compute fibo 10 by hand? Nobody draws the call tree. You write the sequence in order: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. Each term is the sum of the two previous ones, which you have just written.

That is the idea: look at the problem “the other way round”.

• Rather than computing the term of rank $n$ from the two previous ones, we compute the term of rank 2, then the following ones.
• We only need to keep the last two terms computed to compute the new one.
• We also need to know which rank we are at: a parameter $i$ will serve as a counter, increased at each call, and we stop as soon as it equals $n$.
• The two other parameters of the recursive function are the current term (at rank $i$) and the previous term.

Fibonacci, in linear time!

let fibo n =
  if n < 0 then
    failwith "fibo : rang négatif !"
  else
    let rec fib i fi fi_1 =
      if i >= n then fi
      else fib (i + 1) (fi + fi_1) fi
    in
    fib 1 1 1 ;;
fibo 10 ;;
fibo 80 ;;

fib makes at most $n$ calls: the complexity is linear. fibo 80 is immediate, whereas the previous version would not have finished any time soon.

A classic: the towers of Hanoi

At the end of the 19th century, the French mathematician Édouard Lucas (1883) made up the following legend: “In the great temple of Benares, beneath the dome that marks the centre of the world, rests a copper base fitted with three vertical diamond needles, 50 cm high. At the creation, God threaded 64 plates of pure gold onto one of the needles, the largest at the bottom and the others smaller and smaller. This is the tower of Brahma. The monks must continually move the discs so that they end up in the same configuration on another needle. Brahma's rule is simple: only one disc at a time, and never a larger plate on a smaller one. When this is achieved, the world will crumble to dust and disappear.”

The aim of the game is to move all the discs from the “source” peg to another peg (the “destination”), using the “intermediate” peg, and following these rules:

• only one disc can be moved at a time;
• a disc that lies under another one cannot be moved;
• a disc cannot be placed on a smaller disc.

What is the minimum number of moves needed to move a stack of $n$ discs?

The solution

Method:

• problem: move $n$ discs, from the source peg to the destination peg;
• base case: moving 0 discs means doing nothing;
• hypothesis: we know how to “move $n - 1$ discs from peg $i$ to peg $j$”;
• recurrence equation: to move $n$ discs from the source peg to the destination peg, it is enough to:
• move $n - 1$ discs from the source peg to the intermédiaire peg;
• move 1 disc (the largest) from the source peg to the destination peg;
• move $n - 1$ discs from the intermédiaire peg to the destination peg.

The implementation

The function hanoi has 3 parameters:

• n: the number of discs;
• source: the number of the starting peg;
• destination: the number of the target peg.

We also need to know the intermediate peg: it is 6 - source - destination, since $1 + 2 + 3 = 6$!

let rec hanoi n source destination =
  if n > 0 then begin
    let intermediaire = 6 - source - destination in
    hanoi (n - 1) source intermediaire ;
    print_int source ; print_string " -> " ; print_int destination ;
    print_newline () ;
    hanoi (n - 1) intermediaire destination
  end ;;
hanoi 3 1 3 ;;

For 3 discs, 7 moves. If $D_n$ is the number of moves for $n$ discs, $D_0 = 0$ and $D_n = 2D_{n-1} + 1$, hence $D_n = 2^n - 1$. And we cannot do better: to move the largest disc, the $n - 1$ others must all be on the intermediate peg.

For the 64 discs of the legend, $2^{64} - 1 \approx 1.8 \times 10^{19}$ moves: at one move per second, almost 600 billion years. The world still has a little time.

Undecidability of termination

Alan Turing proved in 1936 that it is impossible to write a program that tests whether a function finishes its computation. Whether a computation halts is undecidable. We will show it with a little story.

Once upon a time…

An algorithmics teacher is fed up with his students' Caml functions that never stop. Each time, they force him into complicated manoeuvres to stop these programs. Then he sees the following advertisement in a specialist magazine:

…and then…

Impressed by the advertisement, the teacher pays a fortune for this little marvel, and thinks that his teaching life will at last be peaceful.

A student, however, points out that he does not understand the purchase, and shows him the following function:

let termine f = (* contents patented by the seller *) ;;

let rec absurde () =
  if termine absurde then absurde ()
  else () ;;

Does absurde terminate?

• If termine absurde answers true, then absurde () calls itself forever: it does not terminate. termine was wrong.
• If termine absurde answers false, then absurde () returns () immediately: it terminates. termine was wrong again.

In both cases, termine gives a wrong answer about absurde. So a function termine that always answers correctly cannot exist: the teacher has been swindled.

Conclusion on recursion

Finally, a good rule: do not try to follow the recursive calls in every detail to understand what a recursive function does. Check the stopping case, assume that the recursive call does what it should, and check that the rest of the function gets the right result from it.