FAQ: Recursion: Python - Sum to One with Recursion

I don’t understand how does the variable “n” store value 28 when it reaches base

Me neither man, I cannot understand which part is adding all the returns in a call stack together.

It’s extremely annoying, that you already wait over two months for a response (moderators are volunteers so it’s understandable that you sometime might wait, it’s something they are doing nonprofit so I appreciate their work) but anytime you try contacting help with some question about a course their answer is “go to the forum, someone will answer your question there”. But if they don’t actually employ some people to do it, this advice is not very good.

It doesn’t.

If you can figure out what the sum of 1…6 is, then it is trivial to find the sum of 1…7 because you’d figure out the sum of 1…6 and then add 7

questions made in already existing threads are unlikely to be seen

Also, you’ve got print, with which you can write out what’s being done as it is happening.

Well, print is kinda unavailable for me since I get syntax error every time I try to execute the code, I cannot even debug it in python tutor since instead of executing step by step it just raises “syntax error” and that’s it :confused:

That’s my code, error is in line 6:

def sum_to_one(n):
  if n == 1:
    return n
  else:
    print("Recursing with input: {0}".format(n)
    return n + sum_to_one(n-1)

make sure the syntax is valid then I guess?
and if you’re completely unable to spot such issues then remove some code and add it back one small part at a time, running between each edit to make sure it’s still valid

Ok, found the missing parenthesis :smiley: But I still have no idea wheres the 28 coming from, my code looks like this:

def sum_to_one(n):
  print(n)
  if n == 1:
    print(n)
    return n
  else:
    print("Recursing with input: {0}".format(n))
    print(n)
    return n + sum_to_one(n-1)    
# uncomment when you're ready to test
print(sum_to_one(7))

And this is my return:

7
Recursing with input: 7
7
6
Recursing with input: 6
6
5
Recursing with input: 5
5
4
Recursing with input: 4
4
3
Recursing with input: 3
3
2
Recursing with input: 2
2
1
1
28

When the code gets to base case n==1 it returns n, which is 1, not 28 so how am I getting 28 here? Value of n is getting smaller and smaller but theres no addition going on. Whats more is that in the if loop print(n) is printing 1 but return n returns 28, so realy, I’m confused as to whats happening.

told you where it comes from (also it says in the code how the return value is obtained)

You’re also only doing addition in one place, so you might want to look at what additions are being made there. (though, I said what)

Or treat it as math, expand the functions, you’ll end up with
(7 + (6 + (5 + (4 + (3 + (2 + (1)))))))

1 Like

Oh, so that’s what stack looks like in regular math. Somehow the way it was explained I misunderstood it and thought that every step is more separate, like now n is 7, now it’s 6 and didn’t realize that those previous calls are still stored. We were thaught about stack call but I think I didn’t really get it until now. Thanks!

So:

while n > 1:
 return n + function(n-1)

this is basically saying return n plus every integer from n to 1 inclusive. Only when I looked at it this way I understood how the last in first out works, and how we can get our final sum thanks to this mechanism.

So when last call is executed and function iterations start passing their return values to their “parent” iterations it means that the previous iterations up to this point were actually stored somewhere? Does that mean that when you accidentally let stack grow too big it might cause problems with memory?

1 Like

There’s no stack in that. Only rewriting. It is sum_to_one(7) but with each use of sum_to_one replaced with its definition. Replace each use of a function with its definition.

sum_to_one(1) is defined as 1
sum_to_one(2) is defined as 2 + (sum_to_one(1)), make the replacement from before, get 2 + (1), and so on.

Here’s the same function in haskell (this is valid, executable code)

sum_to_one 1 = 1
sum_to_one x = x + sum_to_one (x - 1)

The thing on the left side of = can be replaced with the thing on the right side, that is what = means, that each can be replaced with the other, that they are equivalent.

Because those are expressions, you can expand each use of sum_to_one directly with its definiton

sum_to_one 10            <- start with this, replace according to the function definiton
10 + sum_to_one 9        <- after one replacement you have this. keep going.
10 + 9 + sum_to_one 8
10 + 9 + 8 + sum_to_one 7
... look at what's left behind as the replacements are made.
10 + 9 + 8 + 7 + sum_to_one 6
10 + 9 + 8 + 7 + 6 + sum_to_one 5
2 Likes

In any case you’re not interacting with a stack any more than when you call any other function.

So instead think of it as solving a smaller problem and then with the help of that solution, solving the current problem.

convince yourself of that this is correct:

sum_to_one(10) = 10 + sum_to_one(9)

It doesn’t matter what sum_to_one(9) does. The point is that you can call it, and when you get the result back you can solve the problem.
The only thing you do need to ensure is that the problem is closer to a base case, if the problem does not get smaller then it would never hit the base, there would never be a result that can be used to solve the larger problems.

1 Like

If you really wanted to do recursion with a stack then you would be implementing function calling yourself.
That means being able to put a value representing resume-running-from-here on the stack.

I made an example of it. This is recursive, but it does not use python’s call stack, instead it implements its own.

calling a function involves adding the current location to the stack, along with the arguments to the function

similarly, the return value is put on the stack before a routine exits, so that the caller can find that value on the top of the stack after calling a routine

that’s why yield is there. it is used to suspend execution to obtain a value from which execution can be resumed at that same location. this value is placed on the stack so that it gets executed again when the called routine finishes

def sum_to_one(n):
    # create a stack and operations for it
    stack = []
    push = stack.append
    pop = stack.pop
    peek = lambda: stack[-1]
    size = stack.__len__
    def swap2():
        stack[-2:] = reversed(stack[-2:])

    # the recursive routine
    def sum_to_one():
        # base case does nothing - the result is the same as the argument, so
        # leave it on the stack and return
        if peek() == 0:
            swap2()
            yield

        # recursively call self by putting self and the argument on the stack
        push(peek() - 1)
        push(self)
        swap2()
        push(sum_to_one())
        yield
        # then add the result to the argument by popping both and putting the
        # result back to onto the stack
        push(pop() + pop())
        swap2()
        yield

    push(n)
    push(sum_to_one())

    # execute the stack
    while size() > 1:
        print([item if type(item) is int else item.__name__ for item in stack])
        self = pop()  # global variable referring to the current routine
        next(self)  # run it until it yields

    # final result found on the stack
    return peek()


print(sum_to_one(1))
print(sum_to_one(7))
print(sum_to_one(8))

I’m printing out the stack each time a routine is about to be called.

Keep in mind that the top of the stack is the end, not the beginning, because the stack is a list, and a list does operations at the end.

There’s only one routine. It has two parts, because it suspends. The first part puts the current value on the stack and calls itself recursively. While this part is running, the stack will grow.

The second part looks the same on the stack, because it’s the same routine, but it’s the second part of it, this part adds two numbers, this causes the stack to shrink again, because it pops two numbers and puts one back, it gets smaller. Note that there will be two adjacent numbers in the stack while this is happening, those are what will be added.

Because all intermediate values are put on the stack, you can also see where 28 “comes from”, because after each addition the result is put back on the stack.

fibonacci is a bit more difficult, because there are two recursive calls in the recursive case.

    def fib():
        if peek() in [0, 1]:
            # base case, result same as input, leave it on the stack
            swap2()
            yield

        # obtain fib(n-1) and fib(n-2) through recursion

        # put self to the stack as the return location
        # put n-1 as the argument
        # put fib as the next routine to run (recurse)
        # suspend (yield) to continue executing from the stack
        push(peek() - 1)
        push(self)
        swap2()
        push(fib())
        yield

        # stack now has fib(n-1) and arg, swap them to bring arg to the top
        swap2()

        # then do the same again for n-2
        push(peek() - 2)
        push(self)
        swap2()
        push(fib())
        yield

        # bring the arg to the top again, and discard it
        swap2()
        pop()

        # add the two results, putting the sum back on the stack
        push(pop() + pop())

        # done. fib(n) is now the top of the stack (the return value)
        swap2()
        yield

The stack shown over time gets a more interesting shape than just a pyramid like is the case with single recursion.

[7, 'fib']
[7, 'fib', 6, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 4, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 4, 'fib', 3, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 4, 'fib', 3, 'fib', 2, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 4, 'fib', 3, 'fib', 2, 'fib', 1, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 4, 'fib', 3, 'fib', 2, 1, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 4, 'fib', 3, 'fib', 1, 2, 'fib', 0, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 4, 'fib', 3, 'fib', 1, 2, 0, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 4, 'fib', 3, 1, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 4, 'fib', 1, 3, 'fib', 1, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 4, 'fib', 1, 3, 1, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 4, 2, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 2, 4, 'fib', 2, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 2, 4, 'fib', 2, 'fib', 1, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 2, 4, 'fib', 2, 1, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 2, 4, 'fib', 1, 2, 'fib', 0, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 2, 4, 'fib', 1, 2, 0, 'fib']
[7, 'fib', 6, 'fib', 5, 'fib', 2, 4, 1, 'fib']
[7, 'fib', 6, 'fib', 5, 3, 'fib']
[7, 'fib', 6, 'fib', 3, 5, 'fib', 3, 'fib']
[7, 'fib', 6, 'fib', 3, 5, 'fib', 3, 'fib', 2, 'fib']
[7, 'fib', 6, 'fib', 3, 5, 'fib', 3, 'fib', 2, 'fib', 1, 'fib']
[7, 'fib', 6, 'fib', 3, 5, 'fib', 3, 'fib', 2, 1, 'fib']
[7, 'fib', 6, 'fib', 3, 5, 'fib', 3, 'fib', 1, 2, 'fib', 0, 'fib']
[7, 'fib', 6, 'fib', 3, 5, 'fib', 3, 'fib', 1, 2, 0, 'fib']
[7, 'fib', 6, 'fib', 3, 5, 'fib', 3, 1, 'fib']
[7, 'fib', 6, 'fib', 3, 5, 'fib', 1, 3, 'fib', 1, 'fib']
[7, 'fib', 6, 'fib', 3, 5, 'fib', 1, 3, 1, 'fib']
[7, 'fib', 6, 'fib', 3, 5, 2, 'fib']
[7, 'fib', 6, 5, 'fib']
[7, 'fib', 5, 6, 'fib', 4, 'fib']
[7, 'fib', 5, 6, 'fib', 4, 'fib', 3, 'fib']
[7, 'fib', 5, 6, 'fib', 4, 'fib', 3, 'fib', 2, 'fib']
[7, 'fib', 5, 6, 'fib', 4, 'fib', 3, 'fib', 2, 'fib', 1, 'fib']
[7, 'fib', 5, 6, 'fib', 4, 'fib', 3, 'fib', 2, 1, 'fib']
[7, 'fib', 5, 6, 'fib', 4, 'fib', 3, 'fib', 1, 2, 'fib', 0, 'fib']
[7, 'fib', 5, 6, 'fib', 4, 'fib', 3, 'fib', 1, 2, 0, 'fib']
[7, 'fib', 5, 6, 'fib', 4, 'fib', 3, 1, 'fib']
[7, 'fib', 5, 6, 'fib', 4, 'fib', 1, 3, 'fib', 1, 'fib']
[7, 'fib', 5, 6, 'fib', 4, 'fib', 1, 3, 1, 'fib']
[7, 'fib', 5, 6, 'fib', 4, 2, 'fib']
[7, 'fib', 5, 6, 'fib', 2, 4, 'fib', 2, 'fib']
[7, 'fib', 5, 6, 'fib', 2, 4, 'fib', 2, 'fib', 1, 'fib']
[7, 'fib', 5, 6, 'fib', 2, 4, 'fib', 2, 1, 'fib']
[7, 'fib', 5, 6, 'fib', 2, 4, 'fib', 1, 2, 'fib', 0, 'fib']
[7, 'fib', 5, 6, 'fib', 2, 4, 'fib', 1, 2, 0, 'fib']
[7, 'fib', 5, 6, 'fib', 2, 4, 1, 'fib']
[7, 'fib', 5, 6, 3, 'fib']
[7, 8, 'fib']
[8, 7, 'fib', 5, 'fib']
[8, 7, 'fib', 5, 'fib', 4, 'fib']
[8, 7, 'fib', 5, 'fib', 4, 'fib', 3, 'fib']
[8, 7, 'fib', 5, 'fib', 4, 'fib', 3, 'fib', 2, 'fib']
[8, 7, 'fib', 5, 'fib', 4, 'fib', 3, 'fib', 2, 'fib', 1, 'fib']
[8, 7, 'fib', 5, 'fib', 4, 'fib', 3, 'fib', 2, 1, 'fib']
[8, 7, 'fib', 5, 'fib', 4, 'fib', 3, 'fib', 1, 2, 'fib', 0, 'fib']
[8, 7, 'fib', 5, 'fib', 4, 'fib', 3, 'fib', 1, 2, 0, 'fib']
[8, 7, 'fib', 5, 'fib', 4, 'fib', 3, 1, 'fib']
[8, 7, 'fib', 5, 'fib', 4, 'fib', 1, 3, 'fib', 1, 'fib']
[8, 7, 'fib', 5, 'fib', 4, 'fib', 1, 3, 1, 'fib']
[8, 7, 'fib', 5, 'fib', 4, 2, 'fib']
[8, 7, 'fib', 5, 'fib', 2, 4, 'fib', 2, 'fib']
[8, 7, 'fib', 5, 'fib', 2, 4, 'fib', 2, 'fib', 1, 'fib']
[8, 7, 'fib', 5, 'fib', 2, 4, 'fib', 2, 1, 'fib']
[8, 7, 'fib', 5, 'fib', 2, 4, 'fib', 1, 2, 'fib', 0, 'fib']
[8, 7, 'fib', 5, 'fib', 2, 4, 'fib', 1, 2, 0, 'fib']
[8, 7, 'fib', 5, 'fib', 2, 4, 1, 'fib']
[8, 7, 'fib', 5, 3, 'fib']
[8, 7, 'fib', 3, 5, 'fib', 3, 'fib']
[8, 7, 'fib', 3, 5, 'fib', 3, 'fib', 2, 'fib']
[8, 7, 'fib', 3, 5, 'fib', 3, 'fib', 2, 'fib', 1, 'fib']
[8, 7, 'fib', 3, 5, 'fib', 3, 'fib', 2, 1, 'fib']
[8, 7, 'fib', 3, 5, 'fib', 3, 'fib', 1, 2, 'fib', 0, 'fib']
[8, 7, 'fib', 3, 5, 'fib', 3, 'fib', 1, 2, 0, 'fib']
[8, 7, 'fib', 3, 5, 'fib', 3, 1, 'fib']
[8, 7, 'fib', 3, 5, 'fib', 1, 3, 'fib', 1, 'fib']
[8, 7, 'fib', 3, 5, 'fib', 1, 3, 1, 'fib']
[8, 7, 'fib', 3, 5, 2, 'fib']
[8, 7, 5, 'fib']
13

I suppose one might want to display something other than ‘fib’ since the fibs are in different locations in the fib routine, but I think it’s fine if it is read as “resume fib”

4 Likes

Thanks for detailed explanation, I understood some of it but I bookmarked it so I can come back here couple of months from now and then try to get it all : P

The idea with a stack and calling is that the current things on the stack do not get touched.

When a function begins running, it can put things on the stack as working memory, but when it’s done, it will have removed all of it, meaning the stack is left exactly the way as it was, except for the return value.

Each piece of code is therefore only concerned with a few things at the top of the stack. The overall thing may be difficult to follow, but each individual use of it is simple.

But when reasoning about recursion you probably generally ignore how the full thing plays out. Don’t pay attention to what a function will end up doing, instead consider what the result is and how you can use it. You know that if you call a function you’ll get some result. So the concern should be what to do with the result, not what the function did, that’s not interesting.

So you should only consider a single “level” at a time:
the sum of numbers 1..7 is sum(1..6) + 7, and the sum of 1..1 is 1
that’s all you should care about.

same with fib…

fib(n) is fib(n-1) + fib(n-2) and fib(0) is 0 and fib(1) is 1

same with tower of hanoi. to move a stack, move all but the last ring to the peg you don’t want to move the stack to. then move the big ring to the peg you want to move to. then move the other rings on top of it. <-- this is executable, believe it or not

Hello, why would we put “0” into the
print("Recursing with input: {0}".format(n))’ statement?
Thank you.

It’s a method of controlling the formatting a little further, if we wanted repeats or a little more control over the placement. A very quick example below-

a = 'red'
b = 'blue'
print("We pass two colours, {1} and {0}. Order is important for {0} and {1}.".format(a, b))

Numbers can get quite confusing though, so consider when they’re actually appropriate instead of names.

So basically (0 and 1) are indices from parentheses of “.format(a, b)”. a = 0, b = 1 ?

1 Like

Yes, sorry that was a bit brief but you’re quite right, it is indexing. For something a bit more complex naming them properly might be worthwhile- '{name}'.format(name=myvariable) so that it remains readable since numbers alone are hard to decipher; or consider f-strings for Python3: print(f'Recursing with input: {n}')

1 Like

Hi I’m confused on how the code works? I’ve added some print statements which ended up confusing me about the order that the code runs
Couple of questions:

  1. Why is it printing all the first print statements then all the second as I thought it would stagger them?
  2. How do you come up with the first answer of 3?? Thought the first answer would be 7 + 7 - 1

Sorry but obviously missing some basic understanding of how it works
Thanks for your time
Nathan

def sum_to_one(n):
if n == 1:
return n
print(’“n” value is = {}’.format(n))
answer = n + sum_to_one(n - 1)
print('answer = ', answer)
return answer

print(sum_to_one(7))

Results
“n” value is = 7
“n” value is = 6
“n” value is = 5
“n” value is = 4
“n” value is = 3
“n” value is = 2
answer = 3
answer = 6
answer = 10
answer = 15
answer = 21
answer = 28
28

If you’re posting code to the forums, please see the following and format it as it can be very hard to read otherwise- How do I format code in my posts?

You have a function call before your second print, so you enter the function, print the first line and then the function is called again and you effectively move to the start of the function again (with an altered n value) and just start adding to your call stack with decreasing values of n.

So there’s no staggered print because until n == 1 the second print is not reached. Hopefully that part is clear?

Let’s start again from the point where the recursion ends, that is when n == 1 is passed as an argument to this function. In order to pass 1 as an argument the function call would’ve had to be sum_to_one(2 - 1) as that would be the only way to pass n == 1 as an argument (in this example).

That call sum_to_one(2 - 1) would’ve required n == 2 and the whole line would’ve been answer = 2 + sum_to_one(2 - 1), the return of sum_to_one in that case is 1 and answer therefore evaluates to 3.
answer = 2 + sum_to_one(2 - 1) evaluates to answer = 3
So the first answer value you print is 3.

Then you’d be moving through your call stack. The previous line had n == 2 so the next call on the stack obviously had n == 3 and we already know the returned value was 3, so you have answer = 3 + 3.

Is the order a little clearer now?

Yeah, clearer now thanks.