ya_hossein's blog

By ya_hossein, history, 6 weeks ago, In English

in the name of god

i'm new to python and i write recursion function in it for solving this problem and i get runtime error on test 5.

why recursion function in python gets runtime error?

its ok in c++.

thanks for your helping!

 
 
 
 
  • Vote: I like it
  • -6
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ya_hossein (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ya_hossein (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ya_hossein (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

The default limit on recursive calls in Python is 1000 or 10000. You can increase it by calling sys.setrecursionlimit(...).

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks so much

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i don't know why but after adding sys it doesn't work. here is my submission

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It seems to be working on ideone (code) but gives Runtime Error on Custom Invocation [I am guessing the testcase's input based on whatever is visible on the submission page, i.e., an alternating sequence of 1s and 10^9s followed by an alternating sequence of 10^9s and 1s (because test 13 for that problem has the same pattern but with 1s and 4s)]. I am guessing that the max recursion limit on Codeforces depends on other programs running on the same machine. I tried multiple runs with the recursion limit of 1315, and sometimes I got return code 1, other times I got return code as a large negative number (which I guess points to a segmentation fault).

»
6 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Further to the comments about recursion limits, you may also find that even changing the max depth does not solve your problem. I certainly had that experience.

I found a solution in this thread and specifically this comment — it turns your recursion function into a non-recursive stack implementation.

Note that all recursions can be achieved using stacks instead, and (using DFS as an example), it is possible to code a DFS recursion using stacks instead, thus eliminating any concerns.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

it doesn't work after using bootstrap...

did i forget something?

here is link

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When you call the function from within itself, you must precede the call with "yield", so the correct version looks like this:

    arr1[x] = num1[x] + max((yield(ans0(x + 1))), (yield(ans0(x + 2))))

    and the same for your other function

»
6 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

The solutions are not equivalent.

When they are, the next thing is to learn to increase stack size in Python. You can refer here for an example.