recursion depth problem

[Michael Bentley]

On Apr 22, 2007, at 5:47 PM, proctor wrote:

> On Apr 22, 4:37 pm, Michael Bentley <mich... at jedimindworks.com> wrote:
>> On Apr 22, 2007, at 4:08 PM, proctor wrote:
>>
>>
>>
>>> On Apr 22, 2:55 pm, half.ital... at gmail.com wrote:
>>>> On Apr 22, 11:49 am, proctor <12cc... at gmail.com> wrote:
>>
>>>>> hello,
>>
>>>>> i have a small function which mimics binary counting.  it runs
>>>>> fine as
>>>>> long as the input is not too long, but if i give it input longer
>>>>> than
>>>>> 8 characters it gives
>>
>>>>> RuntimeError: maximum recursion depth exceeded in cmp
>>
>>>>> i'm not too sure what i am doing improperly.  is there really a
>>>>> lot of
>>>>> recursion in this code?
>>
>>>>> ==================
>>
>>>>> import sys
>>
>>>>> def ch4(item, n=0):
>>>>>         if n < len(item):
>>>>>                 if item[n] == '0':
>>>>>                         item[n] = '1'
>>>>>                         print ''.join(item)
>>>>>                         ch4(item)
>>>>>                 elif item[n] == '1':
>>>>>                         item[n] = '0'
>>>>>                         ch4(item, n+1)
>>
>>>>> ch4(list(sys.argv[1]))
>>
>>>>> ==================
>>
>>>>> this function expects input in the form of a string of zeros, like
>>>>> this:
>>
>>>>> python test-bin.py 00000000
>>
>>>>> and is expected to output a list of permutations like this:
>>
>>>>> $ python test-bin.py 0000
>>>>> 1000
>>>>> 0100
>>>>> 1100
>>>>> 0010
>>>>> 1010
>>>>> 0110
>>>>> 1110
>>>>> 0001
>>>>> 1001
>>>>> 0101
>>>>> 1101
>>>>> 0011
>>>>> 1011
>>>>> 0111
>>>>> 1111
>>
>>>>> thanks for all help!
>>
>>>>> sincerely,
>>>>> proctor
>>
>>>> If you just want to make it work as is....check
>>
>>>> sys.setrecursionlimit()
>>
>>>> ~Sean
>>
>>> very nice.  thanks sean.  so is the structure of my original code
>>> unrescuable?  i cannot rearrange it to bypass the recursion?
>>
>> Anything that can be done with recursion can be done without
>> recursion.  If you really wanted to mimic a binary counter, why not
>> write a function that converts a number to binary?
>>
>> Then you could just count up from 0, printing the return from your
>> binary conversion function...
>>
>> And the binary converter would be pretty easy too: just think of it
>> as making change -- for a given number you just divide the number by
>> each of [2 ** x for x in range(len(sys.argv[1]), 0, -1)] and append
>> the string representations of the answers to a list and if the answer
>> is 1, subtract that much from the number...
>
> cool...  i'm going to have to think about this one... :-)
>

he he...  Run this snippet and see if it makes more sense:

def binary(val, width):
	print '%10s = the sum of' % val
	for i in [2 ** x for x in range(width, 0, -1)]:
		a = val / i
		print ' ' * 13 + '%s * (2 ** %s)' % (a, i)
		val -= i * a

binary(333, 8)