[Tutor] strange recursion result

Daniel Yoo dyoo@hkn.eecs.berkeley.edu
Sun, 7 Jan 2001 14:22:48 -0800 (PST)

On Sun, 7 Jan 2001 mbc2@netdoor.com wrote:

> I wrote a short little program to perform a recursive calculation for me.
> #!/usr/local/bin/python
> def rlgncount(n):
> 	if (n<=1):
> 		return 0
> 	else:
> 		return (n-1)+rlgncount(n-1)
> print rlgncount(1000)

[some text cut]

> I must be missing something simple, but I don't see it. Does anyone have
> any suggestions?

Ah!  So it calculates the sum from 1 to n-1.  Cool!

The definition of your program is perfectly legitimate.  The only problem
is that Python doesn't support such a larger recursion depth.  You
probably got the following message:

RuntimeError: Maximum recursion depth exceeded

which means that it just hit its limits.  The Python implementors are
probably planning to support recursion to arbitrary depths in the future,
but this hasn't been done yet.

Are you coming from a Scheme background?  Since Scheme's only iteration
consists of recursion, the implementors of Scheme made extra sure that
they didn't impose limits to recursion.  Python, on the other hand, does
recursive-like stuff with for/while loops, so it's a bit less functional
in terms of recursion.

for i in range(n):
    sum = sum + i

is one way of performing your function, at the expense of requiring the
use of variables.  But Python also supports a bit of functional

sum = reduce(lambda x, y: x+y, range(n))

will also add the numbers from 0 to n-1.

Apologies: it feels like a disappointing answer to say "It won't work
yet"; does anyone have any suggestions or comments?