Can decorator decorate a recursive function?

Question

I wanted to see difference of time cost between two ways to calculate Fibonacci sequence： First, I created a decorator add "output time cost" function to a function:

def time_cost(func):
    def wed(n):
        start = time.time()
        func(n)
        stop = time.time()
        print(stop-start)
    return wed

Then I wrote the first function:

@time_cost
def DP_F(n):
    f = [1,1]
    while len(f)<n:
    f.append(f[len(f)-1]+f[len(f)-2])
    return f

It worked well

>>> DP_F(10)
0.0
>>> DP_F(100)
0.0
>>> DP_F(10000)
0.007944107055664062

But something wrong happened when I create the second function with decorator:

@time_cost
def R_F(n):
    if n<=2:
        return 1
    else:
        return R_F(n-1)+R_F(n-2)

Raised error saying some of the output may missed

>>> R_F(10)
0.0
0.0
Traceback (most recent call last):
  File "<pyshell#44>", line 1, in <module>
    R_F(10)
  File "<pyshell#28>", line 4, in wed
    func(n)
  File "<pyshell#43>", line 8, in R_F
    return R_F(n-1)+R_F(n-2)
  File "<pyshell#28>", line 4, in wed
    func(n)
  File "<pyshell#43>", line 8, in R_F
    return R_F(n-1)+R_F(n-2)
  File "<pyshell#28>", line 4, in wed
    func(n)
  File "<pyshell#43>", line 8, in R_F
    return R_F(n-1)+R_F(n-2)
  File "<pyshell#28>", line 4, in wed
    func(n)
  File "<pyshell#43>", line 8, in R_F
    return R_F(n-1)+R_F(n-2)
  File "<pyshell#28>", line 4, in wed
    func(n)
  File "<pyshell#43>", line 8, in R_F
    return R_F(n-1)+R_F(n-2)
  File "<pyshell#28>", line 4, in wed
    func(n)
  File "<pyshell#43>", line 8, in R_F
    return R_F(n-1)+R_F(n-2)
  File "<pyshell#28>", line 4, in wed
    func(n)
  File "<pyshell#43>", line 8, in R_F
    return R_F(n-1)+R_F(n-2)
  File "<pyshell#28>", line 4, in wed
    func(n)
  File "<pyshell#43>", line 8, in R_F
    return R_F(n-1)+R_F(n-2)
TypeError: unsupported operand type(s) for +: 'NoneType' and 'NoneType'

So Python decorator cannot decorate recursive function?

Answer 1

Or just do this:

def R_F(n):
    if n<=2:
        return 1
    else:
        return R_F(n-1)+R_F(n-2)

R_FCOST = time_cost(R_F)

Answer 2

The immediate issue is that wed doesn't return the return value of func. That's easy to fix.

def time_cost(func):
    def wed(n):
        start = time.time()
        n = func(n)
        stop = time.time()
        print(stop-start)
        return n
    return wed

However, now look what happens when you call R_F(3).

>>> R_F(3)
9.5367431640625e-07
1.1920928955078125e-06
0.0001671314239501953
2

You get 3 times: one per recursive call. This is because the original function calls whatever R_F is bound to, which now is the the function wed, not the actual Fibonacci function.

Something like this is better handled using a context manager.

from contextlib import contextmanager

@contextmanager
def time_cost():
    start = time.time()
    yield
    stop = time.time()
    print(stop - start)

with time_cost():
    R_F(3)

---

A digression

In some sense, Python doesn't have recursive functions. A function cannot call itself, but rather only some function bound to the name you expect will refer to your function. Call it "cooperative recursion".

For example, consider the standard example of a recursive function, the factorial.

def fact(x):
     return 1 if x == 0 else x * fact(x-1)

We can easily break this by rebinding the name fact.

g = fact  # save a reference to the original function
def fact(x):
   print("Broken")
   return 0

Now g(3) prints Broken and returns 0, because it will try to call whatever fact is bound to now, not what fact was bound to before you redefined it.

If you want a "safe" recursive function, you would have to define it in terms of a private recursive helper.

def fact(x):
    def helper(x):
        return 1 if x == 0 else x * helper(x - 1)
    return helper(x)

Now you can safely decorate fact, because no matter what fact is bound to (whether the original or the decorated function), helper is never rebound.