- On Thu, 5 May 2005, vly3 wrote:

> I am having trouble understanding tail recursion. I have read the

Tail recursion is one of those things that never seems to be explained

> posts about tail recursion in the archives, and I have used google to

> look up articles on tail recursion, and I still don't understand how

> to tell if a function is tail recursive or not,

well. It's not hard, once you get it. And anything you can do with a

loop you can do with tail recursion.

There are basically two rules for making a function tail recursive:

1) you can not modify the return value of the recursive call in any way-

this includes sticking the return value in into data structure, prepending

it to a list, or performing any operation on it what so ever.

2) you can not wrap the recursive call in a try/with clause to catch

exceptions.

So, some standard patterns emerge- watch for these, they'll show up

everywhere.

To work around the first limitation, a common pattern is what's called the

accumulation value. This is an extra parameter you pass into the

recursive function which accumulates the proper return value. Here's an

example of that- calculating the factorial power of a number. The naive

way would be:

let rec fact n = if (n < 2) then 1 else n * (fact (n-1));;

Unfortunately, this is not tail recursive (we'll ignore the fact that

you'll overflow integers before you hit the tail recursion for the

moment)- because we're violating the first rule, and applying an operation

(*) to the result of the recursive call. The solution is to to accumulate

the value:

let fact n =

let rec loop accum n =

if (n < 2) then

accum

else

loop (accum * n) (n-1)

in

loop 1 n

;;

The equivelent code in a procedural language, like say C, would be:

int fact(int n) {

int accum = 1;

while (n > 1) {

accum *= n;

n -= 1;

}

return accum;

}

In fact, if you look at the assembly language, the correspondence is

pretty much exact, in that both routines compile into effectively the same

object code.

Let's take another example, but this one building a list. One trick you

see a lot in building lists is that the accumulated list is built

backwards. In Ocaml, adding an element onto the head of a list is really

cheap, but adding an element to the end of a list is really expensive

(basically you have to reallocate the whole list- the longer the list, the

more expensive it is).

So what happens when we want to build a list forward, and each iteration

of the recursive function (aka the loop) we create the new last element of

the list? We use an accumulation variable, like above, except the

accumulation variable is the reverse of the list we want to create. Then,

when we're done, we just reverse the list.

An example of this is a function that creates the first N Fibinocci

numbers (I'm picking examples here that don't need a lot of extraneous

code, not for their absolute utility). So we want a function that given

the number 6, returns the list [1;1;2;3;5;8], and given 7 returns

[1;1;2;3;5;8;13]. Now first, let's just write the function that

(efficiently) calculates Fibinocci numbers:

let fib n =

let rec loop a b i = (* a is the ith fib number,

b is the i-1th fib number *)

if (i >= n) then

a

else

loop (a+b) a (i+1)

in

loop 1 1 2

;;

This is the equivelent of the Java code:

int fib(int n) {

int a = 1;

int b = 1;

for (int i = 2; i < n; ++i) {

int c = a+b;

a = c;

b = a;

}

return a;

}

But notice we don't need to instantiate the c variable explicitly in our

ocaml code (it's still there implicitly).

So now we extend the function, to handle lists. We add an accumulation

variable, which is our list, and just prepend new fib numbers as we make

them:

let fib n =

let rec loop accum a b i =

if (i >= n) then

List.rev accum

else

loop ((a+b) :: accum) (a+b) a (i+1)

in

if (n < 1) then

[]

else if (n == 1) then

[1]

else if (n == 2) then

[1;1]

else

loop [1;1] 1 1 2

;;

Now let's do something trickier. Given an input stream, let's read in all

the lines from the input stream until we hit the end of the file, and

stick all the lines in a list for processing, in order, so the first

string in the list is the first line of the file, etc. We use the

input_line function to read in the lines, which throws an End_of_file

exception if we try to read past the end of file. We play exactly the

same trick as above, and first build our list backwards, and reverse it at

the end. So our first whack at this function is:

let readall chan =

let rec loop accum =

try

let line = input_line chan in

loop (line :: accum)

with

| End_of_file -> List.rec accum

in

loop []

;;

This is tail recursive according to rule #1 (it doesn't modify the return

value from the recursive call in any way), but falls afoul of rule- the

recursive call is inside a try/with statement. So what we do is move the

recursive call outside of try/with statement- we just set a variable if we

caught an exception. So the proper way to write this function is:

let readall chan =

let rec loop accum =

let eof, line = (* eof is true if we caught an exception, false

otherwise *)

try

false, (input_line chan)

with

| End_of_file -> true, ""

in

if eof then

List.rev accum

else

loop (line :: accum)

in

loop []

;;

Now we're tail recursive.

Hope this helps.

Brian - On Friday 04 July 2008 06:04:45 marlenemiller71 wrote:
> Jon Harrop wrote:

Yes.

> > Actually that (eta reduction, IIRC) is a dangerous practice in impure

> > languages like OCaml because it changes when the expressions are

> > evaluated.

>

> impure?

> do you mean eager (as opposed to lazy)?

No but that is related because non-strict languages require purity to be

deterministic.

> > In this case, eta reducing by removing the "x" arguments from both sides

Yes. The result is a sequence of n closures, each calling the next and the

> > of the definition causes the function to partially evaluate sooner,

> > yielding a closure that encapsulates "n" nested function applications. If

> > you remove

>

> # let two n = 2 * n;;

>

> # let rec iter = fun n -> fun f ->

> if (n=0) then fun x->x else compose f (iter (n-1) f);;

> val iter : int -> ('a -> 'a) -> 'a -> 'a = <fun>

>

> Here, if... is evaluated and iter is applied 5 times. Right?

> # iter 5 two;;

> - : int -> int = <fun>

last calling your identity function.

> # let rec iter = fun n -> fun f -> fun x ->

Exactly, yes. The result is a single closure that captured "n", "f" and will

> if (n=0) then x else iter (n-1) f (f x);;

> val iter : int -> ('a -> 'a) -> 'a -> 'a = <fun>

>

> Whereas here, fun x... is evaluated but not if... Right?

> # iter 5 two;;

> - : int -> int = <fun>

fully apply "iter" just as soon as it gets its third and final argument.

> > all arguments that were otherwise deferring the evaluation then

Very easy, just partially apply any of the built-in polymorphic HOFs:

> > you can even

> > change the type of the expression from polymorphic to monomorphic,

> > where the

>

> Hmm! (to do: find an example)

# let f = List.map List.map;;

val f : ('_a -> '_b) list -> ('_a list -> '_b list) list = <fun>

> > non-generalized type variable (e.g. '_a) will be ossified at first

There is a trade-off between that and purity. As Haskell has shown, purity

> > use or even resulting in a type error if it tries to escape a compilation

> > unit.

>

> Hmm :-(

sucks.

--

Dr Jon D Harrop, Flying Frog Consultancy Ltd.

http://www.ffconsultancy.com/products/?e