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