[Tutor] help with a recursive function

[Steven D'Aprano]

c smith wrote:
> hi list,
> i understand the general idea of recursion and if I am following well
> written code I can understand how it works, but when I try to write it for
> myself I get a bit confused with the flow.

Your flow is fine. You just forget to return anything in two of the 
three branches. It's one thing to *call* the recursive function, but you 
have to do something with the result, normally return it. Otherwise 
Python just throws the result away and then returns None, exactly the 
same as this non-recursive function:

def add_one(x):
     """Return x + 1"""
     y = x + 1


You need a return statement.

Further comments below:


> I was trying to turn an ackerman function into python code for practice and
> I tried writing it like this:
> #!/usr/bin/env python
> 
> import sys, os
> def ack(m,n):
> 
>     if m == 0:
>         return n+1
>     elif m > 0 and n == 0:
>         ack(m-1,1)
>     elif m > 0 and n > 0:
>         ack(m-1,ack(m,n-1))
> 
> if __name__=='__main__':
>     sys.argv[1] = int(sys.argv[1])
>     sys.argv[2] = int(sys.argv[2])
> 
>     print ack(sys.argv[1], sys.argv[2])
> 
> The major problem, I think, is that I cant figure out where to turn the args
> into ints.

(1) That has nothing to do with recursion.

(2) Your guess as to the problem is wrong. You are successfully turning 
the args into ints.

(3) In my opinion, it is bad form to write back to sys.argv like that. 
You should say something like this:

     m = int(sys.argv[1])
     n = int(sys.argv[2])
     print ack(m, n)


although what you haven't done is strictly *wrong*, it is a bit strange.



> When run in this form I get the 'typeError' error on 'n+1' I guess because
> the args are still strings.

Rather than guess, you should read the error message and pay attention 
to what it actually says. When I run your code, I get:

TypeError: unsupported operand type(s) for +: 'NoneType' and 'int'


But if I try to add 1 to a string, I get a very different error message:

 >>> '2' + 1
Traceback (most recent call last):
   File "<stdin>", line 1, in <module>
TypeError: cannot concatenate 'str' and 'int' objects


So the problem is *not* that n is still a string, the problem is that n 
is NoneType, that is, n = None. Why is n None? Because this branch of 
the function:

     ack(m-1,ack(m,n-1))

calls ack with m=m-1 and n=ack(m, n-1) but ack(...) returns None in two 
out of the three branches. Hence n gets set to None.


If you want to understand recursion, you are probably better off 
starting with simpler examples: start by writing your own recursive 
factorial function, then Fibonacci, and once you understand them, then 
try Ackerman.



-- 
Steven