User Tools

Site Tools


rec

Recursive programming and pattern matching

Recursive definitions

Sometimes you would like to mention the name of the function you are defining, within its own body. This is not allowed by default:

# let f x = f x;;
Unbound value f

To define a recursive function, you have to declare it through the keyword rec. For example, to define the factorial function:

# let rec fact x = 
  if x=0 then 1 
  else x * fact (x-1);;
 
val fact : int -> int = <fun>
 
# fact 5;;
- : int = 120

Note that integer arithmetic is subject to overflows. On 32-bit machines, the values of type int are integer numbers from −230 to 230−1, that is −1073741824 to 1073741823. Some architectures may support a wider range of integer values.

# fact 12;;
- : int = 479001600
 
# fact 13;;
- : int = -215430144

However, arbitrary-precision arithmetic can be easily recovered through the OCaml libraries:

#  #load "nums.cma";;
open Num;;
 
#let rec fact' = fun x ->
      if x =/ Int 0 then Int 1 else x */ fact' (x -/ Int 1);;
 
val fact' : Num.num -> Num.num = <fun>
 
string_of_num (fact' (Int 13));;
# - : string = "6227020800"

Note that our factorial function may diverge, i.e. loop forever What happens in practice is that the Ocaml interpreter signals a run-time error, giving us a hint of what has gone wrong:

# fact (-1);;
Stack overflow during evaluation (looping recursion?).

This is another example of a function that never terminates (without even producing a runtime error):

let rec f x = if x=0 then 1 else f x;;
# val f : int -> int = <fun>
 
# f 2
(loops forever)

Being a dialect of ML, OCaml features a call-by-value (or eager) evaluation strategy. This means that the argument of a function will always be evaluated, even if unused in the body of the function.

(fun x -> 1) (f 2);;
(loops forever)

Sometimes it is convenient to define functions by mutual recursion, that is when the definition of f depends on the definition of g and viceversa. For example, testing whether an integer is odd or even can be implemented as follows:

# let rec even n = if n=0 then true else odd (n-1)
  and odd n = if n=0 then false else even (n-1);;
 
val even : int -> bool = <fun>
val odd : int -> bool = <fun>


Tail recursion

Consider the following recursive function:

# let rec foo x =
    if x=0 then 1
    else 1 + foo (x-1);;
 
val foo : int -> int = <fun>

Let's apply it:

# foo 10
 - : int = 11

Actually, foo x computes the successor of x if x is non-negative; otherwise, it diverges.

Let's now try with a bigger input:

# foo 1000000
Stack overflow during evaluation (looping recursion?).

What happened ? Each recursive call caused a new activation record to be pushed on the call stack. When the call stack growns too much, the computation results in a stack overflow.

Why do we need to push a new activation record on the call stack ? Let us examine the branch of the if-then-else where the recursive call is made:

  ...
  else 1 + foo (x-1)

To evaluate the expression 1 + foo (x-1), the interpreter:

  1. evaluates x-1
  2. pushes a new frame for foo on the call stack, contanining the value of x-1 and the return point
  3. executes foo (x-1)
  4. places the return value in the activation record of the caller
  5. pops the frame from the call stack
  6. adds 1 to the return value

So, is it really unavoidable that recursive functions produce a stack overflow on large inputs ?

No, there is a class of recursive functions that can crunch large inputs without making the stack overflow. These are the functions where the recursive call happens as the last thing, i.e. they have the form:

let rec foo x =
  ...
  foo e
;;

These functions are called tail recursive. Since the recursive call happens as the very last thing, there is no need to push a new frame on the call stack: the same frame of the caller can be reused by the callee. This allows the compiler to deal with the recursive call in the same way as a while loop. That is, the recursive call is compiled into a jump to the start of the callee code.

There is a standard technique to write functions in a tail-recursive manner. This technique uses an additional argument to accumulate the partial results computed by the recursive function.

Let us consider again the function foo. We write a function foo2 which uses two arguments. The first argument is the same x as in foo. The second argument acc accumulates the results.

# let rec foo2 x acc =
  if x=0 then acc
  else foo2 (x-1) (acc+1);;
 
val foo2 : int -> int -> int = <fun>

We can now rephrase foo in a tail-recursive manner. It suffices to apply foo2, with the initial accumulator equal to 1 (the return value in the base case).

# let foo' x = foo2 x 1;;
val foo' : int -> int = <fun>

Let's try to feed foo' with a big input:

# foo' 1000000
- : int = 1000001

Since the function foo2 will only be used by foo', it is better to hide it through a nested let-definition:

# let foo' x = 
  let rec foo2 x acc =
    if x=0 then acc
    else foo2 (x-1) (acc+1)
  in foo2 x 1;;
 
val foo' : int -> int = <fun>

Let us now consider a more complex example. The function sumsq computes the sum of the first x squares:

# let rec sumsq x = 
  if x=0 then 0
  else x*x + sumsq (x-1);;
 
val sumsq : int -> int = <fun>

Note that sumsq is not tail recursive. Let us feed it with a big input:

# sumsq 1000000;;
Stack overflow during evaluation (looping recursion?).

We can exploit the accumulator technique to make sumsq tail-recursive.

# let sumsq' x =
  let rec sumsq2 x acc =
    if x=0 then acc
    else sumsq2 (x-1) (acc+x*x)
  in sumsq2 x 0;;
 
val sumsq' : int -> int = <fun>

Let us now try it (on 32-bit machines, you will obtain a negative result):

# sumsq' 1000000;;
- : int = 333333833333500000

To recover a precise result, you can use arbitrary-precision arithmetic:

# let sumsq'' = fun x ->
  let rec sumsq2 x acc =
      if x =/ Int 0 then acc 
      else sumsq2 (x -/ Int 1) (x */ x +/ acc)
  in sumsq2 x (Int 0);;
 
val sumsq'' : Num.num -> Num.num = <fun>
 
# sumsq'' (Int 1000000);;
- : Num.num = Int 333333833333500000


Pattern matching

Pattern matching is another peculiarity of functional programming. We shall see in the next two lectures how it can be fully exploited to define functions on lists and recursive data types. Here, we mainly use pattern matching to write function definitions in a cleaner way.

As a first example, let us consider the Fibonacci function:

# let rec fib = fun n -> 
    if n=0 then 0 
    else if n=1 then 1 
    else fib (n-1) + fib(n-2);;
 
val fib : int -> int = <fun>

This can be made more readable with pattern matching:

# let rec fib = fun n -> match n with
    0 -> 0
  | 1 -> 1
  | n -> fib (n-1) + fib(n-2);;

This is even more readable after some syntactic sugar. The keyword function below allows us to write function patterns as a shorthand for fun x → match x with patterns):

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

Writing nested if-then-else becomes quiclky unreadable as the degree of nesting increases. Consider, for instance, the following (verbose) definition of the XOR function:

# let xor x y = 
    if x then (if y then false else true) 
    else (if y then true else false);;
val xor : bool -> bool -> bool = <fun>

Pattern matching allows here for a cleaner definition:

# let xor = fun x -> match x with
  (false,false) -> false 
| (false,true)  -> true
| (true,false)  -> true
| (true,true)   -> false;;
 
val xor : bool * bool -> bool = <fun>

We can simplify definition of the xor function by using variables within patterns.

# let xor = function
  (false,y) -> y
| (true,y)  -> not y;;
 
val xor : bool * bool -> bool = <fun>

The wildcard _ (underscore) matches every pattern. As an example, we define a function that, given two booleans x and y, computes x ⇒ y (classical implication).

# let imp = function
    (true,false) -> false
  | _ -> true;;
 
val imp : bool * bool -> bool = <fun>

As a further example, we define the predecessor function on natural numbers:

# let pred x = match x with 
  0 -> 0
| _ -> x-1;;
 
val pred : int -> int = <fun>

Patterns may have arbitrary boolean guard expressions associated with them, such that a pattern matches only when the guard expression evaluates to true.

Let us use guards to write a function that computes the sign of a multiplication.

# let sgn n m = match (n,m) with
  (x,y) when x>0 && y>0 -> "+"
| (x,y) when x<0 && y<0 -> "+"
| (0,_) -> "0"
| (_,0) -> "0"
| _ -> "-";;
 
val sgn : int -> int -> string = <fun>


Exercises

rec.txt · Last modified: 2015/10/08 15:20 (external edit)