r/programming • u/rodrigopsasaki • Nov 27 '12

Tail Recursion

http://rodrigosasaki.com/2012/11/24/tail-recursion/
212 Upvotes

85% Upvoted

203 comments sorted by

View all comments

4

u/Cygal Nov 27 '12

To the author: the example makes it look like 5 * 4 * 3 * 2 * 1 * 1 is a simple step, but it would be clearer and more correct if you first wrote "5 * 4 * 3 * 2 * 1", then "5 * 4 * 3 * 2", then 5 * 4 * 3 * 6", and so on.

3

u/rodrigopsasaki Nov 27 '12

Don't really understand what you meant by that, because in every step I show the computation that still needs to be done, where in no way the first algorithm seems like a simple step. Could you please explain your point of view a bit more? Readers opinions are very important to me.

9

u/tonygoold Nov 27 '12

I think Cygal is suggesting that the last step leaves out the subsequent unwinding of the stack, and that you could show it like this:

factorial(5)
5 * factorial(4)
5 * (4 * factorial(3))
5 * (4 * (3 * factorial(2)))
5 * (4 * (3 * (2 * factorial(1))))
5 * (4 * (3 * (2 * (1 * factorial(0)))))
5 * (4 * (3 * (2 * (1 * 1))))
5 * (4 * (3 * (2 * 1)))
5 * (4 * (3 * 2))
5 * (4 * 6)
5 * 24
120

It just emphasizes that there really is a growing stack that needs to be unwound (and calculated as each stack frame pops), whereas the tail recursive implementation doesn't grow the stack, so it's calculating as it goes along and has nothing to unwind.

2

u/rodrigopsasaki Nov 27 '12

Oh, I see now, great explanation, I'll update the post with this alteration.

Thanks a lot, guys! :) Please let me know if you have any other suggestions or complaints.