Tail Recursion Explained - Computerphile 

Thanks, I was thinking about it the whole video. Constant memory just made no sense in that case

If the language *does* support tail call optimization, the general rule of thumb is that if the function has exactly one recursive call which is at the end of the function, then the compiler can optimize that call. For example, most compilers supporting tail call optimization can optimize a factorial function without the need for hand-tuning shown in the video. However, most compilers would requiring such hand-tuning before they could tail-call optimize the Fibonacci function. All that being said, functions where a tail call optimization is possible can often be translated into a loop in a very straightforward manner; in some sense that's what a tail call optimization usually ends up doing.

As someone getting into Elixir, thanks for pointing this out. This is literally how functional programs (like Elixir) have to do loops. For Python enthusiasts: don't do this (just use a loop you lazy sod).

It might also depend on the settings of your compiler. Both gcc and Visual Studio will have tail recursion enabled or disabled according to the optimization level set.

Thanks for this

They could also enable community Translation

Yeah I'm pretty sure some ESL also will appreciate English sub especially complicated topics like this.

We are in the process of putting the subtitles together.

Graham Hutton Great😃

Subtitles now up!

lolz

cringe

Python or any other language with arbitrary precision integers can still calculate and display it. I just tried it out and I can do 100,000! without problems in Python but 1,000,000! takes a bit too long to calculate so I couldn't be bothered to wait until it finishes. However, I see no reason why it wouldn't work.

I tried it out, and calculating that 1 million factorial has 5.5M digits takes around two minutes using the tail recursive version of the function :-)

@@haskellhutt nbod ycares

It's different on the stack if tail call optimization is performed. That's because it can outright replace the current stack frame, because the return value of the two calls is the same. As a bonus, tail recursion means we know the two stack frames have the same shape, and can replace the call with a local branch. Thus it's easier than reshuffling the arguments for calling a different function.

How would it be building up a stack? At least in the examples he showed, there is no stack involved, but effectively building in result variables into the call of the function. It is effectively like using a while loop but in the function definition - while input not = base case, do this other thing. (Nevermind, I don't actually know how these things are implemented. After reading a few other comments, I need to do some reading.)

It’s language dependent. Languages that support tail recreation recognize it and drop the unused stack frames. Python for example doesn’t support tail recursion so if you tried this you’d hit the stack limit of like 500, but in a language that does support it you could write an infinite loop using tail recursion and you’ll never run out of memory.

gcc and clang are able to eliminate recursion from these functions, tail recursion or not. Try it in godbolt.org.

As written, it will use some stack to a depth proportional to N. Rewriting using tail recursion means that when you reach the basse case, there's nothing else to do and you can just return. You (or rather, the compiler) can the rewrite this to use a more efficient loop. The problem with the simple recursive Fibonacci is that it calculates the same values over and over again, and this work doubles each time you move from F(n) to F(n+1)

In some languages the compiler or runtime will perform so-called tail call elimination where the tail-recursive call will reuse the current stack frame. This is done in pretty much all functional languages and also in some imperative languages although it's not that common in the latter. For example Java, Python, or Rust don't do tail recursion, at least not by default or not yet, in part also because these languages allow you to inspect the stack trace which will get messed up by tail call elimination.

@@chriswarburton4296 Thanks, as long as I know I've not been missing something this whole time :P Every language I use has loops.

Because fib needs to remember two computed values and factorial only has to remember one.

Both examples really are just iterative functions which are imo much easier for programmers to understand and don't require the compiler/interpreter to know about these and fiddle with the call stack to actually get the improvements. I'm failing to see the benefit other than to show that some recursive functions are better as iterative ones.

@@Xeridanus 1. Some functions are much simpler in recursive form because you are letting the stack do a lot of the tracking work for you for free. This is almost always true when doing depth first searches such as solving mazes. 2. Iteration is not possible in purely functional languages because you cannot set a variable more than once. Thus making loop counter variables impossible. Recursion is your only option. 3. Having a variable that cannot change once it has been defined is quite efficient when you are writing concurrent code. You can pass data by reference (which is faster and saves memory) without worrying about race conditions. You don't need locks or semaphores because the variable can never be changed. Its completely thread safe by design. 4. But this is only an advantage if you are not overflowing your stack with recursive stack frames. That is why tail call optimization is essential for purely function languages.

@@timharig all your points are just that functional languages have a massive performance flaw and this is the workaround. Is there any reason to use tail recursion over a loop in a language that supports both?

So it is very niche. A little less niche is people knowing if they write their recursion in a particular way then compilers/interpreters *might* do this optimisation for them behind the scenes.

@@joestevenson5568 I had four points. Exactly one of them (number 4) deals with a performance hit using recursion -- which is fixed using tail call optimization. Point 1 explains that recursion is often much simpler to write and cleaner to read than the equivalent iterative form. Point 3 explains that immutable variables (which requires recursion) is both safer than iteration and potentially faster than iteration when writing concurrent (ie multiprocessing) because it requires no locking when passing variables by reference, and never requires passing variables be value for thread safety reasons. There are other advantages that I did not address, such as ease debugging added by having stack a stack traffic trace of where a bug occurred. You may call that point 5.

@Xeridanus 1. Some functions are much simpler in recursive form because you are letting the stack do a lot of the tracking work for you for free. This is almost always true when doing depth first searches such as solving mazes. 2. Iteration is not possible in purely functional languages because you cannot set a variable more than once. Thus making loop counter variables impossible. Recursion is your only option. 3. Having a variable that cannot change once it has been defined is quite efficient when you are writing concurrent code. You can pass data by reference (which is faster and saves memory) without worrying about race conditions. You don't need locks or semaphores because the variable can never be changed. Its completely thread safe by design. 4. But this is only an advantage if you are not overflowing your stack with recursive stack frames. That is why tail call optimization is essential for purely function languages.

You could, but why add extra steps?

@@rogerbosman2126 because 0 should be a valid input to a factorial function. Fac(0) will underlow with a implementation that uses 1 as it's terminating case.

I'm glad somebody else picked that up as it's an error.

too real, denero destroyed me

Ayyy 61A gang

You have so funny course names. We just called the course "Programming Languages". Hehe :P

This is haskell

See Scheme 1975

When is recursion better to use (besides it just looking nice and feeling great)? The only thing I have used that I think recursion is superior to a loop would be efficient searching or sorting algorithms.

Also worth noting is that the largest factorial you can fit in a 32 bit number is 12! and as such you'd be better off just using a lookup table. as such, any requested N in the range 1 to 12 can return a value from the lookup table. For bigger factorials you can also keep values in a table for up to 64 bits or even 128 bits. Don't know off hand what the limits are. For even bigger factorials than what exists in the lookup table you can simply take the max of the lookup table and work onwards from there saving you some cycles. The same can be done for the fibonacci sequence.

Compilers are smart enough to turn recursion into iteration, regardless of if it is a tail call not. So just write code in whatever form is easier to understand.

If the compiler of the language of your choice can do tail recursion optimization, I don't think that the recursion is more expensive. Only one return address would need to be stored. There is no stack then.

No algorithm is more efficient when wrote in its recursive form. This is just cosmetic.

It's probably just not in their houses

For loops don't work in purely functional languages. You cannot have a loop counter when you cannot define a variable more than once.

Don't be so sure it's trivial. In general, languages are forbidden from performing an optimization if that optimization will become visible to the developer (ignoring cases where developers bypass safety systems and ignoring performance). Since php supports exceptions (and emits stack traces after an exception), support for a tail call optimization is more difficult. Further, it's usually not hard to convert code which can be tail-call optimized into a simple loop.

Sometimes recursive definitions are much easier to use and reason about. And tail recursion is normally optimized in many modern compilers, making it as practically as efficient as an iterative solution.

@@ccgarciab especially in tree navigation recursion just makes so much sense

that's always:D

Or you can: import tail_recursion; my_function = tail_recursion.tail_call_optimise(my_function) Then the only thing you need to do is implement some tail_recursion.py that does that or find someone who's already done it.

In imperative languages, a while loop is almost always more efficient than its recursive counterpart (if written properly, of course), because there aren't any function calls and no new stack frames are created. A while loop defeats the whole idea of recursion. Tail recursion tries to be more efficient while still keeping the recursive nature of the function. The 2 shouldn't be compared.

While this is "practical" and " efficient" its boring! Even if there is probably a faster way and I am having fun (side or school project) I'll try and move away from loops and try and do everything functionally (maybe I just want too use scheme)

Tip: you don't need a temp variable, you can do a, b = b, a+b

Tom Galonska This is of course why in Haskell we use the {-# LANGUAGE BangPatterns #-} language pragma and put exclamation marks on the go function’s arguments (like ‘go !n !a = ...’) so that they are strictly evaluated. :)

Tom Galonska (or in the case of the fib function, `go !n (!a, !b)`)

@@qzbnyv I know ;) But with that you also have to be careful, because lazy evaluation is sometimes what makes Haskell so powerful (and yes, i know that Haskell technically is "non-strict", but i don't quite understand the difference :P)

I wonder, can't the compiler figure out from the definition that it will always need to evaluate the parameters and therefore can use strict evaluation?

@@qzbnyv True, but for these simple examples the GHC compiler can figure out that the results are used eventually when optimizations turned on (strictness analysis). Nonetheless, I agree that is it preferable to write code that does not depend on compiler cleverness to achive expected asymptotic efficiency.

@@devrim-oguz Yeah, it would just take the recursive case one more time, then land in the base case for 0

What confused me about you comment is that there should always be two initial conditions for the Fibonacci sequence, no matter the implementation. But in this case the information about the second initial condition is implicit when you define fib n = go n (0,1)

I'm not sure why you would use recursion for Fibonacci sequence if memory usage is what you are concerned about thou. The sequence has a closed form expression.

​@@mannyc6649 The two initial conditions are the two values in the accumulator: (0,1). Recursion termination is not an initial condition and therefore needs to be there only once.

@@randomnobody660 These are just examples. Of course you'd use the closed form expression for Fibonacci in real life; but I suspect it's hard to find a simple-to-follow example to illustrate tail recursion that doesn't have a closed-form expression.

I couldn't agree more. Im a CS student and this channel is really inspiring to keep doing it!

I'm a professional developer and their videos are absolutely great for me too

So, am I wrong, or is this just a fancy name for redefining a recursive function as an iterable one?

Don't be ashamed to say goto.

@@JamesTM Yes the compiler will end up producing something that basically is a loop. But all you used was recursion.

James Tanner It’s actually quite fun - If you play around with different levels of compiler optimisation, no optimisation and -O will generally produce slower code than doing the loop yourself, but -O2 will be roughly the same as -O2 on a loop implementation, and -O3 the recursive one will actually be faster! (Experimentation done with a Collatz algorithm)

@@casperes0912 I'll admit, almost all my programming these days is in non-compiled languages. So I don't really get to enjoy the benefits of compile-time optimizations.

beginner here, so in this case by using tail recursion in fibonacci do the space complexity become o(1)?or it stays same i didnt really understood...

@@tinashine6544 Yes, if tail recursion is used as described, it's constant space efficiency (3 integers, a, b and n). If you consider that larger numbers may require more storage, it coud be O(log n), I suppose.

... and vise versa.

This is really useful when writing GPU code, which doesn't allow recursion.

Chris Warburton I don't see it as "easier to understand" I see loops as a lot easier to understand. Whether the loop is implemented as a "re-start block" until some condition, or just "do block" N times. The only time I find real recursion actually useful in practical programming, is when you need to do double recursion, such as when dealing with a tree like structure. That is doing a full traversal, or rebalancing, not just a simple search down to the leaf. Only then do I find recursion in any way simpler. If it is a loop, not requiring a stack (procedural, or data stack), it is already equivalent in efficiency terms to tail recursion.

@@AntOfThy Some problems are easier to understand as loops, some are easier to understand as recursion. If it has a recursive definition mathematically, it's likely easier understood recursively. Spend long enough writing nothing but Scheme code (without the named let construct) and you start to see recursion as easier to understand. Prof. Hutton didn't show any, but in many cases you don't need the helper function and the recursive calls are really straightforward.

I heard that it is possible with some compiler trickery (CPS (Continuation Passing Style)) for functional languages. But I can't wrap my head around how it is tail-recursive at all even after writing multiple languages.

You can't do everything recursion does with just loops. i.e. Loops can be written in a recursive form, but not all recursive forms have a loop form.

Not everything can be computed using for loops for example you want to compute all the sets that are of length k. As far as i know it will be very hard using loops but its easy using backtracking.

Recursion is also more readable and easier to analyse than loops. The time complexity of quicksort for example can almost immediately be seen from the structure of the program.

@Xeridanus 1. Some functions are much simpler in recursive form because you are letting the stack do a lot of the tracking work for you for free. This is almost always true when doing depth first searches such as solving mazes. 2. Iteration is not possible in purely functional languages because you cannot set a variable more than once. Thus making loop counter variables impossible. Recursion is your only option. 3. Having a variable that cannot change once it has been defined is quite efficient when you are writing concurrent code. You can pass data by reference (which is faster and saves memory) without worrying about race conditions. You don't need locks or semaphores because the variable can never be changed. Its completely thread safe by design. 4. But this is only an advantage if you are not overflowing your stack with recursive stack frames. That is why tail call optimization is essential for purely function languages.

@@1990Hefesto1990 so there are programs which can not be written with loops in any way , but they can we written easily with recursion?

Recursion and loops are equivalent. Any loop can be written as recursion and any recursion can be written as a loop. In fact, computers actually can't do true recursion. They implement it as a loop at hardware level. Converting loops to recursion is simple. You just create a function that performs the loop body and if condition is met, calls itself. It passes all the variables that persist between loop iterations as arguments and return values. Converting recursion to loops is a bit more elaborate. You need a stack data structure. You can push and pop values and you can access/modify values by their position relative to the top of the stack. You can then implement the recursion as a while loop with a giant switch statement inside it. The switch statement switches between different "function bodies". The stack holds all the local variables, including arguments and return values. It also holds identifiers of functions (ie, which function is called and where should it return), that the switch statement uses to pick the right code each loop.

@@KohuGaly I'm not sure your statement holds water. There is apparently thus a thing as non-primitive recursive functions, with the Ackermann function as an infamous example. On the other hand, since we can compute the Ackermann function on real computers, you are right that there is evidently a iterative way to do so. I suspect that that would require rapidly growing stacks, though, and that it thus is not considered an "iterative" solution?

@@jgreitemann you missed the existence of while loops. looping functions only allow primitive for loops. But it is quite trivial to implement the ackerman function using while loops

@@jgreitemann the general conversion of recursion into loops that I outlined is more-or-less how function calls are implemented in machine code. My solution has some extra fluff, to implement "call" and "return" opcodes using while loop and switch statement. You are correct in that this kind of pushes the definition of iteration by having a dynamic data structure to a implement stack.

@@jgreitemann loops that can only loop a value that has been defined before the loop was started (like for loops) are equivalent to primitive recursive functions. But while loops that can modify their termination condition while looping are just as powerful as the most complicated recursion. Like @KohuGaly said, for computers recursion and loops are equivalent and at a hardware level all loops and recursions are implemented as "go to line x" statements.

Same

Functional languages recognize you are using tail recursion and don't use the stack. They just do a loop with whatever is inside the recursive call. Don't try this with ruby, python, java or go, for example. You will get an stack overflow. gcc can detect tail recursion usagfe in c++ and also optimize it, but not sure if does that automatically.

An optimizer will notice that the last instruction of the function would be another function call, which it can turn into a jump instruction instead. This then gets rid of the entire stack frame and effectively turns the recursion into a loop. That's often only an optimization though, not a guarantee. Though with keywords such as `become` it can be guaranteed at the language level.

This is not necessarily a limitation in stack frame-based languages, as it's possible to add tail call optimization. One example is ECMAScript 6, which includes specification about TCO. V8 (Google's engine used in Chrome to run JavaScript) did have an unstable implementation of this at some point but was removed due to drawbacks like losing information about the stack during debugging and breaking software which relies on stack frames to collect telemetry. There are solutions to this, but ECMAScript is in a unique position in that the point of the specification should always be backwards compatible.

Because the recursion occurs on the tail call :D

cringe.

Not really... Try it with Clojure for example. If you try explicit tail-recursion via "recur", it will calculate the answer for fibonacci of 1_000_000 pretty fast. Memoization will fail because you still need to create many stack frames. However, you are right in that both are great optimization techniques.:D If you set up a function with memoization and you can save the results so efficiently that you can save the result for fib(1_000_000) and you run it again, you only need to look it up. With tail-recursion, you would have to calculate everything again. Of cause you could combine both though.

😉 Drop them both in compiler explorer (godbolt.org). Set optimizations to -Os for gcc. Check assembly output. By the time you strip out debugging data and the compiler fully optimizes everything you will have difficulty seeing meaningful differences.

Yeah, if a new stack frame doesn't get established with each function call (which it isn't and is exactly how tail recursion saves memory compared to normal recursion) this is just a fancy way to write a simple for loop. I'm genuinely curious if this has any practical benefits or is just dabbed into because of the intellectual stimulation.

Hi. In case you didnt find it: Some functional languages don't support loops (or implement them with tail recursion). This reduces the number of native expressions you have to implement in your compiler/interpreter in case you want that number low. So instead of having "if" and "while", the "if" keyword will be enough. Then there's a compiler-technique for functional languages called continuation-passing-style (CPS) which can be easily used for tail-recursion but does not lend itself to loops well. The opposite is SSA-form for imperative languages, which plays well for loops but simply sub-optimal for functional languages. :)

Almost forgot: Some languages don't allow re-definition of variables to avoid doing many lookups. That's why you don't put an accumulator outside a loop in scheme or haskell. Thanks for the constructive question. Most others just said that loops are better without giving it any thought. (You clearly did by thinking of the accumulator and stuff) :D

whooops

Christopher G Hi! Professor Hutton teaches (and researches) the style of programming known as Functional Programming, with his videos using the Haskell programming language to demonstrate the principles of Functional Programming (FP). There are plenty of other videos out there on the interwebs showing you how to do traditional Imperative Programming loops. But as these videos by Professor Hutton are still on the basics of FP, you would only really include a loop if your goal was to contrast the FP style of programming with that of traditional Imperative Programming. But they can’t do that in every single FP video that they make. Or, at least, I hope they don’t. At some point you have to start assuming interested people have watched the earlier ones in order to make progress :)

@Mike If they have funtions, they have jumps. If they got jumps, you can make a loop. But I simply did not know this was looking at it from a pure funtional language viewpoint.

Yo, if you're going to make such suggestions, how about suggesting specific examples that meet your requirements? By taking that extra step, you might think it through and realise that any such non-trivially-de-recursable algorithm would be so complicated to explain that the actual topic at hand (tail recursion, remember) would be completely overshadowed.

I'm pretty sure it's not. For example, if you're performing recursive operations on a tree, each node can have multiple children and you have to call your function on each child node.

Technically yes, because any recursion can be written as a loop and tail recursion is just loop implemented as recursion. I say "technically" because in order to convert general recursion into loop, you need to use stack data structure (basically dynamic array). Which basically means you are manually recreating in higher language what your compiler would compile your function calls into in machine code.

@@derekeidum1307 For trees, it's the data structure that's recursive. The routine that walks through it doesn't need to grow a stack with recursive calls. For example, if your tree has bidirectional pointers to navigate either to children or to parent nodes, I'm sure you can use the same CPU register to hold the current node address and mutate it as you traverse the tree.

@@retropaganda8442 I don't think it's that easy. You would still need to keep track of which child nodes you already traversed through because if you go back to the parent you need to know if you need to go to another child element of that node or back to the parent before.

No, there are some recursive functions which are not bounded (and hence cannot be implemented as a for loop). The most famous example of this is the Ackerman function.

Yes, tail recursion can easily be transformed into an iteration -- these are just simple examples to illustrate the idea of tail recursion, not applications where you'd actually use it in real life.

remove literally from that sentence and it is precisely the same, only more efficient!

Sheepless Knight, did you study computer science?

RainDog222222 Why did you include “precisely” in that sentence? It’s already implied in “the same”.

skoto “Precisely the same” -> === “The same” -> ==

@@RainDog222222 That is veritably true. :)

How most interpreters I saw do it: Step 1: Set up a small stack where you save the ids of called functions. Native stuff like "if" does not go on the stack, but operators +, -, *, /, &, ... do. Step 2: When you call a function as a parameter to the 2nd function on the stack, you can not tail-recurse. (Think of Ackermann). In that case, put it on the stack. Step 3: When you call a function and its id is not equal to the last one on the stack, put the new function on the stack and do not tail-recurse. Step 4: When you call a function and its id is equal to the last one on the stack, you can tail-recurse. Step 5: Evaluate the parameters of the call and tell them that they are the parameters to some other call and save their results somewhere. Step 6: Now go back to the beginning of the last call. This can be done via a jump or exception throw. Step 7: Done. Notice that, as explained in the video, the stack is not expanded if a tail-call is done.

True, but in many cases translating a recursion into a loop requires you to store intermediate data into your own stack. Mind you, this is often necessary for deep recursions to avoid a stack overflow exception.

I would say "Most useful recursive functions". However, I would give you two counterexamples: --Tree traversal. You can do it yourself, but you have to maintain a stack yourself with your history. --Ackerman's function. (not that you'll ever need it...)

​@@johnlister You can make Ackerman's with a loop and a stack

@@arturgasparyan2523 You absolutely can. Any time there's recursion, you can turn it into loops with a stack. That means you're doing the work hand building the stack instead of the run time system building stack frames.

@@johnlister That is true. My Java implementation was 4 times slower than the native recursion method 😒 I guess sometimes it's better to let the compiler do its thing.

Python doesn't support it, no, but there is a way, so I'll shamelessly copy-paste a comment I made. 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)

That's a thing with functional languages. They are very, very different from imperative languages you might be used to. (It took me 7 months to "get" functional languages and I am not embaressed to say it...) Take a look at continuation-passing-style for functional languages. It is a technique for compilers. It lends itself well to tail-recursion, but not to loops. SSA-form for imperative languages is better for loops. There are some great talks on it on LLVM conferences. Tldr: Haskell != C. Thanks a lot for aaking. :D

Hi. It's cool that you grasped the concept! The language being used in the video is Haskell and the thing with haskell is that brackets confuse it. In general it is better style not to use too many brackets.