1

I'm working on a checkio.org problem and I've built a solution that uses recurssion, except when it runs on the 8th test I get this error:

RuntimeError: maximum recursion depth exceeded while calling a Python object, count_gold, 16, count_gold, 29, count_gold, 29, count_gold, 29, count_gold, 29, count_gold, 29, count_gold, 29, count_gold, 29, count_gold, 29, count_gold, 29, count_gold, 29, count_gold, 29, count_gold, 29, count_gold, 29, count_gold, 29, count_gold, 29, count_gold, 29, count_gold, 29, count_gold, 29, count_gold, 29, count_gold, 29, count_gold, 29,

I truncated the end off, but it continues for a good amount of time. I think this is a fundamental misunderstanding I have about the way recursion works. Initially I was very reluctant to post my code since I don't want to give away answers, but I think if I don't link the problem, then my code will just be lost in obscurity. So here we go:

def mystery_function(pyramid, perm=0, lastmax=0, result = [], running=False):

    if not running:
        result = []

    bitstr = bin(perm).zfill(len(pyramid)+1)
    bitstr = bitstr.replace("b","")

    j, newmax = 0, 0

    for i in range(len(pyramid)):

        j += int(bitstr[i])
        newmax += pyramid[i][j]

    maxpermute = "1"*(len(pyramid))
    result.append(newmax)

    if newmax < lastmax:
        nextmax = lastmax
    else:
        nextmax = newmax

    if perm < int(maxpermute,2):
        mystery_function(pyramid, perm+1, nextmax, result, True)

    return max(result)

So like I said, I think the problem is that I just simply don't fully understand recursion. I read this post: Python RuntimeError: maximum recursion depth exceeded but it doesn't seem to apply because my recursion will break down to the base case and stop.

Any ideas? For those interested (and know the problem based off my function), the recursion fails on test 8.

NOTE: in the function, "pyramid" is a tuple of tuples between 1 and 20 tuples long. We are supposed to travel through the "pyramid" to find that path that yields the largest sum and return that sum

Community
  • 1
  • 1
Djones4822
  • 577
  • 3
  • 6
  • 23
  • Have you tried `if perm < int(maxpermute,2): return mystery_function(pyramid, perm+1, nextmax, result, True)` – Chrispresso Mar 24 '15 at 15:47
  • 1
    Just a quick note about recursion: it's totally possible to exceed the maximum recursion depth even if your code would provably reach the base case eventually. Computer memory is finite, after all. – David Cain Mar 24 '15 at 15:49
  • @DavidCain yea I was worried about that. According to the input parameters, the max number of recursion possible to call is 2^20 which might just be too many. But if I was to use a loop, then I'd be creating a list of 2^20 elements which is just as bad, no? – Djones4822 Mar 24 '15 at 15:57
  • 2
    If you're getting started on recursion, it often helps to solve a smaller subset of the problem first... say, the first two or three levels of your tree / pyramid. If you're trying to find the *largest* sum, there's probably no way to avoid walking the whole tree. So don't worry about checking as you go (yet) but just build a solution that shows the sum of each possible path. Decompose the problem first, then optimize. – dylrei Mar 24 '15 at 15:58
  • 2
    I'm don't think this is the problem here, but be very careful creating a function with a default arg of `[]`, its a common gottcha for new python programmers: http://stackoverflow.com/questions/1132941/least-astonishment-in-python-the-mutable-default-argument – Matt Mar 24 '15 at 16:00
  • 2
    @Apc0243, the maximum recursion depth is somewhere around 1,000. A byte array of 2^20 elements is just 1 MiB, definitely not a problem for modern RAM. (Granted, a Python list of objects will take more memory, but considering simple arrays is a useful benchmark). – David Cain Mar 24 '15 at 16:01
  • 1
    @DavidCain ok, so maybe running this through a loop is better then, huh. I just tested it with a loop instead and it is much simpler and it works! Thanks David! – Djones4822 Mar 24 '15 at 16:17

1 Answers1

0

try this:

import sys
sys.setrecursionlimit(5000)

Python's limit is 1000 I believe

wa7d
  • 129
  • 1
  • 2
  • 12