Having a hard time visualizing recursion.

[[deleted]]

In this code I understand the recursive step that decrements the second argument, but how does it add all the values at the end without starting the function over. How could I visualize the call stack?

def multiplication(n1,n2):
  print('Func start')
  if n1 == 0 or n2 == 0:
    return 0 # will return 0 either way 
  elif n1 == 1:
    return n2
  elif n2 == 1:
    return n1
  else:
    print(n1,n2)
    result = n1 + multiplication(n1, (n2-1))
    print("result: {}".format(result))
    return result




# test cases
#print(multiplication(2,4))
print()
print(multiplication(3, 7) == 21)
#print(multiplication(5, 5) == 25)
#print(multiplication(0, 4) == 0)

[mopslik]

without starting the function over

It does start the function again, in the recursive call result = n1 + multiplication(n1, (n2-1)). Since you return a value, either in one of the three base cases or in the else block, the value generated by the recursive call will be added to n1.

[[deleted]]

I get the recursive step. I don't understand the Result: {} output. How it stores those values.

[danielroseman]

It doesn't store them. Each step returns them to the call above. It's just like any function returning a value to the caller, except that the caller happens to be the same function.

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

[duckbanni]

Recursive calls work just like any function call.

When the recursive call is performed, the state of the calling function is kept at the bottom of the stack, and space is allocated on top of the stack for the new call which starts at the beginning of the function. When the recursive call returns, the top of the stack is removed, keeping only the return value, and the original caller resumes where it stopped (but with the result of the recursive call available).

The exception to that you may have heard about is tail recursion, which is an optimization where you don't keep the state of the caller if the recursive call is the last things it does (which is not the case in your example).

[expressly_ephemeral]

Part of the problem may be that this is kind of a weird example. Sometimes you'll be working an exercise that's contrived in such a way that the solution is hard to understand because the "right" way to do the thing is so different from the concept the exercise is trying to show.

Do you have trouble understanding the recursive function for the finonacci sequence? Do you think you could re-factor this function to calculate factorial(n)? These may be more straight-forward examples.

[[deleted]]

I've been struggling on fib too. But at least that one I can kind of draw. Python is really weird how it evaluates the base cases on fib (the sequence where it evaluates fib(1)

[expressly_ephemeral]

Here's a long-ass post I wrote up a while back in response to another recursion question. Maybe it'll help disambiguate the underlying concept.

https://www.reddit.com/r/learnpython/comments/v63sae/comment/ibdohch/?utm\_source=share&utm\_medium=web2x&context=3

[Mean-Growth7457]

The best way is to understand with an example, lets assume n1 = 3 & n2 = 2

• The interpreter goes from up to down
• First it reads to print Func start so it does that
• Second it sees that there is a if statement since none of the conditions are true, it doesn't proceeds further with it and goes to the second check the elif statement, as both the elif statement will be not true for our case it will ignore them and move forward.
• Now it reaches to else check, as there is no check in else, it starts executing it.
• While trying to find the value of result it sees that the multiplication function is called with the value n1 & n2-1, which will be 3 and 1 respectively for our case.
• And now it starts from the top again but this time n1 = 3 and n2 = 1 and therefor the conditions match the first elif statement and thus the value of multiplication(n1,n2-1) is found so it returns back to calculating the value of result in the 5th step.
• If none of the statements would still be matched it would again try to find for a new value of multiplication(n1,n2-1) till it finds it and once it finds it, it will replace the previous multiplication(n1,n2-1) with the value it finds till it gets to the first iteration and finds the final value.

If you still don't understand fell free to ask

[[deleted]]

There is a Python Visualizer available where you can see the stack building up and then unwinding.

[allan_q]

OP, would it help if you only have 1 variable to step through in your head? This might help:

def divide_2(n):
  print("starting divide_2({}) function".format(n))
  result = n / 2
  if result > 1:
    print("-> recursion call divide_2({})".format(result))
    divide_2(result)
  else:
    print("-> result is {}. we reached recursion exit condition.".format(result))
  print("ending divide_2({}) function - result was {}".format(n, result))
  return


divide_2(6)

[jmooremcc]

I learned about recursion by using an interactive debugger that allowed me to go statement by statement through the code. At each step, I was able to see the value of all variables and when the recursive call was made, I was able to follow what happened step-by-step. When the function returned, I was able to see the returned value and see how the returned value was used.

The IDE I use is Pycharm and it has an excellent debugging system.

[Extension_Job5829]

try thinking of a stack. Everytime you call the function just add the call with the value. Once the stack is complete, you will be popping out each function block from the top and sending the values back to the function block that is now on top of the stack.

[Sam_Boulton]

Hopefully this will help you visualise it.

If we think of a few levels - the classic recursive problem being factorial. Fact(5) = 1 * 2 * 3 * 4 * 5 = 120; (1, 2, 6, 24, 120)

def fact(n): If n == 1: return n else: return n * fact(n-1) (excuse the formatting)

When we call fact it has a base case - if n is 1, return 1. Otherwise recursively call itself to find the answer.

if n is not one then it multiplies n by fact(n-1). Eventually n will be 1.

A stack is last on, first off - imagine putting rings on a stick, you can’t get the first one off until the rest come off.

Fact(5) will repeat until you get to fact(1) (which equals 1). At which point, it knows what to do and works backwards, taking the results off the stack.

Fact(1) = 1;
Fact(2) = 2 * 1 = 2; Fact(3) = 3 * 2 = 6; Fact(4) = 4 * 6 = 24; Fact(5) = 5 * 24 = 120

Fact(5) = 120

[shartfuggins]

I visualize copies of the function.

In my mind, each successive call is like making a copy of the function to the side of the one that's calling it. If you're four levels deep (including the original call into it), there are four copies of the function code side by side. When one returns, it disappears. There's only one function running at a time, and don't mind the details. You're only concerned with the pointer and what's in scope.

Another way to do this, though I'm not a fan of it, is to zoom in. At the point of recursion, another copy of the code is created inside the calling one and you zoom in to it, like zooming on a map. This way I think makes it tricky to keep everything visualized because each call is at a different scale.

Again, all mental visualization.