This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

[Caml-list] How to find out if a function is tail recursive?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: -- (:) From: Wolfgang Müller Subject: Re: [Caml-list] How to find out if a function is tail recursive?
```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

```