Tail Recursion Explained - Computerphile

Improve the efficiency of recursive code by re-writing it to be tail recursive. Professor Graham Hutton explains.


This video was filmed and edited by Sean Riley.

[daverotors]

It's important to note that the language/compiler will need to support tail call optimisation, otherwise it's not helping as much: For example with the accumulator, a "naive" language implementation would still keep all the stack frames around until the end, and return the just-received value back up the stack. Only if the language supports TCO will it recognize the tail call and replace (overwrite) the current stack frame for the next call - which is where the optimisation helps to reduce memory usage.

[krishna]

Dear Computerphile, would it be possible for you to enable CC (the auto-generated one is enough) for us deaf viewers? I would really appreciate it. Thank you.

[frognik]

No stack frames were harmed in the making of this video.

[TomGalonska]

Be aware that tail recursion in languages with lazy evaluation can actually make it slower or more memory-heavy. Let's take factorial as an example: with lazy evaluation, in the expression go (n-1) (a*n) the (n-1) would be evaluated because it's immediately needed in the next call of the function (to decide if this is the simple case go 1 a or the case go n a). The (a*n) isn't needed immediately, so it's not going to be evaluated. And the and you get sth. similar to the "primitive" fac function: go 3 1 = g (3-1) (1*3) = g 2 (1*3) = g (2-1) ((1*3)*2) = g 1 ((1*3)*2) = (1*3) * 2 = 6

[Number_]

As noted by avawn
, your chosen language will need to support tail call optimisation to get the most of this technique, HOWEVER if your language does not support tail call optimisation, you can still exploit the efficiency of tail recursion. Since, by definition, tail recursive functions make the recursive call last, you can convert them to a while loop with minimal changes. All you generally need to do is define the parameters before the loop, then replace the recursive call with code that edits the parameters. The following is a demonstration in python, which does not support TCO:

#Factorial
n = 4
a = 1

while (n > 0):
a = a*n
n -= 1

print(a)



#Fibonacci
n = 4
a = 0
b = 1

while (n > 0):
temp = a
a = b
b = temp + b
n -= 1

print(a)

[bradH]

The explanation was very clear and easy to understand. Thank you for making this world a better place.

[casperes]

This omits some of the cool compiler optimisations this allows you, like not setting up new stack space for the new call, and just reusing the context of the current call

[randomelectronicsanddispla]

I'm surprised you didn't mention that it saves overloading the stack, it turns a "call, call, call, ...., return, return, return" into a "call, while, ..., loop, return"

[Qbe_Root]

In the tail-recursive Fibonacci example, there’s no need for 1 to be a base case, since go 1 (a, b) = go 0 (b, a + b) = b anyway

[agmessier]

I think it's important in this case to discuss how the stack normally gets used, and how tail recursion causes the current stack to get discarded, effectively allowing the program to forget it made recursive call. An important aspect of the optimization is the ability to return the result directly to the original caller and not have to traverse back down the stack.

[duxoakende]

You guys are amazing. This channel and Numberphile have really given me so much inspiration to work in math and computer science. I probably owe my career to this channel. Thank you.

[scheimong]

I learned tail recursion in my uni's SML computing fundamentals course and knew how it worked, but never understood why it's called "tail recursion". Now I do so thanks.

[Kartaal]

Nice little video explaining tail recursion with accumulators.
I think it'd be really great to have one covering tail recursion with continuations though. Mostly to fill in the gap of "tail recursion is an optimised version of recursion" being not true for all cases.

I just got done with a university course in F# so not that useful for me personally but I have always liked how accessible Computerphile videos are. Covering continuations in a similar manner would probably be really helpful to a lot of viewers.

[Kepler]

I cant discribe how your lesson is helpful. Thank you so much. Where is the button for likes?

[andreasimonecosta]

I'd like to see prof. Graham Hutton explaining Continuation Passing Style, it could be a nice next step after Tail Recursion. 😄😄😄

[Semtx]

I keep finding great litle tools here that might help me write better scripts. Thanks!

[thomasdtrain]

This was actually pretty interesting. Thanks.

[mikehosken]

I remember doing both of these problems when I was 10. It takes about 4 lines of Apple Basic. Didn’t take long for it to overflow but I’m pretty sure they were efficient. Factorial was a for loop irc

[leoncruz]

CPython: I have no idea of what you are talking about...

[snensnurnberg]

Thank you Mr.Graham ! Really enjoyed this Lesson.