#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2013
    Posts
    6
    Rep Power
    0

    Counting recursive calls


    Having read how to use global variables to count recursive calls, I want to count calls in function without using global variable. My best attempt follows (it Fails!)


    numOfCalls = 1
    def fib(x, numOfCalls):
    """
    assumes x an integer > 0
    returns fibonacci of x
    """



    print 'number of calls is ',numOfCalls
    if x == 0 or x == 1:
    return 1

    else:
    return fib(x-1, numOfCalls + 1) + fib(x-2, numOfCalls + 2)




    fib(5, numOfCalls)


    Any help would be appreciated
    My attempt does generate 15 print lines, I would therefore like to count the print lines but not sure how to do this.
    I would also appreciate to know where I can read up how to format code to present on this forum (I am pasting from IDLE).
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    194
    Rep Power
    2
    Use the # button in the tool bar for code tags. After pasting your code, highlight it and hit that button.

    Anyway, this is of course trivial if you use a class with an identical method to using a global, except with a class attribute instead.

    With just a function however it is a bit tricky. This seems to do the trick:
    python Code:
    def fib(x,num_calls=0):
        """
        assumes x an integer > 0
        returns fibonacci of x
        """
        if x == 0 or x == 1:
            return 1,num_calls+1
     
        else:
            a,num_calls = fib(x-1,num_calls)
            b,num_calls = fib(x-2,num_calls)
            return a+b,num_calls+1
     
    if __name__ == "__main__":
        x = 5
        print("Fib({}) = {}\nCalls = {}".format(x,*fib(x)))

    -Mek

    Comments on this post

    • Nyktos agrees
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2012
    Posts
    114
    Rep Power
    3
    This one only works in Python 3:
    Code:
    def fib(x):
        num_calls = 0
        def _fib(x):
            nonlocal num_calls
            num_calls += 1
            if x in {0, 1}:
                return 1
            else:
                return _fib(x - 2) + _fib(x - 1)
        return _fib(x), num_calls
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2013
    Posts
    6
    Rep Power
    0

    Thanks Again Mek


    Thanks Mek
    your function works well.
    There are a few new concepts in code that I need to explore!
    What does this do?
    Code:
    if __name__ == "__main__":
    I am hoping last line delivers as code tags
    If it does thanks also for teaching me this
    Simon


    Originally Posted by Mekire
    Use the # button in the tool bar for code tags. After pasting your code, highlight it and hit that button.

    Anyway, this is of course trivial if you use a class with an identical method to using a global, except with a class attribute instead.

    With just a function however it is a bit tricky. This seems to do the trick:
    python Code:
    def fib(x,num_calls=0):
        """
        assumes x an integer > 0
        returns fibonacci of x
        """
        if x == 0 or x == 1:
            return 1,num_calls+1
     
        else:
            a,num_calls = fib(x-1,num_calls)
            b,num_calls = fib(x-2,num_calls)
            return a+b,num_calls+1
     
    if __name__ == "__main__":
        x = 5
        print("Fib({}) = {}\nCalls = {}".format(x,*fib(x)))

    -Mek
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    194
    Rep Power
    2
    That lines tells the interpreter to only execute the code in that block if the program is run as main. If you import it from another module it won't run that. This way if you wanted to import and use your fib function in another file you wouldn't have to worry about that file printing our fib(5) calculation. Basically no real python program executes any code (save for imports and perhaps global assignments) in the raw global namespace. This is a good habit to get into early as you will see it a lot.

    I would also like to note that recursively calculating Fibonacci numbers like this is stupendously inefficient. This excercise only serves to teach you how to use recursion; it does nothing to teach you when to use it.

    -Mek

    Edit:
    Here is a non-recursive version if you are interested that uses a generator:
    python Code:
    import sys
    if sys.version_info[0] == 2: range = xrange #version compatibility
     
    def fib_gen():
        a = 0; b = 1
        while 1:
            a,b = b,a+b
            yield a
     
    if __name__ == "__main__":
        fibby = fib_gen()
        for i in range(100):
            print("Fibbonacci #{:<4} : {}".format(i+1,next(fibby)))
    Last edited by Mekire; May 23rd, 2013 at 10:15 AM.
  10. #6
  11. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,897
    Rep Power
    481

    Please ignore this bad posting.


    [edit]Mekire proved this post is wrong. Please ignore it.[/edit]


    Two other ways to count recursive calls without using a global.

    Use a class, update the counter in the object.

    and

    Code:
    def recursive(args, count_in_item_0_of_this_list):
        count_in_item_0_of_this_list[0] += 1
        #...
    
    counter = [0]
    result = recursive(args, counter)
    print('calls:', counter[0])
    It would make a nice decorator.



    Thank you for example of nonlocal . I hadn't known of a use for it.



    When you invoke python the module name is
    '__main__'

    And that's why the __name__ test causes different behavior in

    $ python myprogram.py

    versus

    $ python -c 'import myprogram'
    Last edited by b49P23TIvg; May 25th, 2013 at 07:28 PM. Reason: This post sucks big time.
    [code]Code tags[/code] are essential for python code and Makefiles!
  12. #7
  13. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    194
    Rep Power
    2
    Code:
    def recursive(args, count_in_item_0_of_this_list):
        count_in_item_0_of_this_list[0] += 1
        #...
    
    counter = [0]
    result = recursive(args, counter)
    print('calls:', counter[0])
    You are passing it in as an argument, but this is still tantamount to modifying a global variable; wouldn't you say? The end result is that a global has been modified. The use of a mutable data type is just masking this fact.

    Also I mentioned the using a class attribute in my first post

    -Mek

    Edit: I suppose you could wrap it up just as the nonlocal version did:
    Code:
    def fib(x):
        num_calls = [0]
        def _fib(x):
            num_calls[0] += 1
            if x in {0, 1}:
                return 1
            else:
                return _fib(x - 2) + _fib(x - 1)
        return _fib(x), num_calls[0]
    Last edited by Mekire; May 23rd, 2013 at 09:44 PM.
  14. #8
  15. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,897
    Rep Power
    481
    I had a bad day at the forums!
    [code]Code tags[/code] are essential for python code and Makefiles!
  16. #9
  17. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2013
    Location
    Usually Japan when not on contract
    Posts
    240
    Rep Power
    12

    Don't use variables


    Some of the responses up there are swimming very hard against the current to make Python (and recursive calls) work in a way that isn't natural.

    All you need is an accumulator argument. It is a function argument that passes an idea of state along with it, so the function wraps state bits without accessing (or screwing up) any global values. In strict functional languages this is one method of passing state along since in those languages variables are either not permitted to exist or are illegal to change.

    python Code:
    def countdown(x, depth=0):
        if x > 0:
            print x
            countdown(x - 1, depth + 1)
        else:
            print "Blastoff!"
            print "Depth of recursion was: ", depth
    That's all there is to it:
    Code:
    >>> countdown(10)
    10
    9
    8
    7
    6
    5
    4
    3
    2
    1
    Blastoff!
    Depth of recursion was:  10
    This may not seem very special at first, until you consider safety in a parallel processing environment. It has only one side effect: the effect of calling print().
  18. #10
  19. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    194
    Rep Power
    2
    Recursive depth and number of function calls are NOT the same thing.

    -Mek

    Edit: Showing depth and call count for the OPs fib(5):
    python Code:
    def fib(x):
        calls = [0]
        def _fib(x,depth=0):
            calls[0] += 1
            depth += 1
            print("{} Depth: {}, Calls: {}".format("-"*depth,depth,calls[0]))
            if x in (0,1):
                print("{} Returning 1".format("-"*depth))
                return 1
     
            else:
                print("{} Returning fib({})-fib({})".format("-"*depth,x-1,x-2))
                return _fib(x-1,depth) + _fib(x-2,depth)
        return _fib(x)
     
    if __name__ == "__main__":
        x = 5
        print("\nFib {}: {}".format(x,fib(x)))
    Output:
    Code:
    >>> 
    - Depth: 1, Calls: 1
    - Returning fib(4)-fib(3)
    -- Depth: 2, Calls: 2
    -- Returning fib(3)-fib(2)
    --- Depth: 3, Calls: 3
    --- Returning fib(2)-fib(1)
    ---- Depth: 4, Calls: 4
    ---- Returning fib(1)-fib(0)
    ----- Depth: 5, Calls: 5
    ----- Returning 1
    ----- Depth: 5, Calls: 6
    ----- Returning 1
    ---- Depth: 4, Calls: 7
    ---- Returning 1
    --- Depth: 3, Calls: 8
    --- Returning fib(1)-fib(0)
    ---- Depth: 4, Calls: 9
    ---- Returning 1
    ---- Depth: 4, Calls: 10
    ---- Returning 1
    -- Depth: 2, Calls: 11
    -- Returning fib(2)-fib(1)
    --- Depth: 3, Calls: 12
    --- Returning fib(1)-fib(0)
    ---- Depth: 4, Calls: 13
    ---- Returning 1
    ---- Depth: 4, Calls: 14
    ---- Returning 1
    --- Depth: 3, Calls: 15
    --- Returning 1
    
    Fib 5: 8

    Comments on this post

    • b49P23TIvg agrees : I retracted my post 6. Thank you.
    Last edited by Mekire; May 24th, 2013 at 11:40 PM.
  20. #11
  21. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2013
    Location
    Usually Japan when not on contract
    Posts
    240
    Rep Power
    12
    Originally Posted by Mekire
    Recursive depth and number of function calls are NOT the same thing.
    Indeed they are not.

    And maintaining global state is a Bad Thing when writing recursive functions -- which is why accumulators have been used since the before the word "functional" referred to a style of programming. This is true even if that global state isn't global to anything other than concurrent executions of the recursive function, because you can never know whether they are executing in a sequential stack (the way CPython implements it) or are actually represent concurrent tail recursive branches executing in parallel (like in Iron Python) or even don't get executed at all because of a memoization optimizer operating in the background.
    python Code:
    def fib(x, depth=0):
       print "Received x: ", x
       print "Depth of current call: ", depth
       if x == 0:
         return x
       elif x == 1:
         return x
       else:
         return fib(x - 1, depth + 1) + fib(x - 2, depth + 1)
     
    print fib(6)
    Code:
    Received x:  6
    Depth of current call:  0
    Received x:  5
    Depth of current call:  1
    Received x:  4
    Depth of current call:  2
    Received x:  3
    Depth of current call:  3
    Received x:  2
    Depth of current call:  4
    Received x:  1
    Depth of current call:  5
    Received x:  0
    Depth of current call:  5
    Received x:  1
    Depth of current call:  4
    Received x:  2
    Depth of current call:  3
    Received x:  1
    Depth of current call:  4
    Received x:  0
    Depth of current call:  4
    Received x:  3
    Depth of current call:  2
    Received x:  2
    Depth of current call:  3
    Received x:  1
    Depth of current call:  4
    Received x:  0
    Depth of current call:  4
    Received x:  1
    Depth of current call:  3
    Received x:  4
    Depth of current call:  1
    Received x:  3
    Depth of current call:  2
    Received x:  2
    Depth of current call:  3
    Received x:  1
    Depth of current call:  4
    Received x:  0
    Depth of current call:  4
    Received x:  1
    Depth of current call:  3
    Received x:  2
    Depth of current call:  2
    Received x:  1
    Depth of current call:  3
    Received x:  0
    Depth of current call:  3
    8

IMN logo majestic logo threadwatch logo seochat tools logo