Re: [Caml-list] How to find out if a function is tail recursive?

["Wolfgang Müller" <Wolfgang.Mueller2@uni-bayreuth.de>]

On Thursday 12 June 2003 16:15, Richard Jones wrote:
> I was writing the section on tail recursion in the OCaml tutorial, and
> was surprised to find out that the range function (below) isn't tail
> recursive. Or at least it causes a stack overflow on a
> large-but-not-unreasonable input value.
>
> let rec range a b =
>   if a > b then []
>   else a :: range (a+1) b
>   ;;
>
> let list = range 1 1000000;;
>
> Printf.printf "length = %d\n" (List.length list);;
>
> Can you tell me why this function isn't tail recursive, 

I'll try, just to get some brainy people review my code :-)

let my_range a b = 
	let rec r a b out_range=if a>b 
		then out_range 
		else r a (b-1) (b::out_range)
	in r a b [] ;;

The difference is that when your_range is at the end of recursion, it will 
give back the empty list. To this, the innermost "a" will be prepended to [], 
then the before-innermost "a" will be prepended to that, etc... The stack 
needs to memorize this "onion" of things that need to be prepended --> not 
tail recursive.

my_range will give back at the end of the recursion the finished result. 
Nothing has to be done anymore except giving back out_range, so we can give 
it back, and do not need to remember where we came from, except for the 
initial call.

> and share any
> useful tips on how to tell whether a function is or is not tail
> recursive?

If I remember right, in the Scheme R5RS standard document there is a very 
formal description of when things are tail-recursive based on Scheme syntax.

Cheers,
Wolfgang

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners