recursion depth problem

[Alex Martelli]

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]))

...
for interest sake: is my method unredeemable?

Let's just say that I don't currently see an obvious way of redeeming
it. ;-)

Change the outer if into a while, and the recursive calls into proper
assignments to n. They're both tail-recursive calls, so this won't
change the semantics, as it happens.


Alex

 

[Steven Bethard]

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])) ...
for interest sake: is my method unredeemable?

Let's just say that I don't currently see an obvious way of redeeming
it. ;-)

Change the outer if into a while, and the recursive calls into proper
assignments to n. They're both tail-recursive calls, so this won't
change the semantics, as it happens.
Thanks!

... n = 0
... while n < len(chars):
... if chars[n] == '0':
... chars[n] = '1'
... n = 0
... print ''.join(chars)
... elif chars[n] == '1':
... chars[n] = '0'
... n += 1
... 10000000
01000000
11000000
...
10111111
01111111
11111111

Looks good.

STeVe

 

[Dennis Lee Bieber]

this is good stuff. for learning especially! thank you again!

Took me some time to find... My 30year old BugBooks* are in storage,
along with all the other raw comp-sci texts.

What you see above is a Python implementation of a 2 1-bit input,
1-bit sum and 1-bit carry output, full-adder from basic AND/OR/XOR gates
-- you can build the hardware equivalent (except for the variable
length) using old-fashioned 74xx chips (are 74xx TTL chips still made,
or will one need to use the 74Cxx CMOS variants <G>) [heck; is the
multi-function ALU chip still made?]



* The Virginia Tech shootings were just a blip on my radar until I
read that this was Blacksburg -- as I once had most of the Blacksburg
BugBooks
--
Wulfraed Dennis Lee Bieber KD6MOG
(e-mail address removed) (e-mail address removed)
HTTP://wlfraed.home.netcom.com/
(Bestiaria Support Staff: (e-mail address removed))
HTTP://www.bestiaria.com/

 

[mensanator]

this is good stuff.  for learning especially!  thank you again!

I once made a complete full adder in perl with strings
so that I could have unlimited precision (this is before I found
out about Big Arithmetic libraries). Since I was only doing the
Collatz Conjecture, all I needed was to multiply by 3 (shift
left by appending '0' to string and adding to original string
using the full adder), dividing by two (shift right by slicing
off rightmost character from string) and incrementing
(pre-set the carry bit to '1').

It worked perfectly.

But it was slower than snake shit.

 

[proctor]

this is good stuff. for learning especially! thank you again!

Took me some time to find... My 30year old BugBooks* are in storage,
along with all the other raw comp-sci texts.

What you see above is a Python implementation of a 2 1-bit input,
1-bit sum and 1-bit carry output, full-adder from basic AND/OR/XOR gates
-- you can build the hardware equivalent (except for the variable
length) using old-fashioned 74xx chips (are 74xx TTL chips still made,
or will one need to use the 74Cxx CMOS variants <G>) [heck; is the
multi-function ALU chip still made?]

* The Virginia Tech shootings were just a blip on my radar until I
read that this was Blacksburg -- as I once had most of the Blacksburg
BugBooks
--
Wulfraed Dennis Lee Bieber KD6MOG
(e-mail address removed) (e-mail address removed)
HTTP://wlfraed.home.netcom.com/
(Bestiaria Support Staff: (e-mail address removed))
HTTP://www.bestiaria.com/

well i'm going to make it a project to understand properly this
program.

proctor.

 

[proctor]

...

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])) ...
for interest sake: is my method unredeemable?

Let's just say that I don't currently see an obvious way of redeeming
it. ;-)

Change the outer if into a while, and the recursive calls into proper
assignments to n. They're both tail-recursive calls, so this won't
change the semantics, as it happens.

Alex

really helpful! thank you very much!

proctor.

 

[Dennis Lee Bieber]

But it was slower than snake shit.

Given the rate of snake digestion... (rat today... gone next month)
--
Wulfraed Dennis Lee Bieber KD6MOG
(e-mail address removed) (e-mail address removed)
HTTP://wlfraed.home.netcom.com/
(Bestiaria Support Staff: (e-mail address removed))
HTTP://www.bestiaria.com/

 

[proctor]

Oops! Note to self: *ALWAYS* try code before posting to a public
forum :-(

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

binary(233, 8)

hi michael,

just a quick clarification...

it seems to me that the self-documenting part of the code should be
more like this:

print ' ' * 13 + '%s * (2 ** %s)' % (a, width-1)

instead of

print ' ' * 13 + '%s * (2 ** %s)' % (a, width)

is this correct, or am i mixed?

sincerely,
proctor

 

[Michael Bentley]

Oops! Note to self: *ALWAYS* try code before posting to a public
forum :-(

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

binary(233, 8)

hi michael,

just a quick clarification...

it seems to me that the self-documenting part of the code should be
more like this:

print ' ' * 13 + '%s * (2 ** %s)' % (a, width-1)

instead of

print ' ' * 13 + '%s * (2 ** %s)' % (a, width)

is this correct, or am i mixed?

No, you're right -- actually I ended up decrementing width after the
print instead of before it -- but didn't feel like posting yet
another correction. Your correction works though!