back
6 comments
http://openbookproject.net//thinkCSpy/ch11.xhtml

"Both factorial and fibonacci are examples of tail recursion.

Tail recursion is considered a bad practice in languages like Python, however, since it uses more system resources than the equivalent iterative solution."

Uh no, those implementations were plain recursion. Tailrecursion is basically the same as iteration but Python doesn't optimize tail-calls so the stack will blow anyway. He defines tail-recursion something along the lines as "if the last statement ina function is a recursive call". NO! From wikipedia: "In computer science, tail recursion (or tail-end recursion) is a special case of recursion in which the last operation of the function is a recursive call"

And while the solution he presents in the next chapter: previous = {0: 0, 1: 1} def fibonacci(n): if previous.has_key(n): return previous[n] else: new_value = fibonacci(n-1) + fibonacci(n-2) previous[n] = new_value return new_value

works the simple idiomatic way is simply: def fib(n): a, b = 1, 0 while n: a, b, n = b, a+b, n-1 return b

Nope. Its worse. The solutions given in the book for the Fibonacci sequence and the factorial won't be optimized into tail recursion even in scheme unless some additional transformations were carried out on them first. In the factorial sequence, the last call is to the multiply method, not the factorial sequence and in the Fibonacci sequence, the last call is to the addition function.

Sad that most people don't catch that.

What is worse do you mean? Was I wrong about something?
No. You were right that with large inputs the program stack will blow up. However, the definition of tail recursive is if a function returns the value of a recursive call or does not make a recursive call and the factorial and Fibonacci functions weren't even tail recursion in that sense. Ie. it didn't matter where they were implemented, they would still blow up the stack anyway. The "worse" is because they will always blow the stack without some drastic optimization.
He also links in the article to a list of free computer science books http://www.coderholic.com/free-computer-science-books/
Nice find. Thank you.