- On Thu, 5 May 2005, vly3 wrote:

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

OK, let me try :-)

> 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, other than to try it

> in the OCaml interpreter with a large number of recursions and see if

> it runs out of stack space. Maybe a simple example would help me.

> For instance, if I define function f as follows:

>

> let rec f x = if x = 1 then (x * 2) else ( x * 2) + f (x - 1);;

>

> If I call

>

> f 100000;;

>

> The stack overflows with the message:

> Stack overflow during evaluation (looping recursion?).

>

> From that, I assume that my function f is not tail recursive. Can

> anybody rewrite that in tail recursive form, or give me an explanation

> of tail recursion simple enough for an idiot to understand?

The result of the recursive call must be the result which is

returned, without passing through any processing.

Note that the question is not whether the function is tail-recursive, but

whether the compiler knows it and performs the appropriate optimization:

(* detected as tail-recursive *)

let rec f () = f ()

let rec f () = if Random.int 2 = 0 then f () else f ()

let rec f x = (fun () -> f x) ()

let rec f () = g ()

and g () = f ()

(* not detected as tail-recursive *)

let rec f () = f (); ()

let rec f () = let x = f () in x

let rec f () = try f () with Exit -> ()

Martin

--

Martin Jambon, PhD

http://martin.jambon.free.fr - 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