Re: An algorithm problem

On 31/05/2006 7:20 PM, Bo Yang wrote:
I am sorry , and thanks for your friendliness .
I have change my source code for more meaningful variable name and more comments follow the instructions
John has writen . I think that is useful for you to look my code .

And this time I put the code in the attachment . Indeed , I write that in the Eclipse Pydev , I don't know why
it lose its idention in the mailing list .

Also , I forget an example for the question , and I compensate for it :

Given the integer 2 for instance :
what we exapct from the algorithm is a list of 0 or 1 , for this instance it is 1 1 0 0 .
We can take it as a ring , and fetch any continuous 2 numbers from it , finally get four combinations :
11 , 10 , 00 , 01
and they are 3 , 2 , 0 , 1 .


I hope this time it is clear for all to understand what problem confront me .
And again I am sorry for the trouble , thanks for you again !


OK, it was able to be run this time. The algorithm is recursive. For input == n, it needs stack of depth 2**n. The default limit is 1000, and 2**9 < 1000 < 2**10 -- so it fails when n >= 10. You can change this with sys.setrecursionlimit. Please take careful note of the warnings in the documentation:

"""
setrecursionlimit( limit)

Set the maximum depth of the Python interpreter stack to limit. This limit prevents infinite recursion from causing an overflow of the C stack and crashing Python.
The highest possible limit is platform-dependent. A user may need to set the limit higher when she has a program that requires deep recursion and a platform that supports a higher limit. This should be done with care, because a too-high limit can lead to a crash.
"""

I tried it with sys.setrecursionlimit(2**n+10) -- that worked up to 13 on my Windows XP box, throwing a MemoryError (and a long stack trace!) for n == 14. Be careful; yours may crash more horribly than that.

Can your algorithm be expressed non-recursively?

Best of luck,
John
.

Relevant Pages

  • Re: coerce for arbitrary types
    ... the algorithm itself is essentially last-in first-out, ... via some sort of recursion? ... WaitStack <= new stack containing topnode ... As nested lists, there's only one number in a proper position. ...
    (comp.lang.lisp)
  • Re: break
    ... And there are good reasons to avoid recursion in production code. ... When you use an explicit stack you can easily put a limit to the stack ... Most algorithm textbooks don't demonstrate the problem, ... If possible, you should validate your ...
    (comp.lang.java.programmer)
  • Re: Software bugs arent inevitable
    ... I suggested that for a given algorithm implemented ... iteration should always be faster by a small factor. ... > recursive function can run out of stack space while the heap still has ... Which is why, in the part you snipped, I said that recursion (unlike ...
    (comp.lang.python)
  • Re: grassfire algorithm in java
    ... In the design phase, a programmer will need ... How many further uses of the stack are possible after a stack overflow? ... What was going on with the recursion at, say, level 20, a question that may ... All your method does is allow a system error to stop the algorithm. ...
    (comp.lang.java.programmer)
  • Re: Is there a tool or compiler option to make program crash as soon as access memory illegally
    ... I can't find the problem from its call stack. ... and the code snippet around the crash (if it ... That is often the case if crash is happening inside malloc/realloc/free ... ... In order to understand recursion you must first understand recursion. ...
    (comp.unix.programmer)