Making recursive function in python

Question

This is a homework problem. I try to get a recursive function:

def problem_a(n):
    answer.append(n)
    if n == 1:
        return answer    
    elif n % 2 == 0:
        answer.append(n/2)
    else :
        answer.append(n*3 + 1)
        problem_a(n*3 + 1)

This code obviously doesn't work as answer isn't defined as a list. With loops it would work, but I want to make a recursive function. I could just use as input a list, but I wonder if there exist something more elegant.

problem_a(7) should give as output:

[7, 22, 11, 34, 17, 52, 26, 13, 40 , 20, 10 ,5 ,16, 8, 4, 2, 1]

Ashwini Chaudhary · Answer 1 · 2013-06-17T11:40:15.180

You can define a local variable answer and pass it around in recursive calls.

def problem_a(n, answer = None):
    answer = [n] if answer is None else answer
    if n == 1:
        return answer
    elif n % 2 == 0:
        n = n/2
        answer.append(n)
    else:
        n = n*3 + 1
        answer.append(n)
    return problem_a(n, answer)

print problem_a(7)

output:

[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

Wolph · Answer 2 · 2013-06-17T11:39:18.970

2

You could try a generator:

def problem_a(n):
    yield n
    if n == 1:
        return
    elif n % 2 == 0:
        x = n / 2
    else:
        x = n * 3 + 1

    for y in problem_a(x):
        yield y

print list(problem_a(7))

edited Jun 17 '13 at 11:39

answered Jun 17 '13 at 11:33

Wolph

78,177
11
137
148

score 2 · Accepted Answer · answered Jun 17 '13 at 11:48

One alternative solution to the ones that have been suggested so far (which use an extra argument to pass the list up the recursive chain) is to build the final list as you return from the recursion. This is not terribly efficient, since concatenating lists requires copying both of them, but it will work:

def problem_a(n):
    if n == 1:
        return [n]
    elif n % 2 == 0:
        return [n] + problem_a(n // 2)
    else:
        return [n] + problem_a(3*n + 1)

@Kasper `//` is for py3.x, it truncates the decimal digits. – Ashwini Chaudhary Jun 17 '13 at 11:53 — Ashwini Chaudhary, Jun 17 '13 at 11:53

juniper- · Answer 4 · 2013-06-17T11:48:04.860

1

There is a problem with your skeleton solution. You need to recurse when n % 2 == 0 as well as in the final else. The answer variable is given a default value so that it is initialized to [] when the function is first called without an argument.

def problem_a(n, answer=None):
    if answer == None:
        answer = []

    answer.append(n)
    if n == 1:
        return answer    
    elif n % 2 == 0:
        return problem_a(n/2, answer)
    else :
        return problem_a(n*3 + 1, answer)

>>> problem_a(7)
[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

Edit

As per the comments, using a mutable default argument is a bad idea. Just set it to None like in the other posts and check if its None to create a new list. I changed the answer to reflect this.

The original bad code was as follows:

def problem_a(n, answer=[]):
    answer.append(n)
    ...

edited Jun 17 '13 at 11:48

answered Jun 17 '13 at 11:35

juniper-

6,262
10
37
65

1

I recommend using answer=None and check for None. You should never use mutables as default arguments, as they can be mutated easily and only a reference will be handed around. That's dangerous! – enpenax Jun 17 '13 at 11:44
2

Using a [mutable default argument](http://stackoverflow.com/questions/1132941/least-astonishment-in-python-the-mutable-default-argument) is a bad idea. It will only work as intended if you only ever call it only once. – Blckknght Jun 17 '13 at 11:44
Thanks to the comments! I didn't know that that trick was a bad idea :) – juniper- Jun 17 '13 at 11:48

score 1 · Answer 5 · answered Jun 17 '13 at 13:03

You can also use a closure:

>>> def s():
    ret = []
    def f(n):
        ret.append(n)
        if n % 2 == 0:
            f(int(n/2))
        elif n != 1:
            f(int(n*3 + 1))
        return ret
    return f

>>> s()
<function f at 0x00000000033A5848>
>>> s()(7)
[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

Making recursive function in python

5 Answers5