current community

your communities

more stack exchange communities

Stack Exchange Inbox Reputation and Badges
tour help
stack overflow careers
Sign up ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free.
up vote 9 down vote favorite

Ok, so this piece of code is from a practice question at my school. We are to mentally parse the code and check the answer.

When I first parsed it, I got 4. I copied the code and ran it through IDLE and got 8. I ran the debugger and saw that the else: return is looping the if else statement until x == 0 and then it returns 1.

I do not understand how return 1 is coming out to 8.

def foo(x=5):
    if x == 0:
        return 1
    else:
        return 2*foo(x-1)

print(foo(3))

I understand that it is calling foo(x-1) inside the function foo(x=5) which makes it check if else again and again until x == 0 then it returns 1. How does return 1 end up printing 8?

share|improve this question
5  
Duplicate of stackoverflow.com/questions/32653496/… ? –  wap26 yesterday
    
foo is a recursive calculation of "2 to the x power", for non-negative integer values of x. (If it had multiplied foo(x-1) by x instead of by 2, it would have calculated "x factorial" instead.) –  Kevin J. Chase yesterday
    
@wap26 the link you provided seems to be my question –  proxenmity yesterday
1  
@proxenmity it was a recursion joke. You missed it. For explanation, see here: stackoverflow.com/q/32653496/2066079 –  dberm22 yesterday

3 Answers 3

up vote 17 down vote accepted

You will make following calls to foo:

foo(3) -> foo(2) -> foo(1) -> foo(0)

those will return

foo(0) -> 1
foo(1) -> 2 * foo(0) -> 2 * 1 -> 2
foo(2) -> 2 * foo(1) -> 2 * 2 -> 4
foo(3) -> 2 * foo(2) -> 2 * 4 -> 8

Is it clear now?

share|improve this answer
    
@JamesHaskett: this answer (implicitly) shows a method for implementing the same function without using recursion. It would be a good exercise to implement foo both with and without recursion and compare the two approaches. –  Andrea Corbellini yesterday
up vote 11 down vote

I think you’re having the right idea (otherwise you wouldn’t have gotten the answer 4), you’re simply aborting too early in your mental exercise.

You can keep track of the variables by tabulating them while going through the code:

  • foo(3)
    • calls foo(3 - 1) → foo(2)
      • calls foo(2 - 1) → foo(1)
        • calls foo(1 - 1) → foo(0)
          • returns 1
        • returns 2 * foo(1 - 1) → 2
      • returns 2 * foo(2 - 1) → 4
    • returns 2 * foo(3 - 1) → 8
share|improve this answer
up vote 4 down vote

Recursion works in reverse from what you'd initially expect. It doesn't start with x=3, but instead it follows all the recursive calls and the first value of x is actually 0.

Here is a modified version of your script that illustrates the order of how it ran the steps and how it arrived at 8.

def foo(x=5):
    if x == 0:
        r = 1
        print (x, r)
        return r
    else:
        r = 2*foo(x-1)
        print (x, r)
        return r

print(foo(3))

Notice how the first value of x that's printed is 1 instead of the 3 you gave it. Once you understand this, you will understand recursion.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.