Tail Recursion Explained - Computerphile
HTML-код
- Опубликовано: 26 май 2020
- Improve the efficiency of recursive code by re-writing it to be tail recursive. Professor Graham Hutton explains.
EXTRA BITS: • EXTRA BITS: Tail Recur...
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottsco...
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com
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.
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
No stack frames were harmed in the making of this video.
lolz
cringe
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.
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!
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)
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
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
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.
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"
The explanation was very clear and easy to understand. Thank you for making this world a better place.
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.
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
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.
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.
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
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
@@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 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.
Because the recursion occurs on the tail call :D
CPython: I have no idea of what you are talking about...
I cant discribe how your lesson is helpful. Thank you so much. Where is the button for 1000000000000000000000000000000000000000 likes?
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.
I'd like to see prof. Graham Hutton explaining Continuation Passing Style, it could be a nice next step after Tail Recursion. 😄😄😄
This is why teaching assembler still makes sense. This kind of problem is better explained at machine level.
Nevermind that 1 million factorial has more than 5 million digits in it!
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
I keep finding great litle tools here that might help me write better scripts. Thanks!
Same
I'm not a pro on this, but what is the difference between the go function and a for loop? The two examples the prof gave here can be replaced by a for loop doing essentially the same thing as the go function. Is it true that every tail recursion can be replaced by a for loop? Can anyone give an example that must involve a go function?
I'm thinking about something like this:
accumulator = initial value
for (i=n, i>=0, i -= 1):
accumulator = foo(i, accumulator)
return accumulator
where foo is non-recursive
This was actually pretty interesting. Thanks.
Thank you Mr.Graham ! Really enjoyed this Lesson.
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
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.
I coded a tail recursive function literally a week ago and I had no clue this was what it was called!!!
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. :)
My favourite Haskell professor 👨🏫
Each problem that could be solved with tail-recursion can be solved with a loop.
... 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.
10:47 - For anyone that's confused about this, he's right, this really would take a long time because _fib(50)_ calls _fib(49)_ and _fib(48)_ each of which make two calls which in turn make two calls and so on, and before you know it, the program has crashed because the call-stack has been exceeded because the number of calls grows outward at an exponential rate (to 1.5 quadrillion function calls).
Thanks, was wondering about this
The call stack of fib(50) would only be 50ish calls deep. The tree of calls is very very wide (contains 1.5 quadrillion nodes, assuming you did your calculations correctly), but is only 50ish levels high. So it'd take a long time, but for no reason related to the call stack.
i my opinion the most important thing to know about recursion is that every recursion can be written in a loop (additionally that loop optimization is a thing^^)
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.
So you are just developing an iterative formula and calling it tail recursion.
Can this method be applied to say the Ackerman function
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.
This blew my mind the first time I watched it,
Also I thought this came out like 4 years ago, lol
Can someone clarify something for me:
I think tail recursion still uses *some* memory due to building up a stack. Am I wrong or do modern languages abstract this and actively eliminate the stack when it recognizes properly formatted tail recursion?
It makes sense in theory that nothing is really being remembered outside the ever-changing arguments, but I can't help but feel if the stack really does grow and consume *some* resources, that any infinitely large recursion will ultimately consume all the resources.
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.
3:09 problem with the simple recursion
3:58 potentially inefficient in terms of memory use
4:26 tail recursion
One humble suggestion for improvement: a more consistent use of parentheses and commas would be helpful. Example: "fib 4" becomes "fib(4)" and "go n a" becomes "go(n,a)". Python code follows below:
def fibber(n):
#uses recursion
#instructive, but sloooooow and inefficient
if (n==1) or (n==2):
return 1
elif n>2:
return fibber(n-1) + fibber(n-2)
def fibbest(n):
#uses tail recursion
return go(n,0,1)
def go(n,a,b):
#for use with fibbest()
if n==0:
return a
elif n==1:
return b
elif n>=2:
return go(n-1,b,a+b)
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.
This is very elegant
How did they come up with this? I'm interested in the history of this now, how did they figure it out? It's extremely clever.
The tail-recursive formulation basically does the same thing that an iterative solution would do. However, IIRC there are problem which are either only computable by recursion or for which only recursive solutions are known. Are there any cases where one of those can benefit from tail recursion or (as I suspect) is it the case that once you can rewrite it as a tail recursion, you might as well unroll the recursion into a loop and end up with an iterative solution, hence precluding any of those recursion-only problem from tail 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.
The comments are much better than the actual video. If you keep making stack frames there'll be barely any difference.
Can somebody explain Why should we use recursion if everything we can do with recursion can aso be done with loops more efficiently?
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?
But these recursive calls still increase the size of the stack, right? At the end of N iterations, you still need to return the value through those N calls. You could implement 'go' with a loop and break at the base case, but actually calling a function would increase the stack every time.
Disclaimer: I haven't actually watched the video yet
The idea behind tail recursion (as I understand it) is that instead of adding calls on the stack, you modify the existing call. It's functionally identical to a loop. You just store your result in the "tail" instead of in a temporary variable.
Actually, it depends on the implementation of the compiler of your language e.g. in Java tail recursion doesn’t provide any optimisation as it can’t discard stack frames.
IIRC, I read somewhere that it may be implementing by compiling the recursive function in such a way it pops the arguments before calling itself over (asd pushing the new parameters). You can also just modify the parameters on the stack and JUMP to the function (like calling without pushing new parameters).
Either way you end up "reusing" the same stack frame.
As I said I remember reading it somewhere and I can't really confirm it is like that. Never actually looked up implementations or actual compiler theory about it.
Non Tail Call Optimized language compilers will act like that. TCO compilers will release the stack of all the intermediate calls since they are not useful for the final result. With such compilers tail call recursion is as efficient and fast as a while loop.
There's a different kind of pollution which is possible in lazy evaluated languages. Since they delay computation until it's necessary every call the recursive function does will not be executed but they will increment the thunk size (hence memory consumption). That is why those languages offer strict evaluation features.
This was so helpful. Thank you so much!
Excellent vid
Isn't that tail recursion the same trick also known as memoization - at least in this example ?
From what I gather, there is one low-level language thing called "tail call optimization", that is not necessarily related to recursion, but is needed in order to have efficient tail recursion in practice.
Tail recursion allows us to leverage TCO to avoid overflowing the stack, but saving the results of previous computations to avoid repeating them is by definition memoization, isn't it ?
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.
I missed this one. Thanks for teaching, me.
THANK YOU FOR EXPLAINING THIS!!!
I wrote some code for figuring out the Fibonacci Sequence:
int fib1 = 1;
int fib2 = 1;
int output = 1
for (int i = 3; i
my time with f# has made me write all my recursive functions with the fac/go format
In languages with stack frames, won't this kind of recursion still build up memory usage by adding more frames to the stack as it goes?
Also, I notice that it has a single passed "state" as it moves along. So, it seems to me that, by definition, you could rewrite any tail-recursive expression as an iterative expression in a fixed memory space.
Am I missing something? Is there a case where that's not true, or where the recursion would be more efficient and/or inherently desirable?
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.
So I had to try it, I wrote two perl scripts implementing the two factorial algorithms, but the RSS value reported by ps is the same for both (2008 for fac(100)).
Defining tail recursion also give you the opportunity to do other things just once instead of every recursive level, like asserting that n is an integer greater than zero.
Love this video with Prof Hutton !!
more than amazing video, thank you so much
I would have preferred that you include how a tail call is different on the stack, or is there a part 2 coming?
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.
Thanks for the great content!
Thank you so much!!! I've been learning Haskell and this is super useful!!!! Loved to learn it :D
what will be the time complexity and auxiliary space of a tail recursive function ? since in modern compilers it is not considered to be recursive.
This guy is great
Your videos are excellent
Isn't this just an iterative loop with extra steps?
cringe.
I wrote such recursion for fibonacci series on my own, I had no idea it had a name!
Thanks very much this was just what I was looking for.
So the go function is overloaded to return a value for the second base case but how do we reach the first base case where parameter n==0 as n reduces in the function call.
TIL I've been using this for a while. A bunch of programming games don't have a stack or anything, so you need to implement this sort of pseudo-loop to get recursion to work right.
This might explains why my simple up arrow notation program chews through 16 Gb of ram in like 2 min when I plug a large power of 2 into it. It must be trying to keep track of 2, 4, 8 etc until like 2^1000000000000000000000 in ram
whooops
I remember reading this early into SICP
Can someone explain how using tail recursion is better than a for loop? Surely you can just have the accumulator outside the scope of the loop, and just run through from the starting case until the base case?
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
This was a pretty fun watch, thanks for sharing!
It looks like you're basically just turning the recursion into a for loop, by adding an iterator to count up from the base case rather than "normal" recursion to drill down into it. Which makes me think I should just use for loops instead of recursion wherever possible (unless threading is an option) 😛
can you do this with Ackermann Function ^^
Edit: Ok. Would be nice to see the EXTRA BIT in the EXTRA BIT ^^
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.
Pretty satisfactorial!
The one thing this seems to be missing is how they use tail recursion to optimize the call stack though.
Isn't the go function for the Fibonacci numbers just a for loop written as a recursive function? That is how we calculate without using a recursive function.
int fib(int n)
{
if (n=0)
return 0;
for (a=0, b=1; n>0; n--) {
temp=a;
a=b;
b=temp + b;
}
return b;
}
Am I wrong? How is recursion better here?
I would really appreciate explaining how to figure out the helping function for tail recursion.
In cases like factorial and fibonacci you always use an "accumulator" as shown in the video. So the first step of thinking is "Which value/calculation can I use an accumulator for?"
For some functions you don't need to do anything (like foldl in Haskell), for some it's not worth a re-write (like foldr in Haskell) and for some it is almost impossible (like the Ackermann function explained in another video).
Not my Oxford interviewer telling me to remove my "unnecessary" accumulator variable in my Maths and CS interview...
Is it always possible to convert a recursive algorithm into a tail recursive form
?
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.
I love yo6r videos Prof Graham
I love this. Thank you!
Thank you.
Both of the examples given are trivially and more efficiently rewritten as iterative loops. In fact it looks like tail recursion is being used to dress up iteration so that it looks like recursion. It would be nice to see an example where the recursive solution is superior to the iterative one.
I suggest you try coding the "Sieve of Eratosthenes" for an arbitrary number of results.
That just sounds like a for loop with an extra step
😉 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.
I tried this in Python. The tail recursive version of Factorial had no improvement in performance over the standard recursive version but for Fibonacci, it was a HUGE improvement. Lightening fast.
In case of the factorial, the tail recursive version is more memory efficient, especially if compiler optimizes it (basically converting it to for loop). As far as speed is concerned, they should behave the same. Especially in interpreted languages like python, which don't do much of an optimization.
@K.D.P. Ross "despite not knowing a lot about it" ;-)
I thought tail recursion was useless in python...?
It's faster only because the algorithm is more efficient than Fib(n-1) + Fib(n), but it still uses regular stack frame recursion in Python, so it is memory-inefficient and will terminate above Fib(1000) (the default limit of recursion call depth in Python)
What a nice explanation sir ♥ really appreciate
Thank you! I’m coding this one later
There's an error in that function right at the start. That's because the end condition should be 0 as factorial 0 is 1. It may seem counter-factual, but it's part of the definition, and the reason that's the case is because it's to do with the way a number of things can be arranged in a set. An empty set has 1 way of arranging it, as does a set with a single item.
A function to return 0! should return 1.
You're totally right, the function could be expanded to 0! = 1, but it still works and gives the right results. I think Prof. Hutton wanted to simplify the example, and avoid confusion by avoiding this counter-intuitive case. Have a nice day!
@@pqul2828 It doesn't give the right result as it doesn't work for 0!. I realise it doesn't affect the rail recursion issue, but details matter.
You forgot to define that fac 0 = 1 (This is not needed for the programming, but for mathematical accuracy. Otherwise fac 0 would not be defined and wrongly output an error)
The go function in the end if just a fancy iteration? It seems to do the exact same thing as the following pseudo code, or am I missing something.
answer = 1
for i in [1 to 5]:
answer *= i
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
the more you know
while learning about erlang, i got to see this technique of carrying information about the value to be returned in the arguments of an inner function. and it was called "currying", not tail recursion
tail recursion i thought of as when the called function is being called again on its last expression, but for that to work correctly, and to not explode the stack, the compiler/interpreter for that language would have to have implemented tail call optimization
there's video on currying on this cannel too IIRC.
Currying is converting your multi-parameter function into a kind of "chain" of single parameter functions. It makes partial evaluation more ergonomic, and types more consistent.
List is the first thing that I remember when reading the title. It's always follow up tail recursion.
Hello,
thank you for your great videos,
the videos contain a lot of technical details
i notice that most of the videos are without subtitles,
it will be great if you can add at least english subs
Thank you so much,
I have tried a few compilers in godbolt.org, and most are able to transform a recursive function into iterative, regardless of it is tail recursion or not. I would say, trust your compiler and write the function in the manner that is easier to read. Otherwise you are just making your code harder to maintain for no gain whatsoever.
*Cries in interpreted languages*
First, only tail call recursion is easily optimizable to iterable by a compiler. So all the examples you tried, for sure had a tail call recursive equivalent. The tail call optimization is simply a loop with whatever is inside the function. Very easy.
But detection is complex so not all languages have than optimization, java, go, C#, python and ruby don't have it, for example. You will have stack overflow.
So better only use recursion on functional languages. In all others, much better iterate.
@@framegrace1 if the goal is to prevent stack overflow because you expect the recursion depth to be very high, absolutely, you should make your function iterative yourself instead of trusting the compiler. But otherwise, if you care enough about performance to be doing micro-optimizations like this, you should probably be using a different language. This seems to be implemented in LLVM, so I would expect any compiler that uses LLVM as the backend to support it.
As always, thank you! these videos are a great resource.
I hope he write more books soon.
Ok, but how does the system know to not keep track of the stack ?
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.
Thanks for sharing~
U can just do this within a for loop right? Why need recursion?
I was jsut going to ask about some Python example but I see there is no support. Anyway. Great video and love to see it. Please let covid end and we can get back to magic markers and paper.
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)
Can someone explain why this form of tail recursion (at least the ones demonstrated in the video) aren't completely equivalent to a for-loop? The Fibonacci example in particular seemed like it was just counting down from n to 0, which you could do with a while or for loop.
When might you want to use tail recursion instead of loops, if the structure is so similar? I'm asking seriously; my background in CS is pretty limited!
very cool
Yesss
How to decide fib will be use a pair, the factorial only use one number?
Because fib needs to remember two computed values and factorial only has to remember one.
In other word, its a way to simulate a for loop in language that dont support it :P !