Python Function Return Loop

Question

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?

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
– Kevin J. Chase, Commented Sep 18, 2015 at 15:06
@proxenmity it was a recursion joke. You missed it. For explanation, see here: stackoverflow.com/q/32653496/2066079 — dberm22
– dberm22, Commented Sep 18, 2015 at 18:05

Matteo Tassinari · Accepted Answer · 2015-09-18 15:40:35Z

18

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?

edited Sep 18, 2015 at 15:40

Matteo Tassinari

18.6k8 gold badges65 silver badges85 bronze badges

answered Sep 18, 2015 at 13:43

RedX

15.3k2 gold badges57 silver badges81 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Andrea Corbellini Over a year ago

@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.

Konrad Rudolph · Accepted Answer · 2015-09-18 13:43:44Z

11

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

answered Sep 18, 2015 at 13:43

Konrad Rudolph

549k142 gold badges967 silver badges1.3k bronze badges

Comments

Sanna Keller-Heikkila · Accepted Answer · 2015-09-18 13:50:41Z

4

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.

answered Sep 18, 2015 at 13:50

Sanna Keller-Heikkila

2,5946 gold badges25 silver badges36 bronze badges

Collectives™ on Stack Overflow

Python Function Return Loop

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related