Why is my recursive function won't work and why do I get strange results

Question

I need to write a code that will take a string of numbers and find consecutive 5 digits that will give me the highest possible number (as in 9328498503734 the answer will be 9850374).

x = 0    
def solution(digits):
    global x 
    if len(digits) < 5:
        return x
    else:
        if int(digits[0:5]) > x:
            x = int(digits[0:5])
        solution(digits[1:])

My idea was to do it with recursive function - check if the length of the input is not less than 5, if not, then check if the current 5 digits are the biggest number. If so, this number becomes new x, and function gets repeated but without the first digit until the base case is missed.

So my first problem is how to do this without a global variable? I heard they are shunned but when I was writing previous recursive code and used any variable inside that function it got reset every time.

My next problem is that this function returns None and I have no idea why? Also, when I tried to put "print (len(digit))" over global x for each recursion, I can see what's going on! Instead of returning 'None' it raises "RuntimeError: maximum recursion depth exceeded while calling a Python object" and I have no idea why? Although, without this counter, I have None as a return.

So, how to do it without a global variable and why does my code change it's behavior so much over a simple print statement?
Your help would be appreciated!

EDIT: Ok, I was getting None, because I tried to call function from inside function, but I forgot that it has to be called with "return", not just like that, like I would do it outside a function.

Big thank you to the user below who told me that I can carry ariable in a function by placing this variable in function parenthesis. I would definitely not recommend Codecademy, as it omits such simple and important thing, giving only very basic and incomplete knowledge of the topic. I finished their Python course, all exercises and this is how much I know after this :/

`return solution(digits[1:])`....And there are still some errors in your code. — jizhihaoSAMA, Jun 02 '20 at 16:02
"consecutive **5** digits"..."9328498503734 the answer will be 9850374" That's 7 digits. Did you mean 98503? — hundredrab, Jun 02 '20 at 16:10
Ok, now when you point it I think I see it, every iteration it's going to use the same strings. So I have no clue what to do, I tried digits.replace(digits[0], "") solution(digits) But then when I added counter it showed that every recursion lenght of my input is the same, like replace didn't work at all :( hundredab, yes — Jan Kowalski, Jun 02 '20 at 16:14

score 1 · Accepted Answer · answered Jun 02 '20 at 16:06

1

Instead of using a global variable, pass x 'along' when you call the function. By setting it to have a default value of 0 it doesn't need to be passed in at the start:

def solution(digits, x=0):
    if len(digits) < 5:
        return x
    else:
        if int(digits[0:5]) > x:
            x = int(digits[0:5])
        return solution(digits[1:], x)

print(solution('9328498503734'))
98503

answered Jun 02 '20 at 16:06

match

10,388
3
23
41

Oh my goodness, this is so simple and fantastic, I wish they thaught it on Codecademy instead of giving me knowledge full of holes like this. – Jan Kowalski Jun 02 '20 at 16:32

Samwise · Answer 2 · 2020-06-02T16:32:41.290

1

Typically to make a recursive function work, you need to return some kind of combination of a base result with the result of another recursive call on a reduced version of the original argument. Using globals is usually going to be self-defeating because all the recursive calls will overwrite each other (there's a reason using globals is "shunned", it's because it usually makes your code not work, lol).

>>> def solution(digits: str) -> str:
...     """Returns the 5-digit substring of digits with the highest int value."""
...     if len(digits) <= 5:
...         return digits
...     else:
...         return max(digits[:5], solution(digits[1:]), key=int)
...
>>> solution("9328498503734")
'98503'

edited Jun 02 '20 at 16:32

answered Jun 02 '20 at 16:06

Samwise

68,105
3
30
44

What is a base result? – Jan Kowalski Jun 02 '20 at 16:09
The "base case" is the super easy one, the one where the input is so simple that the answer is obvious without further recursion. In this example, it's the `len(digits) <= 5` case -- if there are only 5 digits, there's only one possible subset of them, so you can just return that. Every other solution is just the `max` of the first 5 digits and the `solution` of all the digits after the first one (i.e. a slightly shorter string of digits that will eventually reach the base case). – Samwise Jun 02 '20 at 16:11
Oh, I didn't know base case and base result is the same – Jan Kowalski Jun 02 '20 at 16:16
Wait, if I do len(digits) <= 5 then wouldn't the code skip the last 5 digits, without comparing them to the rest? – Jan Kowalski Jun 02 '20 at 16:23
No, because you are `return`ing the digits, whereupon the caller will compare them to the previous 5 digits using `max`. (And then that caller will return that maximum, whereupon **its** caller will do another comparison, and on and on.) This is why returning instead of using a global is key; each invocation of the function is going to return a potentially different result, and you need to be able to have both results as different values to be able to compare them! If everything is stored in the same global it's difficult to make that work. – Samwise Jun 02 '20 at 16:25

Gwang-Jin Kim · Answer 3 · 2020-06-02T16:26:37.180

0

def max_5_digits(digits, _max=0):
    return _max if len(digits) < 5 else max_5_digits(digits[1:], max(_max, int(digits[:5])))

max_5_digits("9328498503734")                                                                                                                                                                           
## 98503

edited Jun 02 '20 at 16:26

answered Jun 02 '20 at 16:15

Gwang-Jin Kim

9,303
17
30

This is not answering any question, this is just straight up giving me solution and different than I'm looking for. Thanks, but I want to learn. – Jan Kowalski Jun 02 '20 at 16:18
@JanKowalski the only trick is: `A if cond1 else B` - one-liner if-else in python. The other trick is: max() to save one if-else condition. – Gwang-Jin Kim Jun 02 '20 at 16:20
@JanKowalski Ah and you save global var by using optional argument ` _max` which "carry over" memory about `_max` value over the function calls. And at the same time this function fulfills criteria of functional programming (referential transparency): (same argument input should give always the same output). – Gwang-Jin Kim Jun 02 '20 at 16:22

Why is my recursive function won't work and why do I get strange results

3 Answers3