CODEWITHSUNDEEP
pythonrecursiondecorator
jianglai
jianglai

Reputation: 429

Decorating recursive functions in python

I am having hard time understanding how a decorated recursive function works. For the following snippet:

def dec(f):
    def wrapper(*argv):
        print(argv, 'Decorated!')
        return(f(*argv))
    return(wrapper)

def f(n):
    print(n, 'Original!')
    if n == 1: return(1)
    else: return(f(n - 1) + n)

print(f(5))
print

dec_f = dec(f)
print(dec_f(5))
print

f = dec(f)
print(f(5))

The output is:

(5, 'Original!')
(4, 'Original!')
(3, 'Original!')
(2, 'Original!')
(1, 'Original!')
15

((5,), 'Decorated!')
(5, 'Original!')
(4, 'Original!')
(3, 'Original!')
(2, 'Original!')
(1, 'Original!')
15

((5,), 'Decorated!')
(5, 'Original!')
((4,), 'Decorated!')
(4, 'Original!')
((3,), 'Decorated!')
(3, 'Original!')
((2,), 'Decorated!')
(2, 'Original!')
((1,), 'Decorated!')
(1, 'Original!')
15

The first one prints f(n) so naturally it prints 'Original' every time f(n) is called recursively.

The second one prints def_f(n), so when n is passed to wrapper it calls f(n) recursively. But the wrapper itself is not recursive so only one 'Decorated' is printed.

The third one puzzles me, which is the same as using decorator @dec. Why does decorated f(n) calls the wrapper five times also? It looks to me that def_f=dec(f) and f=dec(f) are just two keywords bound to two identical function objects. Is there something else going on when the decorated function is given the same name as the undecorated one?

Thanks!

Upvotes: 19

Views: 11229

Answers (6)

Arsène de Bienne
Arsène de Bienne

Reputation: 11

if you do a bit of function introspection and print the corresponding memory id's, you will see that although the original function id is "baked" in the closure, it is in fact the closure function that is invoked inside the recursive

def dec(func):
    def wrapper(*argv):
        print(argv, 'Decorated!')
        print("func id inside wrapper= ", hex(id(func)))
        return(func(*argv))
    return(wrapper)

def f(n):
    print(n, 'Original!')
    print("f id inside recursive function = ", hex(id(f)))
    if n == 1: return(1)
    else: return(f(n - 1) + n)

orig_id = hex(id(f))
print("recursive f id after its definition = ", orig_id)

f = dec(f)
closure_id = hex(id(f))
print("id of the closure = ", closure_id)

print("function object is at {0}".format(orig_id), f.__closure__)

print(f(1))

if you run the code above, you will get

recursive f id after its definition =  0x1ce45be19d0
id of the closure =  0x1ce45c49a60
function object is at 0x1ce45be19d0 (<cell at 0x000001CE45AFACD0: function object at 0x000001CE45BE19D0>,)
(1,) Decorated!
func id inside wrapper=  0x1ce45be19d0
1 Original!
f id inside recursive function =  0x1ce45c49a60
1

Upvotes: 1

Rohit
Rohit

Reputation: 4178

Changed your code a bit

def dec(func):
    def wrapper(*argv):
        print(argv, 'Decorated!')
        return(func(*argv))
    return(wrapper)

def f(n):
    print(n, 'Original!')
    if n == 1: return(1)
    else: return(f(n - 1) + n)

print(f(5))
print

dec_f = dec(f)
print(dec_f(5))
print

f = dec(f)
print(f(5))

I think this would make things bit more clear here, the wrapper function actually closes the func object from enclosing scope. So every call to func inside wrapper would call the original f but the recursive call within f will call the decorated version of f.

You can actually see this by simply printing the func.__name__ inside wrapper and f.__name__ inside the function f

Upvotes: 0

Freeman
Freeman

Reputation: 6216

If decorators indicate a prologue/epilogue to be done one before or after another function, we can avoid doing it several times simulating decorators with recursive functions.

For example:

def timing(f):
    def wrapper(*args):
       t1 = time.clock();
       r = apply(f,args)
       t2 = time.clock();
       print"%f seconds" % (t2-t1)
       return r
    return wrapper

@timing
def fibonacci(n):
    if n==1 or n==2:
      return 1
    return fibonacci(n-1)+fibonacci(n-2)

r = fibonacci(5)
print "Fibonacci of %d is %d" % (5,r)

Produces:

0.000000 seconds
0.000001 seconds
0.000026 seconds
0.000001 seconds
0.000030 seconds
0.000000 seconds
0.000001 seconds
0.000007 seconds
0.000045 seconds
Fibonacci of 5 is 5

We can simulate the decorator to force only one prologue/epilogue as:

r = timing(fibonacci)(5)
print "Fibonacci %d of is %d" % (5,r)

Which produces:

0.000010 seconds
Fibonacci 5 of is 5

Upvotes: 2

bigblind
bigblind

Reputation: 12877

As you said, the first one is called as usual.

the second one puts a decorated version of f called dec_f in the global scope. Dec_f is called, so that prints "Decorated!", but inside the f function passed to dec, you call f itself, not dec_f. the name f is looked up and found in the global scope, where it is still defined without the wrapper, so from than on, only f gets called.

in the 3re example, you assign the decorated version to the name f, so when inside the function f, the name f is looked up, it looks in the global scope, finds f, which is now the decorated version.

Upvotes: 12

Martijn Pieters
Martijn Pieters

Reputation: 1124070

Your function invokes something called f, which python looks up in the enclosing scope.

Until the statement f = dec(f), f is still bound to the unwrapped function, so that's what is getting called.

Upvotes: 1

John Y
John Y

Reputation: 14549

All assignment in Python is just binding names to objects. When you have

f = dec(f)

what you are doing is binding the name f to the return value of dec(f). At that point, f no longer refers to the original function. The original function still exists and is called by the new f, but you don't have a named reference to the original function anymore.

Upvotes: 5

Related Questions