Detecting repeated subsequences of identical items

[Steven D'Aprano]

On Fri, 22 Apr 2016 12:12 am, Chris Angelico wrote:

> On Fri, Apr 22, 2016 at 12:01 AM, Oscar Benjamin
> <oscar.j.benjamin at gmail.com> wrote:
>> In the recursive stack overflow case what you'll usually have is
>>
>> 1) A few frames leading up to the start of recursion
>> 2) A long repetitive sequence of frames
>> 3) A few frames at the end showing how the exception was ultimately
>> triggered.
>>
>> You just need to find the cycle that makes that big long sequence.

I am not convinced that it is a cycle in the technical sense, or that the
two algorithms that Oscar linked to will necessarily find them. They may,
by chance, happen to find them sometimes, but the way the algorithms work
is by detecting periodic behaviour, and this is not periodic.

Look at the comment for Floyd's algorithm here:

https://en.wikipedia.org/wiki/Cycle_detection

    # The hare moves twice as quickly as the tortoise and
    # the distance between them increases by 1 at each step.
    # Eventually they will both be inside the cycle and then, ...


but that is violated in this scenario. The hare can escape the (non-)cycle
before the tortoise even enters it. Even if both enter the "cycle", there's
no guarantee that the termination condition `tortoise == hare` will ever be
true because the cycle doesn't loop and doesn't go back to the beginning.
Hence it is not a cycle.

 
> If the stack got overflowed, there won't usually be a part 3, as part 
> 2 is the bit that hits sys.recursionlimit (unless increasing the
> recursion limit by a finite number would solve the problem). 

Don't just think of breaking the recursion limit. You might be 100 calls
deep in some complex chain of function calls when something raises
ValueError. In principle, there might not even be any recursive calls at
all.


-- 
Steven