Improving the algorithm there was a question about the behavior of the interpreter. It shuts up without messages and reboots. Here is an intermediate print code that you can skip for now. The essence of the issue in the texts:

import time import sys import functools from math import sqrt #print(f' sys.getrecursionlimit()={sys.getrecursionlimit()}') i=0 sys.setrecursionlimit(10000) @functools.lru_cache() def f(x): global i i +=1 if i%250==0: print(i) if x <=1: return 0 return 1 + min([ f(m + x // m - 2) for m in range(1,int(sqrt(x))+1) if x%m==0]) x = int(input("дай целое!")) t0 = time.clock() print( f(x)) t1 = time.clock() print (t1-t0, ' i=', i)

here's what is strange: when you type for example 1024, it completely works out and produces the following:

 дай целое!1024 250 500 750 ... 3250 3500 7 0.12052656332407201 i= 3636

that is, answer 7 is obtained in 3636 iterations in 0.12 seconds, and when you enter the number 1040, it shuts up without the words “on 1000+ recursions!?!

 дай целое!1040 250 500 750 1000 =============================== RESTART: Shell ===============================

In this regard, two questions
1) why so
2) how to test / debug recursive functions in general in the absence of at least some message from the interpreter?

Insulting addition: but in MS VS Python - where GIL is disabled - the algorithm works "through time". That is, a “clean” Python ALWAYS shuts up on the number 1040, and the same Python from MS VS 2017 - it gives the result, and then it “hangs” on the same 1000+ recursions. How is this possible and how to overcome, if it then believes that it does not count and hangs without words? enter image description here enter image description here

  • You can put a condition and breakpoint inside a function only if it is met - Vladimir Martyanov
  • one
    1- maxsize = None in lru_ cache () 2- [] inside min is not needed. - jfs

1 answer 1

Let's start in order.

I tested your code on myself, but the truth is under Linux. It ceased to work out after entering 2500. At the same time, it fell with a large spectra (as expected). After I raised the size of the recursion to 100,000, I began to receive and process 6000 (but I did not wait for an answer). At 7000 or more, it falls with a segmentation error (this should be viewed separately, and this is similar to your last screenshot).

The global variable i, which "supposedly considers the depth of recursion," actually counts the number of calls to the function f() . At each level of recursion, the function recursively calls itself many times. That is, the call graph is like a tree. And if you make two calls on each call, then there will be only 1024 calls per 10 nestings. And if you do 10, then 1 with ten zeros. This actually explains your misunderstanding.

That is, once again, almost everywhere where you write "this is such an iteration" or "at this level of recursion," you need to read "with such a number of calls." To calculate the recursion level correctly, you need to decrease i by 1 when exiting the function.

How to test / debug recursive functions in general in the absence of at least some message from the interpreter?

Apparently you need to use the "interpreter" :). I think that most likely the studio has additional limiters. In the case of c ++, I was able to use a simple program (which just created threads in a loop) to get the studio into a complete freeze.

That is, a “clean” Python ALWAYS shuts up on the number 1040, and the same Python from MS VS 2017 - it gives the result, and then it “hangs” on the same 1000+ recursions.

And here everything is very simple. In the case of pure python, you have a pure experiment. That is, the input is almost always identical. But in the case of the studio is not. It is possible that the studio on its goals (for example, indexing or checking updates) "ate" a little memory ... and that's it.

  • I ate some memory - and this made it possible to work where pure Python hangs? Seriously? Thank you for the work done. I posted this question on the python.org website. They said that the whole problem is that on Windows, under the application stack, allocate 2 MB to any application, and on Linux - 8, and this parameter is adjustable. I found how to change the size of the stack in Windows for python.exe in EXE hands. But - the question remains - how to look for an error even with the help of an interpreter? If he didn’t even bark when he fell? - Vasyl Kolomiets
  • I have never written the phrase "depth of recursion" anywhere. I understand how my program works and what exactly is calculated in "i". But do not despair. The recursion depth of more than 8 per 1000 is not met. That's the joke) - Vasyl Kolomiets
  • maybe you can still answer the questions: 1) how is it that it falls without a message? 2) How to catch this situation by means of Python? How to understand what exactly is due to the Python stack? what intermediate stack size checks can? - Vasyl Kolomiets
  • Under my Linux he swears and how. With a great spectrum. But under Windows somewhere, the system is hiding ... We must look for it. But when the interpreter crashes ... here the interpreter will not help. Here you need to pick up gdb and watch. As for the stack, it used to be over a megabyte. And now I checked it under Linux - yes, they give 8 already. But maybe this is because of the 64bit architecture. - KoVadim pm
  • one
    I retested. The recursion depth is usually greater than the input number. For 1000 it turned out 1000. For 2000 it turned out 6332. - KoVadim