?
Solved

line 6 repeated many times in a debugger

Posted on 2014-08-06
12
Medium Priority
?
134 Views
Last Modified: 2014-08-18
    def rec_exponentiation(b,e):
        if e == 0:
            return 1
        else:
            returnrec=rec_exponentiation(b,e-1)
            return b*returnrec
    # Test!
    rec30=rec_exponentiation(3,0)
    rec33=rec_exponentiation(3,3)
    print (rec30)
    print (rec33)

Open in new window



using a debugger I understand everything
but
when this is called
rec33=rec_exponentiation(3,3)
repeats line6 many times


is this an array

are multiple values returned

in variables i see
returnrec=1
returnrec=3
returnrec=9
and then code goes out of rec_exponentiation function (possibly with value 27)
0
Comment
Question by:rgb192
  • 7
  • 5
12 Comments
 
LVL 35

Expert Comment

by:Robert Schutt
ID: 40245519
That seems to have little to do with Python specifically. You're looking at example code to demonstrate recursion. For this example (calculating 'b' to the power of 'e') recursion is not really necessary but just meant to show you how it's done.

In general the hardest part to determine when using recursion is when to end it. In this case you can see in the code that the recursion ends when e reaches 0. Before that, each time the function calls itself with an 'e' argument 1 less than the one it was called with.

So if you fill in 'b' and 'e' and look at what gets called you would get something like this for the first level:
call    line    code
level   number

0       9       rec33=rec_exponentiation(3,3)

1       2           if 3 == 0:
1       3               return 1
1       4           else:
1       5               returnrec=rec_exponentiation(3,2)
1       6               return 3*returnrec

Open in new window

Now before returning you can see the function calls itself. So to make this clear, I'll copy the function code, indent it and fill in the new value of 'e'. Do that again until 'e' reaches 0 and you get:
call    line    code
level   number

0       9       rec33=rec_exponentiation(3,3)

1       2           if 3 == 0:
1       3               return 1
1       4           else:
1       5               returnrec=rec_exponentiation(3,2)

2       2                   if 2 == 0:
2       3                       return 1
2       4                   else:
2       5                       returnrec=rec_exponentiation(3,1)

3       2                           if 1 == 0:
3       3                               return 1
3       4                           else:
3       5                               returnrec=rec_exponentiation(3,0)

4       2                                   if 0 == 0:
4       3                                       return 1

3       6                               return 3*returnrec

2       6                       return 3*returnrec

1       6               return 3*returnrec

Open in new window

Now, when you look at the end there, you will see the reason why the debugger shows line 6 many times (in fact exactly 'e' times).

Note that this is also a reason to be careful with recursion in many languages, each time the function is called it uses stack space (for storing things like function argument and return values) and that space is usually pretty limited.
0
 

Author Comment

by:rgb192
ID: 40245934
return 3*returnrec
 return 3*returnrec
 return 3*returnrec
 return 3*returnrec

there is no increment and going to if statement

I do not understand how e is changed because the debugger does not visit other lines
is e an array?
0
 
LVL 35

Expert Comment

by:Robert Schutt
ID: 40245949
No, e is just a simple (scalar) variable (the second function argument) which on the call rec_exponentiation(3,3) gets initialised with 3, then on the recursive calls is 1 less each time, so 3... 2... 1... 0, and the recursion ends. The return value gets used to return each temporary value, getting larger each time so 1... 3... 9... 27.

Not sure how the python debugger works but usually a debugger only stops on lines with a breakpoint on it. The other lines are being executed though. Maybe stopping on a return statement is a default option in the python IDE if that's what you're using? Can you post a screenshot of the relevant part of the debugger screen? In most debuggers a graphical hint will be displayed in the left margin to show a breakpoint.
0
Vote for the Most Valuable Expert

It’s time to recognize experts that go above and beyond with helpful solutions and engagement on site. Choose from the top experts in the Hall of Fame or on the right rail of your favorite topic page. Look for the blue “Nominate” button on their profile to vote.

 

Author Comment

by:rgb192
ID: 40247083
debugger stops on all lines

debugger stops on all lines
shown is another file in pyscripter

notice how
a
b
are defined on the left



my question is: I can not follow the debugger for the original .py because it repeats line 6  4 times without going to any other line.

how is value of line6 variable first 1,3,9,27 without changeing by gathering data and incrementing from other lines.
Only example I can think of is an array/list/tuple where 1,3,9,27  are stored
0
 
LVL 35

Expert Comment

by:Robert Schutt
ID: 40247152
No, it's not an array. The debugging behavior has got to be something specific to the editor/tool you're using. When I run your program (in IDLE) it just writes out 1 and 27 (3 to the power of 0 and 3 to the power of 3).

What should give you interesting information is the tab "Call Stack" (where now Variables is selected in the lower left corner), there you will probably see all the (recursive) calling of functions and parameters.

The reason the variables keep changing is the processing that you suspect is not going on because the debugger isn't stopping but in fact it is still being executed, I can't imagine another reason than breakpoints but that could be due to my unfamiliarity with your editor/debugger. I'll see if I can download a trial version to investigate.
0
 
LVL 35

Expert Comment

by:Robert Schutt
ID: 40247243
Ok, I see it's a free Google tool. I downloaded it and pasted your code. When I step through with F7, I see all the lines being executed and at some point (see screen capture) I'm at the deepest level and you can see the call stack displaying the function rec_exponentiation having been called 3 times recursively. After that, line 6 is indeed being executed 3 times after another (ending all 3 recursive calls by returning the result so far) but that is exactly what I would expect.
screen capture
0
 

Author Comment

by:rgb192
ID: 40247268
call stack:

I think the 2 line 5's should be popped off the stack when debugger reaches line 6 in the function

Maybe that is why I am confused.

I understand why line 9 (calling of the function) stays on the stack but do not understand line 5 (previous line of function and why 2x)
0
 
LVL 35

Expert Comment

by:Robert Schutt
ID: 40247293
Would it help to add some more textual debugging to the code?
def rec_exponentiation(b,e):
    print 'start of called function rec_exponentiation with b = {}, e = {}'.format(b, e)
    if e == 0:
        print 'e = 0 so we\'re returning 1'
        return 1
    else:
        print 'e = {} so we\'re going deeper'.format(e)
        returnrec=rec_exponentiation(b,e-1)
        print 'the temporary variable returnrec = {} so we will be returning: {}'.format(returnrec, b * returnrec)
        return b*returnrec
# Test!
print 'now calling function: rec_exponentiation(3,0)'
rec30=rec_exponentiation(3,0)
print 'rec30 = ' + str(rec30)
print 'now calling function: rec_exponentiation(3,3)'
rec33=rec_exponentiation(3,3)
print 'rec33 = ' + str(rec33)

Open in new window

The output shows how the calls and returns follow each other and build up the end result.
The tab "Python interpreter" contains the output:
*** Python 2.7.2 (default, Jun 12 2011, 15:08:59) [MSC v.1500 32 bit (Intel)] on win32. ***
>>> 
*** Remote Interpreter Reinitialized  ***
>>> 
now calling function: rec_exponentiation(3,0)
start of called function rec_exponentiation with b = 3, e = 0
e = 0 so we're returning 1
rec30 = 1
now calling function: rec_exponentiation(3,3)
start of called function rec_exponentiation with b = 3, e = 3
e = 3 so we're going deeper
start of called function rec_exponentiation with b = 3, e = 2
e = 2 so we're going deeper
start of called function rec_exponentiation with b = 3, e = 1
e = 1 so we're going deeper
start of called function rec_exponentiation with b = 3, e = 0
e = 0 so we're returning 1
the temporary variable returnrec = 1 so we will be returning: 3
the temporary variable returnrec = 3 so we will be returning: 9
the temporary variable returnrec = 9 so we will be returning: 27
rec33 = 27
>>> 

Open in new window

0
 
LVL 35

Expert Comment

by:Robert Schutt
ID: 40247337
I understand why line 9 (calling of the function) stays on the stack but do not understand line 5 (previous line of function and why 2x)
In essence there's no difference between the calling of the function from the main code (adding one level to the stack) and the calling of the same function from within the function itself (also adding to the stack). That's exactly what I tried to visualize in my initial post. At level 3 line 5, you can see that for the last time the function calls itself, then it ends the recursion (because e == 0) and each instance of the function call goes from line 5 to line 6, returning the powers of 3 in increasing order to the function that called it, with the last level returning it into the variable to which the main code is assigning it.
0
 

Author Comment

by:rgb192
ID: 40259760
the temporary variable returnrec = 1 so we will be returning: 3
the temporary variable returnrec = 3 so we will be returning: 9
the temporary variable returnrec = 9 so we will be returning: 27


okay emptying out the stack
lifo
this is the only reason why one variable has 3 returns
and one call to function gets the third result
0
 
LVL 35

Accepted Solution

by:
Robert Schutt earned 2000 total points
ID: 40259899
Yep, that's correct.
0
 

Author Closing Comment

by:rgb192
ID: 40269229
thanks for stack information.
0

Featured Post

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

A set of related code is known to be a Module, it helps us to organize our code logically which is much easier for us to understand and use it. Module is an object with arbitrarily named attributes which can be used in binding and referencing. …
Introduction On September 29, 2012, the Python 3.3.0 was released; nothing extremely unexpected,  yet another, better version of Python. But, if you work in Microsoft Windows, you should notice that the Python Launcher for Windows was introduced wi…
Learn the basics of strings in Python: declaration, operations, indices, and slicing. Strings are declared with quotations; for example: s = "string": Strings are immutable.: Strings may be concatenated or multiplied using the addition and multiplic…
Learn the basics of while and for loops in Python.  while loops are used for testing while, or until, a condition is met: The structure of a while loop is as follows:     while <condition>:         do something         repeate: The break statement m…
Suggested Courses
Course of the Month16 days, 20 hours left to enroll

862 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question