[Tutor] learning recursion

[Neil Cerutti]

On 2014-02-06, Denis Heidtmann <denis.heidtmann at gmail.com> wrote:
> Running python 2.7 on Ubuntu 12.04
>
> Code:
> def fib2(n):
> if n==1:
> return 1
> elif n==2:
> return 1
> else:
> return fib2(n-2) +fib2(n-1)

Something ate your leading spaces. Keep in mind that that makes
most Python code unrecoverably corrupt. When sharing Python code
you have to take care that leading space (preferably) or tabs (if
you must) are preserved.

> The above works:
>
>>>> fib2(7)
> 13
>>>> fib2(4)
> 3
>
>>>> for i in range(4):
> ...     print fib2(i)
> ...
>
> The above results in an error:
>
>  File "testing.py", line 21, in fib2
>     return fib2(n-2) +fib2(n-1)
> RuntimeError: maximum recursion depth exceeded
>
> Is this some subtle problem or is it some stupid mistake on my
> part?
>
> Thanks for your help.

It's because fib(0) never terminates.

The fibonacci numbers should start with (1, 1, 2) i.e., fib(0)
ought to return 1, with the rest of your algorithm adjusted
accordingly.

-- 
Neil Cerutti