3

To make the process of recursion more visible, this example is given:

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

def trace(f):
    f.indent = 0
    def g(x):
        print('|  ' * f.indent + '|--', f.__name__, x)
        f.indent += 1
        value = f(x)
        print('|  ' * f.indent + '|--', 'return', repr(value))
        f.indent -= 1
        return value
    return g


fib = trace(fib)
print(fib(4))

I can understand "what" the trace function does, but I don't understand "how". Specifically:

1) Why do we have f.indent instead of, say, simple indent = 0 (well, I see that that doesn't work, but I don't see why).

2) I don't understand how

print('|  ' * f.indent + '|--', 'return', repr(value))

is not executed until a value is found.

Would somebody be kind enough to explain the whole thing thoroughly?

Improve this question
1
  • Add Sven's answer to Santiago's and both 1) and 2) are explained comprehensively :) Commented Apr 4, 2011 at 13:45

3 Answers 3

Reset to default
7

Whew. All right, here we go!

First, you have a function, any function. In your case, that's fib(). Now, in python, functions are also objects, and they can be created in runtime, so we can actually do this:

def give_me_a_function():
    def f(x):
        return x

    return f

(Warning: horrible repetition of the word 'function' for the rest of this answer).

Well, we defined a function that takes no arguments and returns,... another function? That's right! Functions are objects! You can create them in runtime! So we defined a second function inside our original one, and returned it, as we would any other object.

Now, let's do something a tad more complicated:

def alter(other_function):
    def altered(x):
        return other_function(x) + 1

    return altered

What the hell was that?

Well, we defined a function, alter(). Just as in the example above, it creates a function in run-time and returns it, as the object it is. That much we already covered.

Now, if functions are objects, and can be created and returned, why wouldn't you be able to pass one as argument? And call it, while it you're at it! That's right: alter() takes a function as argument(*), and uses it.

All it takes to have alter() is combining the above magic with this new magic: we receive a function as an argument, create another one on the fly that makes use of it, and return this new function-object!

Let's try it.

>>> def f(x):
...     return 2*x
>>> new_function = alter(f)
>>> f(2)
4
>>> new_function(2)
5

There it goes! alter() takes my f(), creates a new function that will return f() + 1, and gives that to me as a return value. I assign it to new_function, and I have a new, home-brewed, run-time created function.

(I did warn you about the use of the word 'function', did I not?)

Now, to your piece of code. You're doing something more complicated than just f() + 1. Or not? Well, you're creating a new function that takes the original one, calls it, and prints some data. That's not much more magical than what we just did. Where's the big difference?

Well, there is one detail: fib() is recursive, so it calls itself, right? Nope! Not itself. It calls fib(), and you happened to do this:

fib = trace(fib)

WHAM. fib() is not itself anymore! Now fib() is trace(fib)! So when fib() goes into recursion, it's not calling itself, it's calling the wrapped version of itself we created.

That's why the indentation is handled like that. Look at trace() again, now knowing it's actually recursively indenting, and it makes sense, doesn't it? You want to have one indentation per level of recursion, so increment it, call fib() (which, remember, is now trace(fib)), and then when we're back (so the recursion went and came, and we're about to return to a previous step in the calling chain) we decrement it.

If you still don't see it, try moving all the functionality to fib(). Forget about the decorating function, that's plain confusing.

Ah. I really hope this helps, and that the 2.000 guys that beat me to the answer didn't already make this question obsolete.

Cheers!

(*) Yeah yeah duck typing yadda yadda callable objects bla bla irrelevant.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Thanks for sparing your time, Santiago Lezica.
When I say alter(f(4)), I get <function altered at 0x000000000240A248>. So what is the exact difference between that and first assigning it to new_function (as in your example: new_function = alter(f)) ?
Uhm... when you do alter(f(4)) you are not even passing a function as argument for alter(). alter(f)(4) would be the same as assigning and calling new_function, though it would create the function every time you called it.
Actually, by alter(f(4)) I was trying to do what you did with alter(f)(4). I didn't even know that I could do that. Poof! I have so much more to learn.
4

  1. If we would just use indent instead of f.indent, it would become a local variable inside the inner function g(), due to the assignments to indent in g(). Since this seems to be Python 3, it is actually not necessary to use a function attribute -- you could also use the nonlocal keyword:

    def trace(f):
    indent = 0
    def g(x):
        nonlocal indent
        print('|  ' * indent + '|--', f.__name__, x)
        indent += 1
        value = f(x)
        print('|  ' * indent + '|--', 'return', repr(value))
        indent -= 1
        return value
    return g

  2. The second print() call won't be reached before at least one invocation of f() has returned. It appears in the code after the call to f(), so the flow of execution will only get there after f() has returned.

Improve this answer

2 Comments

I used your function to answer a question found here: stackoverflow.com/questions/42277373/… I hope you don't mind, gave you the credit to the function and linked it to this
@MooingRawr All contributions on SO are licensed under the CC BY-SA 3.0 licence, so you are encouraged to reshare the content. :)
1

If you would store the indent level just in indent, it would be local to the current function call. Each time the function is called, you would get a new variable, with the value 0. By storing it in the function object, it will be the same for each function call (function are objects too in python).

For the second part, I'm not really sure what you are asking. Whenever the argument is greater then 1, two new calls to fib are made, and thus, no value is returned. Until the argument equals 1 or 0, a return call is made.

Improve this answer

2 Comments

"Whenever the argument is greater then 1"..Where in the code does it say that "whenever"?
It's the else part of the if statements. If it's not zero or one, it will make another call to fib().

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.