[Tutor] Recursion confusion

[Karl Pflästerer]

On  5 Oct 2003, Todd Stephens <- tbstep at tampabay.rr.com wrote:

[...]
> So, what is going on here is this:
> 3 results in the function returning 3* the result of factorial(2), which 
> results in 2 * the result of factorial(1), which results in 1 * the 
> result of factorial(0) which results in 1.  So, we have 1*1*2*3.  Now, 
> if I were to omit the first condition of n==0, I would get infinite 
> recursion, correct?  So, along those lines, for recursion to work, I 

Yes.

> have to include some sort of conditional terminator.  Is that correct?  

Yes.  Never ever forget that.

> If so, I guess I finally understand it (somewhat anyway :-))

Fine.

But don't rely too much on recursion in Python.  Too deep recursion will
cause Python to complain.  Try factorial(999) with your code.  Python
does nothing like eg. Scheme which can optimize recursive algorithms
where the recursive function call is in tail position (the last function
call in the caller).  Better use an iterative version here.
(You could increase the maximal recursion depth in Python but than the
error would occur only later; I am not sure at the moment but I think
stackless Python does not have this problem).


   Karl
-- 
Please do *not* send copies of replies to me.
I read the list