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
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.
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):
(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
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>
Consider the following recursive function:
Let's apply it:
# foo 10 - : int = 11
foo x computes the successor of
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:
fooon the call stack, contanining the value of
x-1and the return point
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
We write a function
foo2 which uses two arguments.
The first argument is the same
x as in
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'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.
sumsq computes the sum of the first
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
# 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 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.
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.
_ (underscore) matches every pattern.
As an example, we define a function that, given two booleans x and y, computes x ⇒ y (classical implication).
As a further example, we define the predecessor function on natural numbers:
Patterns may have arbitrary boolean guard expressions associated with them,
such that a pattern matches only when the guard expression evaluates to
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>