Recursion in memory

Question

def rec(x):
    if x < 2:
        return 1
    else:
        a = rec(x-1)
        b = rec(x-2)
        return a+b
rec(4)

I don't understand this works in memory or why it returns 5. Could someone help me out?

Maybe you're interested in learning more about [stack frames](http://www.programmerinterview.com/index.php/recursion/explanation-of-recursion/). — Two-Bit Alchemist, Apr 10 '14 at 23:07
Your `rec` computes the Fibonacci numbers. You will find many, many discussions of recursive Fibonacci functions if you type “recursive” and “fibonacci” into your favorite search engine. — rob mayoff, Apr 10 '14 at 23:08

score 1 · Answer 1 · answered Apr 10 '14 at 23:02

Use print statements, it will make the recursion process more clear: Basically it will keep calling rec over and over until it hits the "base case" which for you is when x < 2. It has to recursively call all the way down until it hits the base case, then come all the way back up.

Input

def rec(x):
    if x < 2:
        return 1
    else:
        print "x = ", x
        a = rec(x-1)
        print "a = ", a
        b = rec(x-2)
        print "b = ", b
        return a+b
rec(4)

Output

x =  4
x =  3
x =  2
a =  1
b =  1
a =  2
b =  1
a =  3
x =  2
a =  1
b =  1
b =  2
5

score 1 · Answer 2 · answered Apr 10 '14 at 23:05

Lets map out the calls:

                                  rec(4)
                rec(3)              +              rec(2)
      rec(2)       +     rec(1)     +      rec(1)    +      rec(0)
rec(1)  +  rec(0)  +       1        +        1       +        1
  1     +    1     +       1        +        1       +        1

So you can see there (and by looking at the code) that for each call of rec(i) where i >= 2, it splits into rec(i-1) + rec(i-2), when i < 2 we are at the base case and the call just returns 1. So by writing something like what I have done above you can trace through the calls until all you are left with is the base cases.

score 0 · Answer 3 · answered Apr 10 '14 at 23:08

As an addition to Cyber's answer, here's output that indicates the depth of recursion:

def rec(x, depth=0):
    print " "*(depth*3), "x =", x
    if x < 2:
        print " "*(depth*3), "=> 1"
        return 1
    else:
        a = rec(x-1, depth+1)
        print " "*(depth*3), "a =", a
        b = rec(x-2, depth+1)
        print " "*(depth*3), "b =", b
        print " "*(depth*3), "=>", a+b
        return a+b

rec(4)

Output:

score 0 · Answer 4 · answered Apr 10 '14 at 23:10

Assume each indentation denotes another layer of recursion (it's in a deeper function call). Note that when x < 2, I assume you understand why rec(x) = 1.

rec(4)
    a = rec(3)
        a = rec(2)
            a = rec(1) = 1
            b = rec(0) = 1
            return a + b
        #a = 1 + 1 = 2
        b = rec(1)
        return a + b
    #a = 2 + 1 = 3
    b = rec(2)
        a = rec(1) = 1
        b = rec(0) = 1
        return a + b
    #b = 1 + 1 = 2
    return a + b
#rec(4) = 5

Recursion in memory

4 Answers4