The separating line for me personally to decide between using loops and recursion is whether I'm looping over an unknown-sized structure or a known-sized structured. Say looping over an array, that is a loop. Walking a deeply nested tree, that will be recursion. Forcing the use of one another blindly is like trying to force a wrench into hammering a nail, the nail does get in, but neither was the wrench designed to smash nor is it comfortable to be used for smashing.
I think that's a reasonable heuristic. I do find looping easier when it comes to arrays, for sure, but I find HOFs even easier than that, especially when you get nice pipe operators. It's much a matter of personal preference - this video is meant to be a bit tongue-in-cheek 😉
I don't know exactly what it is for me, but I know there are sometimes I'm trying to work something out and even though I know all recursive solutions can be "unrolled" into a procedural loop, I simply cannot easily think of the loop version.
@@JayLooney For me, that depends on whether the loop is "bounded" or "boundless". "Bounded" as to say you know the size of the structure you need to loop over, e.g., enumerate all values in a 500 elements array, and these will always be a simple procedural loop. "Boundless" as to say you do not know the size beforehand, or the size is depending on the individual elements itself, like a tree structure, you will never know how many levels down there until you actually walked it. For these problems, that will always be recursion for me.
@@IsaacHarrisHolt Except that not every compiler supports TCO, so you cannot blindly trust the compiler to Do The Right Thing(tm) in case there's a tail call.
tail recursion just feels like loops with worse syntax to me, except maybe in haskell where you have pattern matched function definitions. I do like recursion for tree problems tho since you're actually using the stack frames as intended (with an iterative approach literally requiring you to explicitly define a stack to keep track of state)
Oh for sure, there are some problems that loops are probably better suited for. I never said you HAD to replace all your loops with recursion, I was just making the point that you COULD 😉
I really liked one bit in the video that was obvious, once Isaac said it, but it genuinely didn't occur to me: "break" is just returning early and "continue" is just calling the function again early. I mean, yeah, so simple - thanks, Isaac, that actually really helped!
@IsaacHarrisHolt Yeah, I was surprised how controversial it was. Louis Pilfold is seemingly a popular streamer relative to coding, so I thought this would go over really well. But maybe as some solace: I'm very new to both low-level and functional programming and the disagreeing comments were useful as they pointed out limits I wouldn't have been aware of and can now anticipate. So, at least it was a kinda spirited discussion? Anyway, thanks again and keep up the great work - the Lustre content is another banger. :)
I write primarily number crunching code - mostly signal processing and numerical math, sometimes a bit of graphics and image processing. I really don't think that I want to implement a Gaussian blur filter recursively without any loop over the pixels, for example. How would that code even look like?
The thing is that I would much rather use an imperative instruction when convenient rather than shooting myself in the foot performance and readability wise for the sake of "purity" (I don't think recursion is inherently purer than a loop). Jump exists so you may as well use it without returning shenanigans.
You're unlikely to encounter a performance hit if you're doing tail recursion (which, if you're replacing a for loop, you probably should be), and it's no less readable. Recursion can be a lot more "pure" - loops have to modify state, and can therefore be misused to modify state external to your scope. While you can, of course, modify state in a recursive function (if your lang allows it), you don't have to, and often shouldn't if you want the best performance.
In my experience with the real world, recursion will lead to far more crashes than any other construct you will ever use. The fact that you're using stack memory instead of jumps in a program's flow is too big of a downside to ignore.
@@IsaacHarrisHolt Well, tail call recursion is a special case. Not all loops can be implemented like this. For example, search and sort algorithms will rarely fit that mold. Also, not all languages support this optimization. Java, Python and Go are three examples. Those always (or in some cases selectively) use the stack, even if the function is tail recursive.
recursions ? did he just finished a online course ? it is far to soon to make video about programming my little padowan ! do some real programming, not redos !
I'd like to see some practical real world cases where to support your claim that the compiler can "usually compile recursive code just as well as iterative code". I work on high performant code at my job and usually the "should I implement this function recursively or iteratively" debate goes like this: 1. I want to express my idea into code 2. I choose to implement it recursively, since I feel it is easier 3. I profile the code and regret my decision 4. I unroll the recursion into a loop 5. Win (big time) I like to think of my code in a data oriented way. Since all computer engineering is, is taking data as input, transforming the data, and spitting out the tranformed data as output. The number 1 most important thing to do this efficiently is to first of all, know your hardware, and second of all, lay out your data in a way that you know the hardware will be able to execute it efficiently. The reality is that most of our modern hardware has become pretty good at performing repetitive tasks on contiguous blocks of data. So naturally, I try to lay out the data in such a way. Loops (especially over sequential data) are very easy for the compiler to understand. So I trust the compiler to do a relatively decent job compiling my code to SIMD instructions and to perform other optimisations. Recursion on the other hand is complex, since the logic is divided in the multiple recursive calls. But all the compiler sees is just a regular function that happens to call itself. On top of that, you're often times breaking up the single data structure that you could have in a loop into multiple singular "recursion states". Good luck to the compiler figuring out how to stitch everything together efficiently. Aside from my concerns as someone who is tasks writing fast real world code, I think recursion has a beauty. It is simple. It is expressive. It is powerful. I prefer it over recursion if I'm just zen, drinking my tea, listening my chill music playlist, while implementing my function. When my piece of code is just something small off the hot path, I use it. And I'm happy with how it looks. But in hot paths, when the stakes are high, I avoid it as much as possible. I just don't trust the compiler enough to make anything good out of it. And whenever I feel like "recursion just makes more sense" or "a regular loop is going to be messy", I reflect on it and probably conclude that the data layout is not good enough. I have to rethink the models. I think your video was nice. Informative, and provides a little peek into the magical world of functional programming. Just think the statement that recursion usually doesn't kill performance is false. Keep up the good vids :)
The optimisations will be very language dependent, but often tail-optimised recursive calls will be compiled to the same or similar assembly to a loop. There's a good Twitter post showing the difference SOMEWHERE, and iirc the recursive example actually produced fewer instructions. You can get SIMD optimisations out of recursion, but yes, for highly performance critical stuff, loops are probably your friend (and I said as much in the video!).
you really nailed the beauty of recursion, it's kind of rare to find situations where it's more applicable than alternatives, but it's such a pleasure to write a recursive function, like a functional fractal
Clojure has wonderful loop/recur construct, which is really beautiful in my opinion because it looks like a loop but behaves functionally without need of tail call elimination.
You never justified why recursion should be used at all. Yes, recursive functions can be limited to only modify local state if that is how you write them. But why? Why is that better? It is just a different way of thinking about a problem, but programming is in the end neither about mathematical functions and proofs, nor about state or objects, or about memory management. Programming is about transforming data and what should be the focus is how data is transformed the most efficiently, which depending on your circumstances may include the time it takes to for new people to read and understand your code.
This video wasn't really meant to be a "omg you should always just recurse" - it was mostly a bit of fun saying you CAN just recurse. Like I said in the video, recursion is best for traversal problems because it allows you to only focus on the one item at a time very simply.
@@IsaacHarrisHolt Recursion is best for problems where it is easy to divide the problem into different easily defined and solvable states but where it is difficult to hold or even imagine the big picture and/or the many different paths it can take in your head. Traversal problems can be one example.
@@IsaacHarrisHolt This! exactly. Due to my job and the languages of my hobbies im in the same boat. BUTTTT theres really good ideas you can always take across.
Question: is organizing your loop as a recursive function "really" eliminating state? I hear that functional programming is meant to make things easier to reason about, but I don't believe making your variable an explicit part of the function necessarily changes the fact that not-always-trivial transformations may have to be done to it every iteration, and you're effectively still mutating it every time the function recurses, just not literally.
>Question: is organizing your loop as a recursive function "really" eliminating state? Nope, it just hides it. But what functional programmers state is that they eliminate external state because all states are internal. But that is only true if you write your functions that way, and you can do the same with a loop through: { //declare all data you need in the loop for(... //return answer here } And in reality it doesn't matter because data is state, state is data, your functions will only ever be called when your program reaches a certain state so your functions are always relying on external state meaning that you can't reason about your program any easier. It is more or less an ideological thing rather than a practical thing.
I find it curious how the Fibonacci sequence is often one of the prime examples of how to do recursion, but at the same time the loop version is soo much better. It cannot be tail recursed normally, and it's not a particularly common pattern, so you can't necessarily rely on your compiler to have a specific optimization for it. If it's not optimized you end up calculating numbers exponentially more. In the meanwhile the loop is just simple with two state variables and can calculate any number up to system limits.
I agree with what you're saying. I think it's mostly because the sequence is inherently recursive (you could think of it a bit like a tree), and it's also something that most people understand, so you're not having to teach a new concept like graphs or trees on top of recursion
I believe that Fibonacci sequence being used as an example in schools and other training material is one of the reason why recursion is harder than it has to be for many. You present a nail in a board, but instead of reaching for a hammer you tell people to use a wrench to punch it in. It is better to start with problems where recursive thinking is not only better but where the actual usefulness of recursion shines. I.e. present a nut and bolt, not a problem where everyone will think "geez, I wish I had a hammer".
A fun fact BTW is that the loop solution to Fibonacci sequence is the optimal, bottom up DP solution. Just because DP builds on recursion relationships doesn't mean that the solution must use recursion, because just the same as the compiler can turn a recursive solution to a loop so can you, and in the case of Fibonacci if you optimize the recursive solution you get the simple loop. Fib is literally the absolutely worst problem to use when teaching about recursion because all it teaches is that recursion is stupid. Which it isn't.
Wdym by "it cannot be tail recursed normally" ? (define (fib n) (define (fib-aux n a b) (if (= n 0) a (fib-aux (- n 1) b (+ a b)))) (fib-aux n 0 1)) Is this not tail recursive ?
some people tend to forget that a lot of features present in some programming languages do not come for free , like inheritance , virtual functions and recursion, whilst it depends on the use case iterative implementations sometimes far outperform recursion for the simple reason that recursion has overhead whether it is in interpreted or compiled languages .
@@IsaacHarrisHolt Which makes it even less appealing to use recursion, as iterative loops are simpler to read, understand and maintain and they don't cause memory overflows.
@ especially for tree traversal, I wouldn’t go with a recursion algo! Most JS/TS libraries use recursion and they all run out of memory at a certain tree size. In compiled languages, it’s less of a problem of course, but JS is the most used one, although for tasks like this Go or Gleam would be much better.
Loops are more efficient for e.g factorials because they use less memory (no stack frames) and avoid the overhead of recursive calls. Recursion is elegant but can cause stack overflow for large inputs
Not if you've got tail call optimisation! For example, here's a tail-call optimised factorial function: playground.gleam.run/#N4IgbgpgTgzglgewHYgFwEYA0IDGyAuES+aIcAtgA4JT4AEA5gDYQCG5A9IgDpK+UBXAEZ0AZkjrlWcJAAoAlHWC86dRADoAJhCECGs0axz4acVk1kBWefN4BfXr3FijJqGYtJFyiXU0IAfUNjU3NZJEw6dFskBz4kZ38g11DPSKMcbxU6HFYYCDoJH1VVdDoAWgA+Ogzs1Qkqv0Dgtw9wiqjIiQAqGpxM7Li7EDsgA= If you look at the compiled JavaScript, you'll see that it's essentially a tight loop :)
I avoid recursion as much as possible, since it creates a new stack frame every time it calls itself, which can lead to a stack overflow if you're doing it wrong. Especially true in embeded softwares and really long recursions. Just be carefull with it..
In my career I’ve used recursion ONCE, and it was only because the limitations of the platform I was using (Salesforce) made a for loop impossible. Though I suppose I also once defined a recursive database formula. That was pretty neat.
I agree with the loopy not mattering that much stuff, but beyond raw speed you have things like GC cycles happening more frequently in some runtimes. anyway, I think its foolish to focus on such stuff when you are trying your ideas out. Code must first work, then be pretty, then be optimized for a context.
I wonder how recursion will tackle any or all of these problems. A.) 1 Billion Rows Challenge B.) Are You Surrounded? Challenge C.) Best Seller With The Least Discount
@zweitekonto9654 that's the thing. b and c is hard to find or not even existing. But it is actually an ask question. Though technically there maybe similar problem, I can give you the gist of one of the problem. Idk if you can search it. Best Seller With The Least Discount The problem goes like this. Given a list of products for sales with its name, price, discounted, price, and sold numbers. Determine which product satisfies one or either both description. 1.) It have the least Discount but sells well. 2.) Have the highest sales return for the same discount. The problem is something like that.
There was a good talk on the 1brc in Elixir at Code BEAM Europe this year. The talk isn't available yet, but in summary, it got down to 2.5 seconds, and Elixir doesn't have loops. Ultimately, good recursion will compile to the same code as a loop would anyway 🤷♂️
I will complain that recursion leads to unknown max stack size. If you do something like a depth-first search iteratively you have more control both over the max depth and handling the case when it is reached.
Yep! But a lot of languages have properly implemented last call optimisations, too :) And most of the time, you're probably not going that deep on a recursive call.
As a follow up video it would be nice to see actual application of recursion over loops that justifies to use one over the other. The theoretical aspect is nice but real life examples are going to be more useful
Valid criticism! I don't like it either, but unfortunately I have very little time to edit these days so it's a bit necessary. Looking at ways to improve it though!
Nothing's perfect, but it's rare you'll actually hit upon it in most software. The times you'll be recursing deep enough to matter are generally the times when TCO is a good option (e.g. mapping over a list)
There are some times when you should use C, and other times when you should use a shell script or Python. This depends on several factors, too large to quantify, but we just go with the flow, or if we want perfection, we could use AI to select the optimal approach for us too.
I think there needs to be some sort of guideline (like SOLID in oop) for functional programming s.t. everyone can write equally readable code. take the repeat at 3:30 for example, it's more readable to define a base case as the initial state than tracking produced state in the params. like this: ``` fn repeat(val, count) { case count [] False -> [val, ..repeat(val, count - 1)] } } ```
The problem with your refactor is that it no longer is tail recursive, so it is less memory efficient and doesn't scale well. The produced state in the params is necessary for tail recursion, as it allows to move the operation in the parameters, which will be executed before calling the function.
@@VarpieUse monads/monad pattern? More obtusely, refactor your state into a parameter to be passed into an inner function, then wrap the inner function that does the logic into an outer function, where state can be hidden from the consumer of the function. Of course, there are nuances to such, but as is with general advice on the internet.
@@oserodal2702 Yes, the common pattern in the Gleam standard library is to have the public function without the "accumulator" parameter, and it calls do_function which has an extra parameter, using the default value from the base case. But the function that has the actual implementation does require this extra parameter for tail call optimization.
The good old times when people told you about recursion in university and you showed them how it is overflowing your memory and is slower in most cases :D
And then someone comes along and shows you that properly implemented recursion and loops compile to basically the same assembly. I remember those days too!
@ if it compiles to the same machine code (in most compilers) then why should you chose the syntax that is more complex to understand? Also in JS for example, it doesn’t compile to the same code and recursion has been the source of a lot of memory issues over the past decade.
It's only more difficult to understand for some problems. I'm not suggesting you should always use recursion, but for a lot of problems it does make sense
not having loops in any language is just stupid, you're letting yourself get carried away by the ideology instead of what's actually practical. BE CAREFUL WITH THE IDEOLOGY, do not let yourself be carried away by it
The first part of this statement is objectively incorrect, as often compilers will give you the same output for recursion or a loop. As for the second part, it depends on the problem.
While gleam has been a fun language to learn, something I have experienced is that it is not always a good idea to be forced to handle a problem in a different. For me personally, playing around and learning how to perform the different forms of recursion has been quite tedious and exhausting. I was attempting to implement an html parser in gleam and it was just a tremendous hassle when traversing strings and handling different cases (logical conditions is another pet-peeve of mine). Obviously it's just a skill issue on my part but the main issue for me is that it doesn't really feel like a skill worth delving deeper into when the solutions one has to come up with are due to arbitrary restrictions and over simplification. Overall I'd say that gleam is a pretty fun toy language, and while it is possible to build solid applications using it, The cost of doing things the overly-functional, gleam way restricts far too much and makes me not want to do anything particularly complex with it.
You're definitely allowed to have your opinion, but I wanna say a couple of things: Gleam isn't a "toy" language. It has all the features a lot of functional languages do, and it's used in production in a few places. Just because you can't see how you'd build a production system in it, doesn't mean it's not a "real" language. Secondly, the lack of loops generally isn't an arbitrary restriction. Like I mention in the video, a lot of functional programming languages don't have mutable state, and thus loops can't really exist. And Gleam is a fantastic language for writing parsers! Functional languages with type systems like Gleam are some of the best ways to build parsers, in fact. Why do you think lots of languages are written in OCaml?
@@IsaacHarrisHolt I know that the term "toy" brings with it negative connotations and so I apologize for my poor choice in wording. When I said toy I really just meant raw and overly simple. I understand that a lot of functional languages are designed to work with immutable data and thus can't function properly with the more common looping method. In my opinion it feels a little foolish to restrict to strictly immutable data handling instead of a more opt-in approach, as it allows for more capabilities as it pertains to memory management. For me, it's always felt as if FP languages only work well in areas where there is additional work being done in the background to support it as best as possible (An analogy I came up with off the top of my head just now is like a garbage-collector but on steroids). As for your statement regarding the popularity of building parsers using FP languages like ocaml, that's pretty fair. While I will acknowledge my ignorance on the subject, from a quick search, the beauty doesn't seem to come from the fact that it is a FP language in itself but due to two aspects that can exist out of the FP paradigm (pattern matching, and algebraic data types). All in all, seeing as my post was more insulting than it was useful. I'll restate my point: Pure FP languages introduces too many restrictions that disallows one to really build large projects without having to come up with new solutions to already-solved problems. It doesn't feel particularly worth it at the moment with gleam as it feels overly-simplified. This is my opinion after working with it for a little over 3 months so not quite a great deal of time I'll admit.
That's completely valid. If you haven't been having a good time with it, I'm not going to disregard your experience! It's definitely a mindset shift, but I've quite enjoyed immutable programming. There are some things you need to get used to, but the Erlang BEAM VM that Gleam runs on is incredibly powerful and only really works because a lot of things are immutable. Immutability immediately wipes out a whole class of bugs, especially around concurrent programming and shared memory. Gleam's type system on top of that removes a lot of type errors that you might see in Erlang or Elixir. It's not perfect, because you're still fundamentally compiling to an untyped system, but it's a lot better.
@@zerofirex12 FP languages aren't exactly new, ML was created in 1973 for instance, so most of the problems you see have already been solved in functional programming too. Gleam is quite recent, and the library ecosystem isn't always very mature, so I feel like it isn't very fair to say that functional programming languages as a whole aren't fit to build large projects just based on that. It's like Go: the language itself is pretty simple, but you can do anything you want with it! And maybe 10 years ago, the ecosystem in Go wasn't big enough to do it quickly, but now it is recognized as one of the best languages to create cloud native applications. If the community keeps building on Gleam, I could see it be a very solid language for web applications for instance (we already have Lustre which is great for that).
@@Varpie I don't doubt Gleam's ability to grow and adapt and eventually become an excellent language to use. My main problems are more fundamental to the idea of such a strictly functional language. In my opinion, having restrictions that are imposed, not due to limitations of a machine's capability, but due to the tendency of functional languages to only work with immutable data, leads to solutions being created to self-imposed problems. To be honest, there are quite a few things I enjoy that are frequently found in FP languages (higher-order functions, pattern matching, algebraic data types). However there is a solid reason that logical statements and loop constructs exist and I don't think being forced to consider how to work around their lack of existence in a language is a worthwhile trade-off.
the gifs genuinely make the video a pain to watch... I'd recommend finding some other background footage other than typing a word you said in the video into tenor and picking the first result
@IsaacHarrisHolt i understand not having enough time to make anything fancy, for my own video i recorded a cool background from shade toy, which works well for preventing the viewer from getting bored.
PS: no hate here just saying this idea sucks "if you're going to complain in the comments that recusion would make your zero user crud app slow, I want to see proof that every other part of your code is totally optimized, especially any I/O your app is doing, your database queries will be orders of magnitude slower than a bit of recursion in nearly all cases, basically if you want to moan bring receipts" what? So I can only complain about something being slower if my code is nearly perfect? something being slow isn't reason for you to make the whole thing slower like what is this backwards logic that says that all speed wins have to be lost just because some part of the code is slow and all that just in order end up with code that is harder to reason about (look at what you did at 2:53) even though I've done my whole FP experience with haskell you gotta be able to notice that this code is just worse to read even if you hid it behind some higher level functions like list.map or made it tail recursive you're just making it a mess that's super annoying to debug because you try to turn everything into an expresion and forbid mutation
That point was meant to be a little tongue-in-cheek, but I also stand behind it. It's the same argument people make when choosing programming languages. Realistically, a CRUD API written in Python will have roughly the same latency as one written in Rust, as most of your CPU cycles are spent waiting around for the database to get back to you anyway. It's the same concept here. Again, you're mostly doing no work, so the very little time you spend actually doing some work is going to negligibly impact overall performance, even if that time, say, doubled
Higher order functions are spooky to me. I'm certain that it creates a security black hole. It's like a backdoor to any function. I am a big fan of while loops, even though i typically write my while loops with classic for loop syntax like i=0 while i < x; i++ I did end up using recursion once. I had wrote a python function that took a list argument and sort of parsed the list for certain keywords. The reason for doing that was that the instructions were pure math and it needed to seperate and solve the deepest 'in parenthesis' formula before solving the next step. Recursion allowed each part to be seperated by overwriting the list and returning the result to the correct index of the next list up the call chain.
You actually won't see performance benefits in a lot of cases! Tail call optimisations mean that for loops and recursion will compile to almost exactly the same assembly instructions
@@IsaacHarrisHolt Yeah, proving that for loops are faster. For loops are just jump instructions .Recursion is recursion. Loops require a fixed amount of memory to remember the step at which we are, recursion requires increasing amounts memory for every single recursive call. Tail call optimization is your compiler face palming at your code and rewriting it as a jump, which is, you guessed it, a loop... Not to mention that for tail call optimization to take place you need to force yourself to write your code in a specific way on each language with an optimizing compiler that implements tail call optimization so as to facilitate meeting the required conditions for said optimization to be possible for the compiler to perform... in essense, you are moving from depending on architecture specific behaviour that all machines have to depending on compiler specific behaviour that the compiler you are using may have, but then some poor soul on the other end of the globe compiles the same code as you and now they keep blowing their stack memory because their compiler can't figure out that it can perform a tail call optimization, or maybe doesn't even have tail call optimization support... Not to mention that loops are more easily optimized since they already align with cache based architectures, so they facilitate cache locality based operations and can even make it trivial for a compiler to spot a vectorization optimization. Recursion has its places and deserves to be used, but only when it has to be used. Forcing all loops to be recursion only hurts readability, maintainability and performance, all in a very very negative way.
Neither am I, really. I want a good alternative, but I don't have huge amounts of time to put into creating animations etc. Working on improving things though!
Yeah dude, let's use swords and spears to eliminate mosquitoes and flies too! 😏😏 I mean, there are better ways for click-bait. This is getting old. Find yourself better ways to grow as a tech tuber.
Most of my videos are tutorials. Outside of that, I generally either make things I think would be beneficial for the community, or make things I think would be a bit of fun. This is the latter :)
I hate FP hype. Usually people who promote FP never actually used proper FP language. Those who prefer recursion over loops, never had to debug it. Plus when you start memoizing stuff, loops are way cleaner (faster, less memory intensive). Leave recursion to problems that can't be solved in another other way.
@@IsaacHarrisHolt OCaml or F# would be the bare minimum. Also, when you take immutability into account, the problem grows even bigger. I'm yet to find out someone who points these things out, and proceeds to explain why traverse, lenses and other crap is better than two lines of mutable code in a for loop.
This isn't always true. Some languages can perform tail call optimisation in a lot of cases, which replaces the latest stack frame instead of adding to it
@IsaacHarrisHolt yeah I can also start hardcoding values and not separating code into different files, or even delete an entire repo. Doesn't mean I should!
Most compilers are good enough to generate proper iteration from your poorly written recursive code, but even when they do, it's still iterative in the generated code. What you're advocating for is more layers of abstraction so that no one ever understands how things work. This contributes to the decline in human intelligence and eventually the downfall of humanity. You may not want to look hundreds of years into the future, but I'd prefer humanity to grow more intelligent. That doesn't mean that I think everyone should use assembly, because at some point you just have to get work done, but there is a happy middle ground to be had and we should strive to maintain that. All of that said, how in the furry fuck do you think that a local variable is a non-local state while a parameter to a function is local? You're still modifying state and the compiler is still generating a local variable, even if it's a register that gets used. Most loops are better written as iteration, not just because it's easier for a human to understand, but because you use fewer lines of code to describe how the problem should be solved, which means less opportunities for bugs. Hopefully that's not a difficult concept to understand, but then you are advocating for functional programming. And it's called tail call optimization. If you can implement an algorithm with TCO, then you can implement it as a simple iteration and make it easier to understand and therefore less prone to bugs.
@@IsaacHarrisHolt Last call optimization is a code generation optimization technique where when the last thing your function does is call another function the result from that function isn't stashed to only be immediately used as your functions return value and instead the compiler just generates an immediate return. It's so ubiquitous of a technique that most compilers don't require you to turn on optimization to get that behavior and has nothing to do with recursion. Tail call optimization is when a recursive loop, either calling the current function at the end of itself or the last link in a chain of functions depending on how deep the optimizer looks and how convoluted the algorithmic implementation, gets converted into an iterative loop and eliminates the calling of a function entirely. TL;DR: For the attention span deprived, if you're using TCO, there will be NO LAST CALL to optimize. But thanks, I was worried that I may have been too harsh in my first comment and I feel relieved that I wasn't harsh enough.
I'm sorry to push this point, but last call optimisation is a set of optimisation techniques that INCLUDES tail call optimisation. Other techniques such as trampolining and deferred last call execution.
@@IsaacHarrisHolt Neither deferral nor trampolining have anything to do with optimization. Deferral is basically a coping technique for languages which lack RAII whereby the deconstruction of an object is deferred until the end of the current scope. Trampolining is a way of mostly invisibly linking functions to add to their capabilities by performing work before and/or after calling a "base" function. I can't help but feel like you're either testing me or you were hoping for explanations so that you could understand the concepts yourself.
@@IsaacHarrisHolt Yes very thankful, I whole heartedly believe recursion is the best thing in all the situations :D After I tried recursion my wife unleft me, and my kids started loving me again
I think that evryone forgot that lops are much faster then recursion because you mutate state. In pure functional programin this is not allowed and you habe to realloc
This is true - allocation slows things down. However, most of the time when you're doing loop operations, you're not actually modifying the underlying list - you're often creating a new one anyway
some languages can detect when your immutable manipulations of data are safe and convert them into mutations under the hood. Most of the time the cost is not something you will feel for immutability tho, unless you are doing it thousands of times per second.
For the most modern programming languages today, this is a bad advice. Loops are generally more performant and safer than recursion ... infinite loops? StackOverflowExceptions? compiler optimization? etc ... but I understand the functional point of view of it that might be related to only pure functional programming languages
You can have infinite loops with regular loops too, and if you've got tail call optimisation, you won't hit stack overflow errors as each subsequent call replaces the latest stack frame, rather than adding a new one. Also, compilers generally optimise loops and recursive calls down to the same tight loop in assembly. Sometimes the recursive assembly is actually shorter and more efficient!
depends on the language, some languages handle this stuff completely fine (Ocaml, lua, lisp, basically any language with tail call optimisation) and others simply dont and you probably shouldn't use recursion at all unless you really really need to.
@@IsaacHarrisHolt Yeah I was thinking more about Languages like Python, C#, Vb, Java and maybe JavaScript... Which are a little bit more popular .. for example, Dotnet even have code analyzer to detect recurrsion code and suggests refactoring it to loops to improve the performance.
I don't like the way these videos are edited, too many random animations that take away the focus from what is being explained. And I don't even have ADHD, so imagine what it is for those who do.
It's something I've been working on, and I'm not totally happy with it either. Unfortunately time pressure often means I can do much else, much as I'd like to 😅
The separating line for me personally to decide between using loops and recursion is whether I'm looping over an unknown-sized structure or a known-sized structured. Say looping over an array, that is a loop. Walking a deeply nested tree, that will be recursion. Forcing the use of one another blindly is like trying to force a wrench into hammering a nail, the nail does get in, but neither was the wrench designed to smash nor is it comfortable to be used for smashing.
I think that's a reasonable heuristic. I do find looping easier when it comes to arrays, for sure, but I find HOFs even easier than that, especially when you get nice pipe operators. It's much a matter of personal preference - this video is meant to be a bit tongue-in-cheek 😉
I don't know exactly what it is for me, but I know there are sometimes I'm trying to work something out and even though I know all recursive solutions can be "unrolled" into a procedural loop, I simply cannot easily think of the loop version.
@@JayLooney For me, that depends on whether the loop is "bounded" or "boundless".
"Bounded" as to say you know the size of the structure you need to loop over, e.g., enumerate all values in a 500 elements array, and these will always be a simple procedural loop.
"Boundless" as to say you do not know the size beforehand, or the size is depending on the individual elements itself, like a tree structure, you will never know how many levels down there until you actually walked it. For these problems, that will always be recursion for me.
No matter who the government sends, I am not replacing my loops with recursion!
Totally valid! I never said you HAD to, just that you COULD 😉
@@IsaacHarrisHolt and should NOT
it’s all recursion if you go low enough
@@danser_theplayer01 incorrect
Mee too
Recursion is always the ans...
Stack overflow.
Tail call optimisation 😉
@@IsaacHarrisHolt
Yes the compiler will just convert it into a for loop for you...or not. Who knows
Generally the compiler knows best
@@chudchadanstud
Some languages enforce it, so it will
@@IsaacHarrisHolt Except that not every compiler supports TCO, so you cannot blindly trust the compiler to Do The Right Thing(tm) in case there's a tail call.
tail recursion just feels like loops with worse syntax to me, except maybe in haskell where you have pattern matched function definitions.
I do like recursion for tree problems tho since you're actually using the stack frames as intended (with an iterative approach literally requiring you to explicitly define a stack to keep track of state)
Oh for sure, there are some problems that loops are probably better suited for. I never said you HAD to replace all your loops with recursion, I was just making the point that you COULD 😉
I really liked one bit in the video that was obvious, once Isaac said it, but it genuinely didn't occur to me:
"break" is just returning early and "continue" is just calling the function again early.
I mean, yeah, so simple - thanks, Isaac, that actually really helped!
Glad it was useful! You seem to have got the point of the video better than most 😅
@IsaacHarrisHolt Yeah, I was surprised how controversial it was. Louis Pilfold is seemingly a popular streamer relative to coding, so I thought this would go over really well.
But maybe as some solace: I'm very new to both low-level and functional programming and the disagreeing comments were useful as they pointed out limits I wouldn't have been aware of and can now anticipate. So, at least it was a kinda spirited discussion?
Anyway, thanks again and keep up the great work - the Lustre content is another banger. :)
Thank you!
I write primarily number crunching code - mostly signal processing and numerical math, sometimes a bit of graphics and image processing. I really don't think that I want to implement a Gaussian blur filter recursively without any loop over the pixels, for example. How would that code even look like?
That's fair! For some stuff, loops are definitely better, and I never tried to say you should always use recursion
The thing is that I would much rather use an imperative instruction when convenient rather than shooting myself in the foot performance and readability wise for the sake of "purity" (I don't think recursion is inherently purer than a loop). Jump exists so you may as well use it without returning shenanigans.
You're unlikely to encounter a performance hit if you're doing tail recursion (which, if you're replacing a for loop, you probably should be), and it's no less readable.
Recursion can be a lot more "pure" - loops have to modify state, and can therefore be misused to modify state external to your scope. While you can, of course, modify state in a recursive function (if your lang allows it), you don't have to, and often shouldn't if you want the best performance.
@@IsaacHarrisHolt recursion can be much less readable in a lot of languages
In my experience with the real world, recursion will lead to far more crashes than any other construct you will ever use. The fact that you're using stack memory instead of jumps in a program's flow is too big of a downside to ignore.
Tail call optimised recursive functions don't use any more memory than for loops, and are often just as performant
@@IsaacHarrisHoltyeah tail call optimizations have been implemented in compilers for years
@@IsaacHarrisHolt Well, tail call recursion is a special case. Not all loops can be implemented like this. For example, search and sort algorithms will rarely fit that mold.
Also, not all languages support this optimization. Java, Python and Go are three examples. Those always (or in some cases selectively) use the stack, even if the function is tail recursive.
recursions ? did he just finished a online course ? it is far to soon to make video about programming my little padowan ! do some real programming, not redos !
That's not how functional languages work though
I'd like to see some practical real world cases where to support your claim that the compiler can "usually compile recursive code just as well as iterative code". I work on high performant code at my job and usually the "should I implement this function recursively or iteratively" debate goes like this:
1. I want to express my idea into code
2. I choose to implement it recursively, since I feel it is easier
3. I profile the code and regret my decision
4. I unroll the recursion into a loop
5. Win (big time)
I like to think of my code in a data oriented way. Since all computer engineering is, is taking data as input, transforming the data, and spitting out the tranformed data as output. The number 1 most important thing to do this efficiently is to first of all, know your hardware, and second of all, lay out your data in a way that you know the hardware will be able to execute it efficiently.
The reality is that most of our modern hardware has become pretty good at performing repetitive tasks on contiguous blocks of data. So naturally, I try to lay out the data in such a way. Loops (especially over sequential data) are very easy for the compiler to understand. So I trust the compiler to do a relatively decent job compiling my code to SIMD instructions and to perform other optimisations. Recursion on the other hand is complex, since the logic is divided in the multiple recursive calls. But all the compiler sees is just a regular function that happens to call itself. On top of that, you're often times breaking up the single data structure that you could have in a loop into multiple singular "recursion states". Good luck to the compiler figuring out how to stitch everything together efficiently.
Aside from my concerns as someone who is tasks writing fast real world code, I think recursion has a beauty. It is simple. It is expressive. It is powerful. I prefer it over recursion if I'm just zen, drinking my tea, listening my chill music playlist, while implementing my function.
When my piece of code is just something small off the hot path, I use it. And I'm happy with how it looks. But in hot paths, when the stakes are high, I avoid it as much as possible. I just don't trust the compiler enough to make anything good out of it. And whenever I feel like "recursion just makes more sense" or "a regular loop is going to be messy", I reflect on it and probably conclude that the data layout is not good enough. I have to rethink the models.
I think your video was nice. Informative, and provides a little peek into the magical world of functional programming. Just think the statement that recursion usually doesn't kill performance is false.
Keep up the good vids :)
I think tail recursions are as performant as loops. Atleast theoretically, never tried profiling them though.
@@zweitekonto9654they are if the compiler optimizes it but that might not always happen
The optimisations will be very language dependent, but often tail-optimised recursive calls will be compiled to the same or similar assembly to a loop. There's a good Twitter post showing the difference SOMEWHERE, and iirc the recursive example actually produced fewer instructions.
You can get SIMD optimisations out of recursion, but yes, for highly performance critical stuff, loops are probably your friend (and I said as much in the video!).
you really nailed the beauty of recursion, it's kind of rare to find situations where it's more applicable than alternatives, but it's such a pleasure to write a recursive function, like a functional fractal
Clojure has wonderful loop/recur construct, which is really beautiful in my opinion because it looks like a loop but behaves functionally without need of tail call elimination.
What do you mean it doesn't need tail call elimination? I've not used Clojure at all, so I'm curious what this would look like
You never justified why recursion should be used at all. Yes, recursive functions can be limited to only modify local state if that is how you write them. But why? Why is that better? It is just a different way of thinking about a problem, but programming is in the end neither about mathematical functions and proofs, nor about state or objects, or about memory management. Programming is about transforming data and what should be the focus is how data is transformed the most efficiently, which depending on your circumstances may include the time it takes to for new people to read and understand your code.
This video wasn't really meant to be a "omg you should always just recurse" - it was mostly a bit of fun saying you CAN just recurse.
Like I said in the video, recursion is best for traversal problems because it allows you to only focus on the one item at a time very simply.
@@IsaacHarrisHolt Recursion is best for problems where it is easy to divide the problem into different easily defined and solvable states but where it is difficult to hold or even imagine the big picture and/or the many different paths it can take in your head. Traversal problems can be one example.
Yes, exactly.
Great video as always. I don't write that much functional code, but I really like the thought patterns!
Thank you! Yeah, FP is really interesting, and there's a lot you can take into non-FP languages
@@IsaacHarrisHolt This! exactly. Due to my job and the languages of my hobbies im in the same boat. BUTTTT theres really good ideas you can always take across.
Absolutely! Immutability is a big one if the language you're using makes it easy to do
Question: is organizing your loop as a recursive function "really" eliminating state? I hear that functional programming is meant to make things easier to reason about, but I don't believe making your variable an explicit part of the function necessarily changes the fact that not-always-trivial transformations may have to be done to it every iteration, and you're effectively still mutating it every time the function recurses, just not literally.
>Question: is organizing your loop as a recursive function "really" eliminating state?
Nope, it just hides it. But what functional programmers state is that they eliminate external state because all states are internal. But that is only true if you write your functions that way, and you can do the same with a loop through:
{
//declare all data you need in the loop
for(...
//return answer here
}
And in reality it doesn't matter because data is state, state is data, your functions will only ever be called when your program reaches a certain state so your functions are always relying on external state meaning that you can't reason about your program any easier. It is more or less an ideological thing rather than a practical thing.
Fair points!
I find it curious how the Fibonacci sequence is often one of the prime examples of how to do recursion, but at the same time the loop version is soo much better. It cannot be tail recursed normally, and it's not a particularly common pattern, so you can't necessarily rely on your compiler to have a specific optimization for it. If it's not optimized you end up calculating numbers exponentially more. In the meanwhile the loop is just simple with two state variables and can calculate any number up to system limits.
I agree with what you're saying. I think it's mostly because the sequence is inherently recursive (you could think of it a bit like a tree), and it's also something that most people understand, so you're not having to teach a new concept like graphs or trees on top of recursion
I believe that Fibonacci sequence being used as an example in schools and other training material is one of the reason why recursion is harder than it has to be for many. You present a nail in a board, but instead of reaching for a hammer you tell people to use a wrench to punch it in. It is better to start with problems where recursive thinking is not only better but where the actual usefulness of recursion shines. I.e. present a nut and bolt, not a problem where everyone will think "geez, I wish I had a hammer".
A fun fact BTW is that the loop solution to Fibonacci sequence is the optimal, bottom up DP solution. Just because DP builds on recursion relationships doesn't mean that the solution must use recursion, because just the same as the compiler can turn a recursive solution to a loop so can you, and in the case of Fibonacci if you optimize the recursive solution you get the simple loop.
Fib is literally the absolutely worst problem to use when teaching about recursion because all it teaches is that recursion is stupid. Which it isn't.
Wdym by "it cannot be tail recursed normally" ?
(define (fib n)
(define (fib-aux n a b)
(if (= n 0)
a
(fib-aux (- n 1) b (+ a b))))
(fib-aux n 0 1))
Is this not tail recursive ?
@@mrna4846 in the way it is normally taught it calls itself twice, which cannot be tail recursed.
dont both end up as jump instructions when compiled?
They pretty much do, yeah, assuming you have tail call optimisation
some people tend to forget that a lot of features present in some programming languages do not come for free , like inheritance , virtual functions and recursion,
whilst it depends on the use case iterative implementations sometimes far outperform recursion for the simple reason that recursion has overhead whether it is in interpreted or compiled languages .
In a lot of compiled languages, recursive function calls get compiled down to the same tight loop in assembly as a for loop does!
@@IsaacHarrisHolt Which makes it even less appealing to use recursion, as iterative loops are simpler to read, understand and maintain and they don't cause memory overflows.
@@IsaacHarrisHolt if they get compiled to the same thing then why would you go through the trouble of writing recursion over a simple for loop
It depends on the problem you're solving. Sometimes loops are more difficult to read (e.g. when doing tree traversal)
@ especially for tree traversal, I wouldn’t go with a recursion algo! Most JS/TS libraries use recursion and they all run out of memory at a certain tree size.
In compiled languages, it’s less of a problem of course, but JS is the most used one, although for tasks like this Go or Gleam would be much better.
Loops are more efficient for e.g factorials because they use less memory (no stack frames) and avoid the overhead of recursive calls. Recursion is elegant but can cause stack overflow for large inputs
Not if you've got tail call optimisation! For example, here's a tail-call optimised factorial function: playground.gleam.run/#N4IgbgpgTgzglgewHYgFwEYA0IDGyAuES+aIcAtgA4JT4AEA5gDYQCG5A9IgDpK+UBXAEZ0AZkjrlWcJAAoAlHWC86dRADoAJhCECGs0axz4acVk1kBWefN4BfXr3FijJqGYtJFyiXU0IAfUNjU3NZJEw6dFskBz4kZ38g11DPSKMcbxU6HFYYCDoJH1VVdDoAWgA+Ogzs1Qkqv0Dgtw9wiqjIiQAqGpxM7Li7EDsgA=
If you look at the compiled JavaScript, you'll see that it's essentially a tight loop :)
Heck yeah, recursion forever!
Recursion recursion recursion recursion recursion rec-
Okay my hands are tired
Heck yeah, recursion forever!
@@vikingthedude Heck yeah, recursion forever!
@@giacomo_cavalieri @vikingthedude Heck yeah, recursion forever!
@@mrkhlms Maximum recursion depth reached.
I avoid recursion as much as possible, since it creates a new stack frame every time it calls itself, which can lead to a stack overflow if you're doing it wrong. Especially true in embeded softwares and really long recursions. Just be carefull with it..
Tail call optimisation will prevent new stack frames being added, instead replacing the previous stack frame
In my career I’ve used recursion ONCE, and it was only because the limitations of the platform I was using (Salesforce) made a for loop impossible.
Though I suppose I also once defined a recursive database formula. That was pretty neat.
Recursive queries in Postgres are cool! They let you turn a relational DB into a graph DB 😁😁
I agree with the loopy not mattering that much stuff, but beyond raw speed you have things like GC cycles happening more frequently in some runtimes. anyway, I think its foolish to focus on such stuff when you are trying your ideas out. Code must first work, then be pretty, then be optimized for a context.
Oh yeah, make it work then make it good, for sure
well, loop simplier to maintain and harder to fk up, so to make a recursion - you need a real reson)
Depends on the problem you're solving!
I wonder how recursion will tackle any or all of these problems.
A.) 1 Billion Rows Challenge B.) Are You Surrounded? Challenge
C.) Best Seller With The Least Discount
Can you link to B) and C) problems? A quick google search didn't result in anything.
@zweitekonto9654 that's the thing. b and c is hard to find or not even existing.
But it is actually an ask question.
Though technically there maybe similar problem,
I can give you the gist of one of the problem. Idk if you can search it.
Best Seller With The Least Discount
The problem goes like this.
Given a list of products for sales with its name, price, discounted, price, and sold numbers.
Determine which product satisfies one or either both description.
1.) It have the least Discount but sells well.
2.) Have the highest sales return for the same discount.
The problem is something like that.
There was a good talk on the 1brc in Elixir at Code BEAM Europe this year. The talk isn't available yet, but in summary, it got down to 2.5 seconds, and Elixir doesn't have loops.
Ultimately, good recursion will compile to the same code as a loop would anyway 🤷♂️
To be real: TCO rewrites a recursion into a loop and that is why one can use it for real world applications.
100%! It's very cool
Depends on how you define repeating code. You only used 1 type of it, functions being another.
I would define repeating code as code that's called multiple times. Whether in a loop, recursion, or just from copying and pasting
I will complain that recursion leads to unknown max stack size.
If you do something like a depth-first search iteratively you have more control both over the max depth and handling the case when it is reached.
If you use tail call recursion, and your language supports it, your stack size won't increase.
What's a monad?
Google it 😉
It's a monoid in the category of endofunctors.
A good chunk of languages will crash because the stack will run out of memory.
Yep! But a lot of languages have properly implemented last call optimisations, too :)
And most of the time, you're probably not going that deep on a recursive call.
As a follow up video it would be nice to see actual application of recursion over loops that justifies to use one over the other. The theoretical aspect is nice but real life examples are going to be more useful
There'll be a lot more of this in the recursion tutorial for sure!
why did you make the code so small 😭
I'll make it bigger next time :)
can't wait for the complete functional video
Do you mean the one on recursion?
@@IsaacHarrisHolt yeah
Love the video, but I find the constant changing GIFs a bit too distracting
Valid criticism! I don't like it either, but unfortunately I have very little time to edit these days so it's a bit necessary. Looking at ways to improve it though!
Doctors fear apples and functional bros fear stack overflows.
Tail recursion optimization prevents that in many cases. Most functional languages implement it.
@linuxsbc It isn't perfect though...
Nothing's perfect, but it's rare you'll actually hit upon it in most software. The times you'll be recursing deep enough to matter are generally the times when TCO is a good option (e.g. mapping over a list)
There are some times when you should use C, and other times when you should use a shell script or Python. This depends on several factors, too large to quantify, but we just go with the flow, or if we want perfection, we could use AI to select the optimal approach for us too.
@jyothishkumar3098 I sorta agree. I use recursion for parsers.
I think there needs to be some sort of guideline (like SOLID in oop) for functional programming s.t. everyone can write equally readable code.
take the repeat at 3:30 for example, it's more readable to define a base case as the initial state than tracking produced state in the params.
like this:
```
fn repeat(val, count) {
case count []
False -> [val, ..repeat(val, count - 1)]
}
}
```
Totally fair! This is a nice refactoring, thanks :)
The problem with your refactor is that it no longer is tail recursive, so it is less memory efficient and doesn't scale well. The produced state in the params is necessary for tail recursion, as it allows to move the operation in the parameters, which will be executed before calling the function.
This is true ^^
@@VarpieUse monads/monad pattern?
More obtusely, refactor your state into a parameter to be passed into an inner function, then wrap the inner function that does the logic into an outer function, where state can be hidden from the consumer of the function.
Of course, there are nuances to such, but as is with general advice on the internet.
@@oserodal2702 Yes, the common pattern in the Gleam standard library is to have the public function without the "accumulator" parameter, and it calls do_function which has an extra parameter, using the default value from the base case. But the function that has the actual implementation does require this extra parameter for tail call optimization.
The good old times when people told you about recursion in university and you showed them how it is overflowing your memory and is slower in most cases :D
And then someone comes along and shows you that properly implemented recursion and loops compile to basically the same assembly. I remember those days too!
@ if it compiles to the same machine code (in most compilers) then why should you chose the syntax that is more complex to understand?
Also in JS for example, it doesn’t compile to the same code and recursion has been the source of a lot of memory issues over the past decade.
It's only more difficult to understand for some problems. I'm not suggesting you should always use recursion, but for a lot of problems it does make sense
not having loops in any language is just stupid, you're letting yourself get carried away by the ideology instead of what's actually practical. BE CAREFUL WITH THE IDEOLOGY, do not let yourself be carried away by it
You're not justifying any point you're making here
Recursion is always slower than loops, and in most cases it makes the code less readable
The first part of this statement is objectively incorrect, as often compilers will give you the same output for recursion or a loop.
As for the second part, it depends on the problem.
That's not even slightly true!
@@lpil recursions is a nightmare for prefetchers, this is something that is not really related to high level languages
@@elektro860 Recursion compiles to exactly the same machine code or byte code for any half decent compiler. There's no difference.
@@lpil relying on a compiler to always fix your bad habits is not worth it for me
Yoo this is such a good idea I can't wait to u- stack overflow
Tail call optimisation!
@IsaacHarrisHolt Can only get you so far
Fair enough!
Oh my god I feel so bad for anyone who uses your libraries
You realise Gleam doesn't have loops right? So, uh, recursion is the only option
@@IsaacHarrisHolt Oh my god I feel so bad for anyone who uses your niche programming language
While gleam has been a fun language to learn, something I have experienced is that it is not always a good idea to be forced to handle a problem in a different. For me personally, playing around and learning how to perform the different forms of recursion has been quite tedious and exhausting. I was attempting to implement an html parser in gleam and it was just a tremendous hassle when traversing strings and handling different cases (logical conditions is another pet-peeve of mine). Obviously it's just a skill issue on my part but the main issue for me is that it doesn't really feel like a skill worth delving deeper into when the solutions one has to come up with are due to arbitrary restrictions and over simplification.
Overall I'd say that gleam is a pretty fun toy language, and while it is possible to build solid applications using it, The cost of doing things the overly-functional, gleam way restricts far too much and makes me not want to do anything particularly complex with it.
You're definitely allowed to have your opinion, but I wanna say a couple of things:
Gleam isn't a "toy" language. It has all the features a lot of functional languages do, and it's used in production in a few places. Just because you can't see how you'd build a production system in it, doesn't mean it's not a "real" language.
Secondly, the lack of loops generally isn't an arbitrary restriction. Like I mention in the video, a lot of functional programming languages don't have mutable state, and thus loops can't really exist.
And Gleam is a fantastic language for writing parsers! Functional languages with type systems like Gleam are some of the best ways to build parsers, in fact. Why do you think lots of languages are written in OCaml?
@@IsaacHarrisHolt I know that the term "toy" brings with it negative connotations and so I apologize for my poor choice in wording. When I said toy I really just meant raw and overly simple. I understand that a lot of functional languages are designed to work with immutable data and thus can't function properly with the more common looping method. In my opinion it feels a little foolish to restrict to strictly immutable data handling instead of a more opt-in approach, as it allows for more capabilities as it pertains to memory management.
For me, it's always felt as if FP languages only work well in areas where there is additional work being done in the background to support it as best as possible (An analogy I came up with off the top of my head just now is like a garbage-collector but on steroids). As for your statement regarding the popularity of building parsers using FP languages like ocaml, that's pretty fair. While I will acknowledge my ignorance on the subject, from a quick search, the beauty doesn't seem to come from the fact that it is a FP language in itself but due to two aspects that can exist out of the FP paradigm (pattern matching, and algebraic data types).
All in all, seeing as my post was more insulting than it was useful. I'll restate my point: Pure FP languages introduces too many restrictions that disallows one to really build large projects without having to come up with new solutions to already-solved problems. It doesn't feel particularly worth it at the moment with gleam as it feels overly-simplified. This is my opinion after working with it for a little over 3 months so not quite a great deal of time I'll admit.
That's completely valid. If you haven't been having a good time with it, I'm not going to disregard your experience!
It's definitely a mindset shift, but I've quite enjoyed immutable programming. There are some things you need to get used to, but the Erlang BEAM VM that Gleam runs on is incredibly powerful and only really works because a lot of things are immutable.
Immutability immediately wipes out a whole class of bugs, especially around concurrent programming and shared memory. Gleam's type system on top of that removes a lot of type errors that you might see in Erlang or Elixir. It's not perfect, because you're still fundamentally compiling to an untyped system, but it's a lot better.
@@zerofirex12 FP languages aren't exactly new, ML was created in 1973 for instance, so most of the problems you see have already been solved in functional programming too. Gleam is quite recent, and the library ecosystem isn't always very mature, so I feel like it isn't very fair to say that functional programming languages as a whole aren't fit to build large projects just based on that.
It's like Go: the language itself is pretty simple, but you can do anything you want with it! And maybe 10 years ago, the ecosystem in Go wasn't big enough to do it quickly, but now it is recognized as one of the best languages to create cloud native applications. If the community keeps building on Gleam, I could see it be a very solid language for web applications for instance (we already have Lustre which is great for that).
@@Varpie I don't doubt Gleam's ability to grow and adapt and eventually become an excellent language to use. My main problems are more fundamental to the idea of such a strictly functional language. In my opinion, having restrictions that are imposed, not due to limitations of a machine's capability, but due to the tendency of functional languages to only work with immutable data, leads to solutions being created to self-imposed problems.
To be honest, there are quite a few things I enjoy that are frequently found in FP languages (higher-order functions, pattern matching, algebraic data types). However there is a solid reason that logical statements and loop constructs exist and I don't think being forced to consider how to work around their lack of existence in a language is a worthwhile trade-off.
the gifs genuinely make the video a pain to watch... I'd recommend finding some other background footage other than typing a word you said in the video into tenor and picking the first result
Appreciate the feedback! I'm working on it, but these things take more time than I have at the moment 😅
@IsaacHarrisHolt i understand not having enough time to make anything fancy, for my own video i recorded a cool background from shade toy, which works well for preventing the viewer from getting bored.
I'll look into it, thanks!
I definitely need loops.
Hahaha fair enough! Not everyone likes recursion
@3:22 This animation can scary off anyone from recursion ;)
It's pretty terrifying 😭
This vid is getting a weird amount of pushback.
Map over Arrays, Recur over everything else like functional god intended
Pretty much! All these JS devs using Array.map and not realising that they'd be using the same API in a functional language...
As an embedded bro this video makes me say and angry at the same time...stack overflow
Tail call optimisation means you won't get stack overflows :)
PS: no hate here just saying this idea sucks
"if you're going to complain in the comments that recusion would make your zero user crud app slow, I want to see proof that every other part of your code is totally optimized, especially any I/O your app is doing, your database queries will be orders of magnitude slower than a bit of recursion in nearly all cases, basically if you want to moan bring receipts"
what? So I can only complain about something being slower if my code is nearly perfect?
something being slow isn't reason for you to make the whole thing slower like what is this backwards logic that says that all speed wins have to be lost just because some part of the code is slow
and all that just in order end up with code that is harder to reason about (look at what you did at 2:53)
even though I've done my whole FP experience with haskell you gotta be able to notice that this code is just worse to read
even if you hid it behind some higher level functions like list.map or made it tail recursive you're just making it a mess that's super annoying to debug because you try to turn everything into an expresion and forbid mutation
That point was meant to be a little tongue-in-cheek, but I also stand behind it. It's the same argument people make when choosing programming languages. Realistically, a CRUD API written in Python will have roughly the same latency as one written in Rust, as most of your CPU cycles are spent waiting around for the database to get back to you anyway.
It's the same concept here. Again, you're mostly doing no work, so the very little time you spend actually doing some work is going to negligibly impact overall performance, even if that time, say, doubled
Higher order functions are spooky to me. I'm certain that it creates a security black hole. It's like a backdoor to any function.
I am a big fan of while loops, even though i typically write my while loops with classic for loop syntax like i=0 while i < x; i++
I did end up using recursion once. I had wrote a python function that took a list argument and sort of parsed the list for certain keywords. The reason for doing that was that the instructions were pure math and it needed to seperate and solve the deepest 'in parenthesis' formula before solving the next step. Recursion allowed each part to be seperated by overwriting the list and returning the result to the correct index of the next list up the call chain.
Recursion is a great tool for a lot of problems! Sometimes though, it's definitely easier to stick to a for loop :)
@IsaacHarrisHolt what is recursion really other than a 'hold my instruction set while I get the next one' function.
Durrr this is the math thing we learned recurive and expkicit functions
You don't have to think about maths at all when doing recursion!
Or you could just use for and enjoy the performance benefits.
You actually won't see performance benefits in a lot of cases! Tail call optimisations mean that for loops and recursion will compile to almost exactly the same assembly instructions
@@IsaacHarrisHolt Yeah, proving that for loops are faster. For loops are just jump instructions .Recursion is recursion. Loops require a fixed amount of memory to remember the step at which we are, recursion requires increasing amounts memory for every single recursive call. Tail call optimization is your compiler face palming at your code and rewriting it as a jump, which is, you guessed it, a loop... Not to mention that for tail call optimization to take place you need to force yourself to write your code in a specific way on each language with an optimizing compiler that implements tail call optimization so as to facilitate meeting the required conditions for said optimization to be possible for the compiler to perform... in essense, you are moving from depending on architecture specific behaviour that all machines have to depending on compiler specific behaviour that the compiler you are using may have, but then some poor soul on the other end of the globe compiles the same code as you and now they keep blowing their stack memory because their compiler can't figure out that it can perform a tail call optimization, or maybe doesn't even have tail call optimization support...
Not to mention that loops are more easily optimized since they already align with cache based architectures, so they facilitate cache locality based operations and can even make it trivial for a compiler to spot a vectorization optimization.
Recursion has its places and deserves to be used, but only when it has to be used. Forcing all loops to be recursion only hurts readability, maintainability and performance, all in a very very negative way.
What's a for loop? What's while loop? What a function? I program x86 😎
🦘
I'm not a fan of the "stock animations" or whatever it's called. It's often repetitive and annoying (to me).
But I like your content a lot.
Neither am I, really. I want a good alternative, but I don't have huge amounts of time to put into creating animations etc. Working on improving things though!
Viva la résistance!
It's functioning time 😎
Lets go! Recursion to go :)
Recursion all the way!
Yeah dude, let's use swords and spears to eliminate mosquitoes and flies too! 😏😏
I mean, there are better ways for click-bait. This is getting old. Find yourself better ways to grow as a tech tuber.
Most of my videos are tutorials. Outside of that, I generally either make things I think would be beneficial for the community, or make things I think would be a bit of fun. This is the latter :)
I hate FP hype. Usually people who promote FP never actually used proper FP language. Those who prefer recursion over loops, never had to debug it. Plus when you start memoizing stuff, loops are way cleaner (faster, less memory intensive). Leave recursion to problems that can't be solved in another other way.
I mean, FP languages don't often have loops. What would you consider a "proper" FP language, and which ones aren't "proper"?
@@IsaacHarrisHolt OCaml or F# would be the bare minimum. Also, when you take immutability into account, the problem grows even bigger. I'm yet to find out someone who points these things out, and proceeds to explain why traverse, lenses and other crap is better than two lines of mutable code in a for loop.
Right, but what do OCaml and F# have that "improper" functional languages don't?
@@IsaacHarrisHolt Compiler that allows you to treat everything as a data type and compose it as such comes to mind.
I love gleam
here is my attention :)
Gleam is great!
Each recursive call adds a layer to the call stack, which can lead to high memory usage and risk of stack overflow for deep recursions.
This isn't always true. Some languages can perform tail call optimisation in a lot of cases, which replaces the latest stack frame instead of adding to it
Do not remove loops for recursion. My dude, you usually put out great vids, this wasn't one...
I never suggested that you SHOULD replace them in all cases! Just that you can 😉
@IsaacHarrisHolt yeah I can also start hardcoding values and not separating code into different files, or even delete an entire repo. Doesn't mean I should!
Most compilers are good enough to generate proper iteration from your poorly written recursive code, but even when they do, it's still iterative in the generated code. What you're advocating for is more layers of abstraction so that no one ever understands how things work. This contributes to the decline in human intelligence and eventually the downfall of humanity. You may not want to look hundreds of years into the future, but I'd prefer humanity to grow more intelligent. That doesn't mean that I think everyone should use assembly, because at some point you just have to get work done, but there is a happy middle ground to be had and we should strive to maintain that.
All of that said, how in the furry fuck do you think that a local variable is a non-local state while a parameter to a function is local? You're still modifying state and the compiler is still generating a local variable, even if it's a register that gets used. Most loops are better written as iteration, not just because it's easier for a human to understand, but because you use fewer lines of code to describe how the problem should be solved, which means less opportunities for bugs. Hopefully that's not a difficult concept to understand, but then you are advocating for functional programming. And it's called tail call optimization. If you can implement an algorithm with TCO, then you can implement it as a simple iteration and make it easier to understand and therefore less prone to bugs.
I'm gonna ignore a lot of the angry ranting here to correct you: tail call optimisation is a type of last call optimisation. You can use either term.
@@IsaacHarrisHolt Last call optimization is a code generation optimization technique where when the last thing your function does is call another function the result from that function isn't stashed to only be immediately used as your functions return value and instead the compiler just generates an immediate return. It's so ubiquitous of a technique that most compilers don't require you to turn on optimization to get that behavior and has nothing to do with recursion.
Tail call optimization is when a recursive loop, either calling the current function at the end of itself or the last link in a chain of functions depending on how deep the optimizer looks and how convoluted the algorithmic implementation, gets converted into an iterative loop and eliminates the calling of a function entirely.
TL;DR: For the attention span deprived, if you're using TCO, there will be NO LAST CALL to optimize.
But thanks, I was worried that I may have been too harsh in my first comment and I feel relieved that I wasn't harsh enough.
I'm sorry to push this point, but last call optimisation is a set of optimisation techniques that INCLUDES tail call optimisation. Other techniques such as trampolining and deferred last call execution.
@@IsaacHarrisHolt Neither deferral nor trampolining have anything to do with optimization.
Deferral is basically a coping technique for languages which lack RAII whereby the deconstruction of an object is deferred until the end of the current scope.
Trampolining is a way of mostly invisibly linking functions to add to their capabilities by performing work before and/or after calling a "base" function.
I can't help but feel like you're either testing me or you were hoping for explanations so that you could understand the concepts yourself.
Call stack goes brrrrrrrrrrrrr
Tail call optimisations :)
oh god
I get it, you're just so thankful that recursion exists
@@IsaacHarrisHolt Yes very thankful, I whole heartedly believe recursion is the best thing in all the situations :D After I tried recursion my wife unleft me, and my kids started loving me again
It truly is a blessed craft
Nice
Thanks!
I think that evryone forgot that lops are much faster then recursion because you mutate state. In pure functional programin this is not allowed and you habe to realloc
This is true - allocation slows things down. However, most of the time when you're doing loop operations, you're not actually modifying the underlying list - you're often creating a new one anyway
some languages can detect when your immutable manipulations of data are safe and convert them into mutations under the hood. Most of the time the cost is not something you will feel for immutability tho, unless you are doing it thousands of times per second.
if the compile is aware of immutability this allows the function to be optimised in other contexts (e.g. inlined, or parallelised)
For the most modern programming languages today, this is a bad advice. Loops are generally more performant and safer than recursion ...
infinite loops?
StackOverflowExceptions?
compiler optimization?
etc ...
but I understand the functional point of view of it that might be related to only pure functional programming languages
You can have infinite loops with regular loops too, and if you've got tail call optimisation, you won't hit stack overflow errors as each subsequent call replaces the latest stack frame, rather than adding a new one.
Also, compilers generally optimise loops and recursive calls down to the same tight loop in assembly. Sometimes the recursive assembly is actually shorter and more efficient!
depends on the language, some languages handle this stuff completely fine (Ocaml, lua, lisp, basically any language with tail call optimisation) and others simply dont and you probably shouldn't use recursion at all unless you really really need to.
Yep! This is true. Python, for example, handles recursion particularly badly
@@IsaacHarrisHolt Yeah I was thinking more about Languages like Python, C#, Vb, Java and maybe JavaScript...
Which are a little bit more popular ..
for example, Dotnet even have code analyzer to detect recurrsion code and suggests refactoring it to loops to improve the performance.
Sounds like they just need to add proper handling for recursive functions 🤷♂️ not every problem can be solved elegantly with a loop
No... you do?
did you even... watch the video tho?
I wonder if someone just read the title
Bad news for all the languages that don’t have loop, I guess
I don't like the way these videos are edited, too many random animations that take away the focus from what is being explained. And I don't even have ADHD, so imagine what it is for those who do.
It's something I've been working on, and I'm not totally happy with it either. Unfortunately time pressure often means I can do much else, much as I'd like to 😅
I like it. I would like more code highlighting though
I make the caption enabled and it helps me focus