[Tutor] FW: recursion

[Scott Widney]

> On Mon, 13 Jan 2003, Scott Widney wrote:
> 
> > > ###
> > > def factorial(z):
> > >     assert z >= 0, "Invalid input: z must be nonnegative."
> > >     if z == 1 or z == 0:
> > >         return 1
> > >     else:
> > >         return z*factorial(z-1)
> > > ###
> >
> > Danny, you've talked before about tail recursion. Is this below a
> > properly-formed (if a little terse), tail-recursive definition for
> > factorial()?
> >
> > ###
> > def factorial(x, result=1):
> >     assert x >= 0, "Number must be non-negative."
> >     if x <= 1: return result
> >     else: return factorial(x-1, x*result)
> > ###
> 
> Hi Scott,
> 
> Yup.  This is perfect.  *grin*
> 
> 
> 
> If you'd like more concrete information on what constitutes a
> tail-recursive function, I can quote some stuff off a book 
> I'm reading now called "Concepts in Programming Languages". 
> It's a little dry, but it gives more formal definitions that
> might be helpful.  Here's the section:
> 
> 
> """
> For tail recursive functions, which are subsequently described,
> it is possible to reuse an activation record for a recursive
> call to the function. This reduces the amount of space used by a 
> recursive function.
> 
> The main programming language concept we need is the concept 
> of tail call. Suppose function f calls function g.  Functions f
> and g might be different functions or f and g could be the same
> function.  A call to f in the body of g is a "tail call" if g
> returns the result of calling f without any further computation.
> For example, in the function
> 
>     fun g(x) =
>         if x = 0 then f(x)
>         else f(x) * 2
> 
> the first call to f in the body of g is a tail call, as the 
> return value of g is exactly the return value of the call to f.
> The second call to f in the body of g is not a tail call because
> g performs a computation involving the return value of f before
> g returns.
> 
> A function f is "tail recursive" if all recursive calls in 
> the body of f are tail calls to f.
> """
> 
> 
> The language they're using isn't Python, but we can translate 
> it to Python syntax pretty easily:
> 
> ###
> def g(x):
>     if x == 0: return f(x)
>     else: return f(x) * 2
> ###
> 
> 
> Anyway, hope this helps!

Thanks Danny! (^ ocaml ?)

To the group at large: I timed the two versions above, looping each 100
times through range(100), and noticed that the non-tail-recursive function
is faster (2.163 seconds versus 2.394 seconds). In your experience is that a
common payoff between the two types of recursion (speed for space)?


Scott