recursion depth problem
proctor
12cc104 at gmail.com
Mon Apr 23 02:06:18 CEST 2007
On Apr 22, 5:51 pm, Dennis Lee Bieber <wlfr... at ix.netcom.com> wrote:
> On Sun, 22 Apr 2007 17:37:05 -0500, Michael Bentley
> <mich... at jedimindworks.com> declaimed the following in comp.lang.python:
>
> > 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...
>
> Or a simple lookup dictionary to convert from hex to binary, and use
> string interpolation to produce the hex...
>
> Might also make it more natural -- the original recursive loop is
> producing output with LSB on the left, most folks expect the MSB on the
> left (where, in this case, B is "bit").
>
> Of course, if I were to be masochistic, I'd write a binary adder()
> composed of bit adders with carry... Such as {I hope this was just a
> personal learning experience and not a homework project}...
>
> -=-=-=-=-=-=-
> """
> masochistic exercise in generating a binary adder
> """
> import sys
>
> def badd(b1, b2, c=0):
> """
> badd(b1, b2, c) => (carry, sum)
> """
> if b1 and b2:
> # 1 + 1 + c => carry out, and 0/1 from carry in
> return (1, c)
> elif (b1 and c) or (b2 and c):
> # either b1 or b2 is set, and carry in is set
> return (1, 0)
> else:
> # only one of carry in, b1, or b2 is set
> return (0, b1 + b2 + c)
>
> def adder(w1, w2):
> """
> adder(w1, w2) => w3
> where w1, w2, w3 are lists of 0s and 1s
> """
> #equalize list lengths
> if len(w1) > len(w2):
> w2 = [0] * (len(w1) - len(w2)) + w2
> elif len(w1) < len(w2):
> w1 = [0] * (len(w2) - len(w1)) + w1
>
> w3 = [0] * len(w1)
>
> carry = 0 #initialize
> end = len(w3) - 1
> for i in range(end + 1):
> (carry, w3[end-i]) = badd(w1[end-i], w2[end-i], carry)
>
> if carry:
> return "OVERFLOW" #should be an exception
>
> return w3
>
> if __name__ == "__main__":
> #sloppy conversion from character to binary
> binary = [ {True:1, False:0}[c == "1"] for c in sys.argv[1] ]
>
> #simple counter
>
> while binary != "OVERFLOW":
> print "".join(["%1s" % b for b in binary])
> binary = adder(binary, [ 1 ]) #need to supply a list
>
> print "Overflow must have occurred"
>
> binary1 = [ {True:1, False:0}[c == "1"] for c in sys.argv[2] ]
> binary2 = [ {True:1, False:0}[c == "1"] for c in sys.argv[3] ]
>
> print "".join(["%1s" % b for b in adder(binary1, binary2)])
>
> -=-=-=-=-=- (watch out for line wrap on the command line
> E:\UserData\Dennis Lee Bieber\My Documents\Python Progs>python binadd.py
> 0000 0010 111
>
> 0000
> 0001
> 0010
> 0011
> 0100
> 0101
> 0110
> 0111
> 1000
> 1001
> 1010
> 1011
> 1100
> 1101
> 1110
> 1111
> Overflow must have occurred
> 1001
>
> E:\UserData\Dennis Lee Bieber\My Documents\Python Progs>
> E:\UserData\Dennis Lee Bieber\My Documents\Python Progs>python binadd.py
> 010 001 011111111
>
> 010
> 011
> 100
> 101
> 110
> 111
> Overflow must have occurred
> 100000000
>
> E:\UserData\Dennis Lee Bieber\My Documents\Python Progs>
> E:\UserData\Dennis Lee Bieber\My Documents\Python Progs>python binadd.py
> 00 1 111111111
>
> 00
> 01
> 10
> 11
> Overflow must have occurred
> OVERFLOW
>
> E:\UserData\Dennis Lee Bieber\My Documents\Python Progs>
>
> --
> Wulfraed Dennis Lee Bieber KD6MOG
> wlfr... at ix.netcom.com wulfr... at bestiaria.com
> HTTP://wlfraed.home.netcom.com/
> (Bestiaria Support Staff: web-a... at bestiaria.com)
> HTTP://www.bestiaria.com/
thank you. you guys are keeping me busy!
ps. no, i'm not in school. not in the traditional sense anyway :-)
just books, practice, and forums like this.
More information about the Python-list
mailing list