🔒 Having trouble understanding how this recursion problem works | Python | Page 1

charred linden Oct 18, 2024, 4:51 AM

#

I don't understand

pale rivetBOT Oct 18, 2024, 4:51 AM

#

charred linden I don't understand

#

@charred linden

Python help channel opened

Remember to:

Ask your Python question, not if you can ask or if there's an expert who can help.
Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

verbal gull Oct 18, 2024, 4:52 AM

#

charred linden I don't understand

!code
hi please send text

pale rivetBOT Oct 18, 2024, 4:52 AM

#

Formatting code on Discord

Here's how to format Python code on Discord:

```py
print('Hello world!')
```

These are backticks, not quotes. Check this out if you can't find the backtick key.

For long code samples, you can use our pastebin.

charred linden Oct 18, 2024, 4:58 AM

#

    def helper(sum_so_far,index):
        if index == len(s):
            if sum_so_far == 100:
              return 1
            return 0
        return helper(sum_so_far,index + 1) + helper(sum_so_far + s[index],index + 1)
    return helper(0,0)```

#

sorry it took me so long

verbal gull Oct 18, 2024, 5:01 AM

#

charred linden sorry it took me so long

and what is your question about it?

charred linden Oct 18, 2024, 5:04 AM

#

i'm confused about how the recursion actually works, how does it go back up the recursion line? I understand that helper will go to helper(0,3) but afater that how does it go back up after doing helper(sum_so_far + s[2], 2+1)?

verbal gull Oct 18, 2024, 5:05 AM

#

what do you mean by go back up?

charred linden Oct 18, 2024, 5:11 AM

#

I plugged this into online pythong tutor to see the steps of the code and saw that hel,per had an instance where it was helper(random,2), meaning that the index was decremented somehow?

verbal gull Oct 18, 2024, 5:12 AM

#

what do you mean decremented?

index starts at 0 and goes up by 1 each time

charred linden Oct 18, 2024, 5:14 AM

#

are these the correct steps? helper(0,0) -> helper(0,1) -> helper(0,2) -> helper(0,3) -> returns 0 -> helper(0 + s[2], 3) -> helper(sum_so_far + s[1],2) -> helper(sum_so_far + s[0],1)?

verbal gull Oct 18, 2024, 5:15 AM

#

ok lets have a look

#

[25, 50, 75, 100, 125, 150]
with this data

#

helper(0,0) is called

len(s) == 6
so the condition is False

#

then it calls helper(0, 1) + helper(25, 1)

charred linden Oct 18, 2024, 5:18 AM

#

that's where I'm confused, I thought the first recursive call needs to be run completely before moving on to the other recursive call?

verbal gull Oct 18, 2024, 5:19 AM

#

you add each of them step by step

charred linden Oct 18, 2024, 5:20 AM

#

oh ok so it would be 0+0 for the first step?

#

because sum_so_far for both doesn't equal 100?

verbal gull Oct 18, 2024, 5:21 AM

#

helper(0, 0)
helper(0, 1) + helper(25, 1)
helper(0, 2) + helper(50, 2) and helper(25, 2) + helper(75, 2)

charred linden Oct 18, 2024, 5:22 AM

#

this part confuses me, helper(25, 2) + helper(75, 2)

#

how come the two isn't equal to 3?

verbal gull Oct 18, 2024, 5:22 AM

#

it's called with 25 right?

charred linden Oct 18, 2024, 5:23 AM

#

yeah

verbal gull Oct 18, 2024, 5:23 AM

#

and the second index is 50
so sum_so_far25 + s[1]50

charred linden Oct 18, 2024, 5:24 AM

#

ohhhh

#

so helper(25,2) makes sum_so_far equal to 25 for the next recursive call

verbal gull Oct 18, 2024, 5:24 AM

#

yes

charred linden Oct 18, 2024, 5:25 AM

#

I'm confused about what happens when sum_so_far is equal to 100, I somewhat understand that the value 1 is returned but not sure what happens after this?

verbal gull Oct 18, 2024, 5:26 AM

#

since it returns, that line of recursion is done

#

there are a lot of recursions happening at the same time

charred linden Oct 18, 2024, 5:27 AM

#

what happens if sum_so_far exceed 100?

verbal gull Oct 18, 2024, 5:27 AM

#

charred linden what happens if sum_so_far exceed 100?

it returns 0

#

when all recursions are done, each of them returns either a 0 or a 1

#

they get added 1 + 0 + 1...

charred linden Oct 18, 2024, 5:29 AM

#

With the given data what happens first, 100 returning 1 or 25 + 75 returning 1?

verbal gull Oct 18, 2024, 5:29 AM

#

they both happen
i'm not sure of the order

charred linden Oct 18, 2024, 5:31 AM

#

oh ok I think I'm starting to understand it more and more, I'm going to continue playing around with the values I use for s, I appreicate your help!

verbal gull Oct 18, 2024, 5:32 AM

#

charred linden oh ok I think I'm starting to understand it more and more, I'm going to continue...

printing stuff will help
tho this is a big recursion and a bit hard to unravel

charred linden Oct 18, 2024, 5:33 AM

#

Thank you I will try this problem with a smaller list of values, s, and print out the results

pale rivetBOT Oct 18, 2024, 6:33 AM

#

Python help channel closed

This help channel has been closed and it's no longer possible to send messages here. If your question wasn't answered, feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.

#🔒 Having trouble understanding how this recursion problem works