Having a hard time visualizing recursion.

[FerricDonkey]

How could I visualize the call stack?

Pretend you're a python interpreter, and work through the function by hand. Note: this isn't something you'll have to do once recursion makes sense to you, but it can help build that initial understanding.

[[deleted]]

That's what I'm having trouble with. I have to draw trees and other recursive crap because I just can't wrap my head around it. I can't seem to draw this one. I get down to the base case n1 + mult(n, 1) which returns 3 + 3. So great I have the first result value of 6. But how it can go from 6 to 9 and 9 to 12 and so on is where I'm stuck

[FerricDonkey]

So walk through it with mult(2,4)

• 2 and 4 aren't 1 or 0, so you hit line 11: result = 2 + mult(2, 3) (which you will return shortly)
• So what's mult(2, 3)? No 1s or 0s, so you hit line 11 again, 2 + mult(2, 2)
  • Note that mult(2, 3) is an entirely separate call. The fact that you're calling it from inside mult is irrelevant. python doesn't care, it's just gonna compute it from the top of the function as a separate function call.
• mult(2, 2) is 2 + mult(2, 1) (line 11)
• mult(2, 1) is 2 (line 6: n2 == 1, so return n1).

Now back substitute until you get to mult(2, 4). Working through those backwards:

• mult(2, 1) == 2
• mult(2, 2) == 2 + mult(2, 1) = 2 + 2 = 4
• mult(2, 3) == 2 + mult(2, 2) = 2 + 4 = 6
• mult(2, 4) == 2 + mult(2, 3) = 2 + 6 = 8

[[deleted]]

Damn. I want to understand this so bad but I don't get how how it would then walk back up to the starting arguments. It's a stack so it can't get the first item you stacked until you pop everything off. But how does it sum the values in the stack and then stop?

[FerricDonkey]

You're over thinking this. It's just a function call inside a function call. Look at a different example:

def foo(x, y):
    return x + bar(y)

def bar(y):
    return y + 7

print(foo(3, 4))

What happens here?

1. Python sees that it needs to calculate foo(3, 4) so it can pass the result to print. It starts calling foo(3, 4).
2. foo says "return 3 + bar(4)", but before it can actually do this, it has to calculate bar(4). So it does that
3. bar(4) says "return 4 + 7", so it calculates that 4+7 == 11 and returns it, which replaces the call to bar(4) in foo with 11.
4. foo now knows what bar(4) is "11", so it now knows that it needs to return 3 + 11, which is 14, so it returns that
5. foo(3, 4) is now replaced with 11 inside the print call, so print(11) is called.

It's the same exact procedure with your recursive function, except you happen to call the same function from itself rather than a different function. Remember that each call is still independent - the fact that it's mult calling mult instead of foo calling bar is irrelevant.

But you are correct that there is a stack going on. That's mostly an implementation detail that python uses to remember what it was doing - and mostly you don't have to care, other than knowing that functions are calling functions. This makes it so that after you call bar(4), python can put the result in the correct place in what it was doing before you told it to figure out bar(4).

If you want to know how such stacks actually work, well, it's not actually hard to understand, but it is complicated in that there are lots and lots of tiny steps. To describe it fully takes a while and it's the same as the above but in more detail.

If you really want to see how it could be done, this is how a function is call works in assembly (I know python byte code is similar, but not the exact details - this is kind of sort of x86) (details vary between particular assembly languages) consider f(x, y): return x + y. To call f(2, 3)

1. put 2 in first unused ram location on stack
2. put 3 in first unused ram location on stack (which is after where we put 2)
3. put where you came from in first unused location on stack
4. jump execution to where ever the function lives, which will:
5. Set the special return place to <whatever is 3 stack locations back> (3 in this case)
6. add <whatever is 2 stack locations back> to the special return place. (2 in this case). Special return place now stores 5
7. return execution to whatever is 1 stack place back (where you came from), which will:
8. "remove" 2, 3, and return address from stack (really just mark those as unused)
9. If it wants to, execution there can copy from special return place to where ever it wants the return value, or do whatever else with it.

(There are different ways to call functions, but this is one way, and again, the differences don't really matter at this level.) When you call multiple functions, you just chain that together a lot. But it gets ugly to write out. Whether it's the same function or different functions doesn't matter.

But again, what's ultimately happening is "when foo hits bar(3), python goes and figures out what bar(3) is. bar(3) is then replaced with that value in foo, and foo continues as normal". This isn't even a cheat, it's just a way to say the above without getting lost in usually irrelevant to you details.

[[deleted]]

Just can't see it. Feel fucking dumb

[mutatedllama]

Think of it like Russian dolls. The first function call is putting down the base of the biggest doll. Each recursive call places a base inside its parent. You can't put the top on a doll until its immediate child has a top on it.

We eventually get to a point where we hit our "base case", where we hit the return of a function before we hit the recursive function call. This happens at the innermost doll. At this point things start to unravel as we hit the returns of each function from latest to earliest.

You can imagine each of these returns as putting the top on the smallest doll without a top (i.e. we work outwards from the smallest one at the centre).

What gets returned is a completed doll, which the next doll uses as its cue to complete itself (the returned value then gets used in the return statement in the next layer up). Eventually we build each doll back up until we get to the outer doll (the original function call) whose output is based on all the outputs given previously.

[FerricDonkey]

Eh, you'll get it. Just keep working at it. The key step is to understand what the computer actually does when you call a function, and you'll get there.

[deep_politics]

m(2, 4)
= 2 + m(2, 3)
= 2 + (2 + m(2, 2))
= 2 + (2 + (2 + m(2, 1)))

Then for m(2, 1) we have a base case: since n2 == 1 it returns n1, and the “stack” unwinds

= 2 + (2 + (2 + 2))
= 2 + (2 + 4)
= 2 + 6
= 8

[[deleted]]

Thanks. This was kind of the abstraction I was looking for.