An algorithm problem

[John Machin]

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