So I am happily going along with my one Python student teaching him what I know of Python (admittedly not much but it is an “easy” language and I have several books to learn from).  In my naive confidence that I can learn anything I decided to teach/learn more about recursion.  I have this little program that converts base 10 to base 2.

  1. def binary(n):
  2.    if n > 1:
  3.        binary(n//2)
  4.    print(n % 2,end = ”)
  5. dec = int(input(“Enter an integer: “))
  6. binary(dec)

I think I see how this works so we start to tear it apart.  We are OK with the “//” and the “%” operations.  Into the recursive loop we go.  Surprise!  I cannot figure out how it works.  So I do my usual thing when I cannot figure out some code, I throw in some print statements.  This method is tried and true.  It has clarified code for me for many years.

  1. def binary(n):
  2.    if n > 1:
  3.        print(“first”,n)         # added this for testing purposes
  4.        binary(n//2)
  5.        print(“second”,n)  # added this for testing purposes
  6.    print(“third” ,n % 2,end = ”)
  7. dec = int(input(“Enter an integer: “))
  8. binary(dec)

I input 22.  Here is the output.

first 22

first 11

first 5

first 2

third 1second 2

third 0second 5

third 1second 11

third 1second 22

third 0

Lines 1 – 4 are just fine, the recursion loop.  From there it goes to hell in a hand basket.  I do not understand how it even gets to the “second” print statement.  I had to call in the “Pro from Dover”, a friend of mine who teaches programming at the local university.  He emailed me how it works.  Nope.  It still was real fuzzy.  He is going to come over after the break and have a recursion sit-down with my student and I.

I actually like hitting things like this.  If I knew how to do it all what fun would that be?


6 Responses to “”

  1. lenandlar Says:

    What I find helps is drawing a sketch or what happens in memory for each call.

  2. gflint Says:

    I think that is my problem. I do not know enough at the moment of what is actually happening in the memory. The fact print two executes has me flummoxed. My guru hopefully will enlighten me after the break.

  3. gasstationwithoutpumps Says:

    It might help to do one more print before the “if”.

    You should see recursion going in with n dropping, then popping back out with n going back up.

  4. gflint Says:

    A print before the if mirrors the “first” print except it counts down to 1 which I expected.

  5. Mike Zamansky (@zamansky) Says:

    Try looking at it this way:

    What if the routine was

    def spinary(n):
    print(“third” ,n % 2,end = ”)

    def binary(n):
    if n > 1:
    print(“first”,n) # added this for testing purposes
    print(“second”,n) # added this for testing purposes
    print(“third” ,n % 2,end = ”)

    and then call binary(2).

    it will:
    1. print first
    2. Call spinary(1) and do that stuff
    3. when it eventually returns from spinary, it will print second

    whenever you call a function, it saves the “return address” so when the function finishes, the calling function picks up right after the call returns.

    That’s what happens with binary /spinary

    nothing changes in the example with the recursion – when the recursive binary(n/2) call returns, it picks up where it left off and prints second

    This would be easier to show with diagrams.

  6. gflint Says:

    My guru from the university came over and explained the recursion. It was as Mike said. It was a stack issue that I did not know about. Slick. Teaching programming at the level I teach means I rarely have to think about the stack. I need to work on this more.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: