OCAML Course

Recursive functions

Go back

A recursive function is a function calling itself. In OCaml, you have to add rec before the name of your function.

let pow x power = 
	if power = 1
	then x
	else x * (pow x (power-1))

let _ = pow 5 3 (* 125 *)

If you forget the keyword rec, then the compiler will tell you Unbound value pow.

Terminal or nonterminal functions

You usually write a nonterminal function when you are postponing the calculations meaning that you are calculating the next term before the current term (evaluating n+1 before n).

A terminal function is when you are writing your code to evaluate n before n+1.

The function above is nonterminal! To write some terminal functions, we will use the concept of functions of an accumulator.

Functions of an accumulator

A function of an accumulator is called fonction accumulatrice in French. The main idea is that you will store in a variable the result, update the parameters and call the recursive function with a new accumulator, and the updated parameters.

let pow x power =
	let rec pow_acc power acc = 
		(* some code *)
	in pow_acc power 1 (* x^0 = 1 *)

Before completing this function, notice that we are using "let ... in", so the result of let pow x power is the evaluation of pow_acc power 1. This is something you need to master, as you will use this often!

let pow x power =
	let rec pow_acc power acc = 
		if power <= 0
		then acc (* done, return result *)
		else let new_acc = x * acc
			 in let new_power = power - 1
			 in pow_acc new_power new_acc
			 (* <=> pow_acc (power-1) (x * acc) *)
	in pow_acc power 1 (* x^0 = 1 *)

let _ = pow 5 3 (* 125 *)

Pro tip: we are talking about Functions of accumulators, if you got more than one accumulator.