Never write another loop again (maybe)
Вставка
- Опубліковано 2 гру 2023
- Live a loop free lifestyle, today.
Loops are an important part of software development. They enable us to perform sequences of actions repeatedly.
While we use loops often when writing code, they're not the only tool out there to achieve iteration. In this video, we're going to take a look at the other ways to achieve a loop free lifestyle.
Become a better developer in 4 minutes: bit.ly/45C7a29 👈
Join this channel to get access to perks:
/ @dreamsofcode
Join my Discord: / discord
Follow on Twitter: / dreamsofcode_io - Наука та технологія
¡Gracias!
Thank you so much! I really appreciate the support ❤️
In C, C++, and Rust, loops often compile into extremely well-optimized and vectorized assembly that is often impossible to improve upon. I'll stick with my loops.
In Rust you should really be using iterators if possible, but I agree that recursion is often not the best choice in languages without guaranteed tail call optimization.
@@ultimatedude5686 rust compile times are ... meh
@@krux02 How do Rust compile times have anything to do with what I said?
In Python, function calls are extremely expensive compared to inlining the function's instructions. That's why, when writing Python, you should usually favour iterative implementations over recursive ones.
Array languages like APL, BQN or Matlab use interpreters with statistics and dynamic typing to improve on specifically that vectorized assembly. It's more nuanced than you might expect.
Most common languages will perform better on loops than using recursion.
EDIT: Woah that's a lot of likes!
Pure recursion is dogshit most of the time
If you use tail recursion, you can rewrite it as a loop trivially and if you're using some kind of library functions that's probably how they are implemented in some languages. Smart compilers might be able to optimize other kinds of recursions too
@@ratfuk9340 Smart compilers might be able to optimize, but why would you make your code harder to read?
@@sarabwtwhy would it be harder to read?
Tail call optimisation just unrolls your recursions into a loop.
Basically means your compiler ends up turning this state machine automaton mathematics phd thesis construct into the normal ass control flow mechanism, as you would expect from a machine with jump instructions
This is a dangerous video for people who didn't already know all of this. It feels like it's targeted towards new programmers, but leaves out so many important details that if somebody would follow it to the letter it would lead to unusable code.
Most of the comments here are from people who write unusable code
Recursion is often far less efficient than loops. And many recursive functions will be optimized into loops by the compiler. Loops are also usually far more straight forward to read. So yeah, i’m going to stick with loops. Unless the data structure lends itself nicely to recursion, eg, Trees.
Loops are just sugar for iterators, so a recursive linear tail call is usually converted to that when possible. Actually, using map can be more performant then a for loop on arrays, because most machines have a special instruction for that. A for loop might not trigger this optimization as the compiler may get tricked in unfortunately too many cases.
Either way, performance doesn't really matter as long as you're not making something really outrageously terrible. I recommend using the higher level algorithms like reduce, map and filter over loops. For recursion, there are times when it's really nice instead of the while loop; for example in some parsing algorithms and file tree iteration.
@@user-uf4rx5ih3v
loops can be made iterators, and it's sugar for gotos
gotos run the world
can't escape the goto;
When you are dealing with a single processor core, that argument may hold water, but not with multi-core processors many times it easier to hand off recursive functions to the different cores than to try and break the iterative loop up and hand it off. For example: if you realize that 24! is the same as (1*2..6)(7*8..12)(13*14..18)(19*20..24) you can split the recursive calls to four separate cores (or split it into 4 separate threads) and then perform the final multiplication on one core. You can also do it with a loop, but you would have to break the loop up so that it's called in a separate function that can be called async. Now for the factorial above, it's not worth the effort, but there are examples where it is.
@@user-uf4rx5ih3v Define ”iterator” as you mean in this context. Because really, we are at the end of the day setting/clearing bits in memory and nothing more.
@@wlcrutch An iterator is a data structure that you can walk over, most of the time that would be a singly linked lazy list. When you do an operation over an array, the array will usually be converted to an iterator, the action performed and the list either converted again or deleted. Exactly what the underlying structure is, is language dependent, for-loops can make this a bit opaque.
If you ever run into issues using recursion, try using recursion to solve them
The plot of Interstellar in a nutshell
And in order to understand recursion, you must first understand recursion.
Nonsense, you can just use a Monad to sort it out…
solve your solution
Recursion is for specific use cases, not a drop in replacement for loops. Recursion often obfuscates the control flow of the program, makes memory management difficulty, but most importantly recursion is almost always slower than the alternative.
Assembly/Machine code do not have a concept of for loops, So it does not matter whether you right a recursion or a loop they both generate the same machine code using jump instructions.
@@shubhamsingh3068 That is not true or my point. The resultant machine code is dependent on the language, compiler/interpreter, optimization settings, program structure among others.
When examining assembly code, its almost impossible to distinguish whether it originated from a for loop, while loop, or recursion. However, different loop structures and recursive techniques do not yield identical machine code. (i.e. the recursive function calls will look much different than mere loops when examine machine code)
Most importantly we usually dont read and write code in assembly, we do so in high-level languages. "Recursion often obfuscates the control flow of the program, makes memory management difficulty, but most importantly recursion is almost always slower than the alternative."
@@shubhamsingh3068 recursion tends to have a large amount of function calls. This will result in vary different machine code and will be in inherently slower than merely looping for examplle.
@@sudoCompetence Depends if the recursive function can be optimized as tail recursion or not. Like the video pointed out, tail recursion will generate a jump instead of a function call, so there'll only ever be a single function call when calling a tail recursion function.
@@minilathemayhem That is somewhat true, but that is the exception not the norm. The majority of languages dont even support the feature to begin with and the majority or problems cannot be solved this way. Recursion (especially tail recursion,) can be faster, or it can result in similar machine code, but this is usually not the case. Regardless, most importantly, it almost never leads to maintainable and readable code.
This doesn't explain, why we shouldn't use loops, if the safety is guaranteed (like Rust's for loop with collections).
It's not bad for performance either, since loops are often unrolled and don't overload stack like recursion. They are also much more readable usually, since recursion can be pretty tricky to grasp, even if you're familiar with concept.
Even if the loop isn't unrolled, it will still be faster than the recursion (assuming it is the style of recursion that can be optimized to a loop but the optimization isn't enabled) due to a single jump being much less work than jump + setup new stack frame & locals.
@@Zullfix I mentioned it, because he made a point about how recursion can in some cases be optimised by compiler. But he never mentioned, that loops can also be optimized.
And yes, of course they are more performant even without optimisations, in the worst case, since function calls are memory intensive operations unlike loop iterations.
A tail-end recursion *is* a loop. It can be optimised just as much as your original loop, so the fact that loops can be unrolled isn't going to make a difference.
Functional programming is easier to understand once you have a grasp of recursion, allowing you to optimise not just the machine instructions but the whole algorithm.
Take a look at "A better way to think about Quicksort" by Sam Spilsbury for a good example of how quick sort in functional style is much easier to understand. If you understand the algorithm you can reason about it, prove it works, and replace it with a better algorithm.
Thinking that imperative programs "run faster" and therefore ignoring functional programming is both missing the point, and almost certainly going to result in buggier and slower programs. Pre-mature optimisation results in micro-optimisations that make it harder to find the macro-optimisations. Each such optimisation also has a cost in complexity that makes it harder to work with the code, and each line of code only takes seconds to write and is after that being maintained until the program is no longer in use.
That doesn't mean you need to, or even should, swap to Haskell and always write pure functional programs. Sometimes a scripting language is the best option, sometimes imperative is, and sometimes functional is.
A pure functional program is trivial to multi-thread because order of execution isn't even an issue, this allows you to optimise simply by throwing more hardware at a problem. It's not trivial to get a performance boost out of doing this, but the fact that it's not going to break is a huge upside. This is why databases are functional, SQL is a *functional* language.
Even if you ignore databases that run every enterprise scale website in the world you still have lots of examples where they picked functional programming over imperative and simply used clustering to solve any possible issues with optimisation.
@@Sylfa but then you find out that not every sort of recursion can have that optimization (which you can see in the video).
@@tri99er_The only reason you "find out" that is because it was written in a language with hidden side effects and without any tail call guarantees. This does not happen in e.g. Scheme, Kotlin or Haskell.
stack frames on their way to inhale all your memory rn
especially in embedded
That's only an issue if you don't use tail recursion :p. Instead, if you forget or write the wrong condition, you just sit there waiting forever while nothing happens!
@@minilathemayhemWhy don't just use loops then; in that case you don't need to crutch on compiler optimizations.
I’ve used recursion and fp extensively on embedded with rust. Never had issues.
haskell is the only language i trust enough with recursion, because fn programming looks like maths to me
That's because it is. Category Theory, mostly.
@@NostraDavid2 yeah, i heard someone say that haskell looks as if an actual mathematician made a programming language
@@NostraDavid2 Haskell is not category theory. It uses it for some major features, but its core is type theory.
Haskell is not a total language though, you cannot trust that recursion ever terminates. Try Coq or Agda instead.
if you're doing recursion too much in haskell you might be doing something wrong. you should prefer builtin constructs such as map filter fold scan traverse
I don't know why it's so difficult to just say use the right tool for the job. "I'll trade readable and safe code for performance any day of the week." What a quote. Firstly performance, safety and readability are not mutually exclusive, and what a perfect encapsulation of the difference between a developer and an engineer.
fung shei driven development
Surprised this doesn't have more likes. Recursion has its place, but so do loops.
You got it backwards, the author prefers readability over performance
@@Naej7 he didn’t get it backwards, the quoted grammar is just imprecise
Developer time and writing proper logical code is your main job, not being a memory mechanic. And an engineer uses math. Moving memory around is not math
"Never write another loop again"
Newbie, do not tell me what I have to do.
Yeah it’s funny. I imagine writing code that employs recursion for something that is trivially expressible by a loop. I can see every reviewer be immediately targeting that piece the moment it gets pushed into repository.
@@MikeKrasnenkov Or recoding an FFT to actually use recursion. They are coded as loops but the math developing them is based on a recursive idea. For an array length N that would be N*log2(N) calls
One thing to note is that we have to distinguish between two kinds of 'iteration':
1. Iteration that only makes use of O(1) local variables (as extra memory)
2. Iteration that makes use of at least some O(n) data structure (as extra memory)
And these correspond *exactly* to two kinds of 'recursion':
1. Recursion that meets the requirements of tail call optimisation (TCO) - called 'primitive recursion'
2. Recursion that has some components that do not meet said requirements - called 'non-primitive recursion'
The *simplest* function of type '2.' is called the Ackermann function, and it's ridiculously complex
This means that theoretically for most cases we do not need stacks (or queues), and we do not need stack frames.
But practically it requires a great deal of thinking on the behalf of the programmer to turn something that is seemingly in type '2.' into one clearly of type '1.'.
This is related to the Curry-Howard-Lambek correspondence, and further we can understand that for every problem there is a higher order function that deals with it, because we can interpret any 'container' as a 'functor'.
So we can also categorise containers (data structures) corresponding to these two types:
1. Containers that can be traversed (with their correct topology/semantics) without use of a stack or queue / non-primitive recursion, e.g. arrays
2. Containers that can only be traversed (with their correct topology/semantics) with use of a stack or queue / non-primitive recursion, e.g. trees
Also, 'nicer' (more 'optimisable'/'parallelisable') higher order functions correspond to containers that can be interpreted as 'monads' (monoids and semigroups) not merely functors.
High value comment. I hope more people read this.
Very well put!
I thought it was mentioned in the video that for the compiler to do tail call optimize that the recursive function needs to only call itself once? how can you turn the simplest recursive Fibonacci function into a type 1 recursive function?
@@FilipMakaroni_xD hold the previous values in the arguments to the call (there's only 2).
By the way I intended to edit this a little but I remembered that it would remove the heart.
Just wanted to mention the Church-Turing thesis as probably a more related idea to the overall point of recursion = iteration with primitive recursion = iteration using constant temp variables
@@FilipMakaroni_xD by the way, the fibonacci function can be generated by repeatedly applying a 2D linear transformation, which makes it extremely simple so writing it as tail recursive is often one of the first tasks for a functional programming course. If you try hard enough you can even find a closed form representation because the transformation is diagonalisable (no iteration/recursion needed anyway)
9:44 I found this loop version version much easier to read here. You can literally read out the intent word for word
"for each course in the list of course", "for each student in the course", etc.
I can see some cases where map, filter, etc would be more readable however, but this may not have been the best example
Maybe the intent of filtering the students by certain characteristics is a bit clearer in the second (reminds me of SQL)... but otherwise, I agree, I felt the same.
Though it's probably a case of familiarity, as I haven't used those functions (especially reduce) much.
for every for loop out there, there is a more readable version using higher order functions
@@marusdod3685hard disagree. Exhibit A for me is the example I already pointed out.
Not to mention performance. The higher order functions in this example are allocating a new array for each operation. The for loops are just walking through the data once
@@alexander53 that would've been many more lines of code with for loops, but aside from that in real code samples it almost always looks better, you just have too much Cnile brainrot.
performance cost is negligible. reminder that it's a jit compiled language so it's always performing allocations no matter what. and there are implementations using generators which only traverse on demand and don't build arrays.
you could rewrite this algorithm to walk only once too if you wanted using only reduce. it probably would've looked as bad as the for loop implementation, but you easily could
@@marusdod3685 fewer lines of code != more readable. In many cases it's the exact opposite.
I don’t write much JavaScript, so I guess “it’s js, it’s slow no matter what” makes sense for a js developer.
All these functions are using loops under the hood so really it’s just a question of what you’re used to. For me it’ll always be easier to make an explicit for loop performant and for me it’s much easier to read most of the time so ¯_(ツ)_/¯
@9:00 It's worth noting since the example of a language which uses fold instead of reduce that Rust has both fold and reduce and they are distinct operations. Reduce on an iterator if items of type T takes a single argument, a function, Fn(T, T) -> T, and evaluates to a value of type Option (where it's none if the iterator is empty). Fold, on the other hand, takes two arguments: an initial value (of type U) and a function Fn(U, T) -> U, and evaluates to a value of type U. So if you have an array of integers, for example, you can reduce it to an integer, but you could fold it into, for example, a set of integers or whatever.
This is moreso a product of Rust not having overloads than it is a semantic difference in the functions.
@@knifefest I disagree; if it was just the matter of having initial value or not, then sure, but in a strongly typed language, I feel like these are pretty significantly distinct operations. I'm not sure I love the naming, but even in a language with overloading, I don't think it would make much sense to make them one function, the type logic changes too much
Folds tend to have defined directions and possibly a different type than a reduction. In Haskell, reductions are represented by monoids and semigroups. They enable parallelism that a fold can't, since they could start anywhere (possible with associative operations). It also matters in numeric analysis; e.g. floating point sum is more accurate if it starts with the lowest magnitude terms. This reordering is possible because the addition is commutative, and could be implemented with a sort then fold.
@@0LoneTech I mean, more importantly, you floating point addition is not associative, so you're not actually allowed to reorder it. But yeah, I guess reduce assumes an associative and commutative operator while fold has a defined direction and can be any binary operator which has at least one argument of the same type as the output
@@yaksher It's a compromise, like the entire concept of floating point. f32.add is not associative because of the rounding, but its purpose was to emulate an operation that is, so in practice we might reorder for the purpose of a closer approximation of the higher level sum operation. Pardon the digression.
I still don't understand why you would use recursion instead of loops. I mean loops are the most basic and understandable thing in Programming in general imo. Also there's no need for a compiler to optimise anything that way. Try using recursion on a microcontler, it's gonna go up in flames.
not to mention that tail recursion translates to a goto, which is literally the same thing a loop does. In any case, recursion has many usages but it looks like people simply forgot how to code these days and try to fit into any problem whatever they are told is cool to use today. When the only you you "have" (remember) is a hammer, everything starts to look like a nail.
Put simply, because you already have all the mechanisms you need in the concept of a function call, and recursive form is often much plainer. Why make your task more complicated by reinventing control structures already fundamental to your language? The tree traversal example shows this plainly in the second data stack used as a task queue.
Having redundant stack frames (i.e. no tail call optimization) and limited stack space (e.g. for multithreading) are implementation details of a particular setup. Some platforms are extremely specialized such as PICs with fixed depth call stacks. Most microcontrollers don't care one way or the other, and there's little point pretending your compiler is incapable of doing things it can.
@0LoneTech "Why make your task more complicated by reinventing control structures already fundamental to your language?"
Exactly, why would you do that? Isn't the loop one of the more basic structures in most programming languages?
"... there's little point pretending your compiler is incapable of doing things it can."
While that's true, I would still follow best practices. Nothing is perfect, and no compiler is nothing. I don't wanna deal with bugs caused by a compiler not being able to correctly refactor some bs I wrote. I just don't trust anything anymore.
@@grillpig3860 Most? Maybe, but certainly not all. It only makes sense in a sequential structure, and that makes it awkward when you're targeting parallelism. E.g. in Haskell, it doesn't exist but can be built using the seq function (or the illusion can be built using the do notation). In Verilog or VHDL, it is only available within always or process blocks, but when targeting hardware it turns into deep logic, not a loop. And in array languages we avoid loops because we operate on arrays in their entirety.
Point is, you're arguing to keep *both* your and the compiler's job harder. Auto-vectorization is exactly the sort of unreliable optimization you worry about. There exists middle ground such as OpenMP's parallel for, where you explicitly write the same old sequential loop which is just syntactic sugar over a conditional goto, and a separate pragma to explain the the compiler you promise this loop in particular has very specific dependencies between iterations and should be distributable. Or... you could have used a tiny function, in a language that doesn't make that unnecessarily complicated, and the compiler would already know.
Quick contrast:
C: int result=0; for (int i=0; i
Rust does have the utility functions and compiler mechanisms to make efficient and safe loops in most simple cases. It also has syntax and semantics to make that unnecessarily awkward. It sits in a similar niche to Java; a language designed to force a particular concept onto the programmer. It's like building the mechanisms to do automatic memory management into the compiler but then forcing the programmer to be explicit about every step of it, rather than merely places where the distinction needs to be made. One example of something it won't make safe for you is if a for loop was supposed to have independent iterations; the sort of thing that OpenMP pragma is about.
Every language has awkward corners. For instance, Haskell's default record types are pretty awkward, and BQN (and other APL family languages) requires memorizing the names of operations to talk about them, since they're not written out, and sometimes overloads distinct operations on the same glyph (e.g. ∧ for both sort ascending and logical and).
I can say that recursion is really better when solving recursion patterns like tree operations, because it has a lot more chance to get stack overflow due to the depth of calls been too high
You can traverse tree with "memoized stack" and it's far better than recursive approach.
can't be sure on 'far better' but both has downsides, recursion has readability and maintainability over the memoized stack and you also doesn't need to manage the call stack in the code.
@@snk-js , complicated cases with recursive approach still more mind blowing. And performance.
It's like debugging Akka actors i.e.. Very difficult.
P.S.: I was fan of functional programming couple years ago until start thinking about some low level performance tips.
the simply arithmetic is performant in whatever the context, it's verbose but really stick to the ground of the fundamentals, while functional programming can solve a group of logical problems very perfectly, its not performant but its abstracted sufficiently so that it can represent solutions through art and abstraction.@@cryptoworkdonkey
it is not only about being better, sometimes the problem you're tackling requires recursion otherwise it is almost impossible to implement
Goto is my favorite loop
my favorite loop is f5
It's the most cursed 🤣 I had to put it in there
For loop is translated to a go to command in assembly, the previous commands are saved in the cache, with recursions you thrown this out of the window
Optimizing compilers often turn recursions into goto also. If the last thing to be done involves the recursion, the compiler can easily spot it.
@@kensmith5694 good to know
ironically almost all of the "improvements" shown made the code less readable to me because we traded whole word variables saying exactly what we do for letter variables which are more difficult to grasp and used functions which may be better for performance but hide part of whats going on f your not familiar to them and ironically despite js being my main language the last one i struggled more and more with every itteration.
There is a reason that Nasa straight up forbids recursion in their code.
For me letter variables are much easier to track than full word ones.
I absolutely love HOFs. I have been using a programming language called snap, which is a block based programming language like scratch, but more advanced. It adds a whole lot of stuff found in regular programming languages, like lambdas, lists as an actual data type (scratch just treats lists as a big variable), and it includes HOFs. I love how easy it is to learn how HOFs work in snap, they visually tell you what is happening, as well as making them easier to read. In fact, they are so readable that I tend to get a bit carried away and create ginormous HOFs, which would be completely unreadable in a text based programming language. Now, whenever I'm writing python, I do also use map a lot, specifically because it is made super easily in python, so easy that you don't need a function call.
Never write another loop again, or Never worry about consuming all your memory and crashing your app again
...until you mess up your termination condition or pass the wrong updated parameter.
The pitfalls are exactly the same, they just appear in different places.
@@totalermistthey are not the same, there's a reason why GPU languages don't use recursion at all
@ My friend, they absolutely are. "GPU languages" don't use recursion because GPUs aren't general computing devices - they are not the same as CPUs and hence don't even support loops (loops in GLSL, HLSL, CUDA, and Metal don't support non-constant loop conditions). Whenever you see a loop in GLSL, HLSL, CUDA, or Metal, the compiler unrolls them behind the scenes.
That's why only constant expressions and uniforms are supported in "loop" variables, even if built-in functions are used; those also need to have a constant input.
@@totalermist how that contradicts what I'm saying? They don't use it because is dangerous, and that's why it should not be advised in CPU because it will consume your resources, and do it without knowing the hardware the code will be running is a bit irresponsible, don't you think?
@ I think you misunderstand completely. Loops and recursion are mathematically *identical* , i.e. you can transform one form into the other without loss of generality.
The reason GPUs don't support recursion has _nothing_ to do with "danger" - it's all about the fact that GPUs simply lack the required hardware features. They don't have program-accessible stacks, accessible address registers, etc. They work differently and hence don't support the same programming paradigms on a fundamental level. And again - they don't support generalised loops and goto either.
From now on, each code review in which I refactor some convoluted loop into a single LINQ expression, my commit message will be some uppity pontification about _"Higher Order Functions"_ and _"Clear indication of intent"_ lmao.
What I really like about rust is that you really have no worries on using functional concepts on perf if theyre abstracted from imperative style
Both loops and recursion have their pros and cons, and can exist and should exist side by side depending on the needs of the project and language.
The only place where no looping really applies is where recursion is king, the functional programming paradigm languages
I agree with you 100%
@@dreamsofcode okay so what is up with the title that says never use loops or is it just clickbait
The neatest part of recursion is that you hardly ever need to implement it yourself.
There are all kinds of useful higher order functions that will turn your normal functions into recursive ones that do things for you, like folds, scans and unfolds
The body of a while loop gets complicated quickly because it will be calculating something, checking some condition and mutating some accumulator at the same time. Splitting those parts out into helper functions and then using map, filter and reduce is way more readable.
your description of why a while loop gets complicated sounds an awful lot like where you would use a for loop.
@@RotatingBuffalo for loops can only really keep track of one variable at a time, usually the index. it's much more descriptive and concise to use common higher order functions
C's for loops don't track anything at all; they're just syntactic sugar for a while loop, with a couple more places to traditionally use for initialization and iteration. Basic has the actual For loop, similar to Do loops in Fortran or Forth. Python has the somewhat more sensible foreach named for. Point being, there's no advantage in repeating by rote an explanation for the compiler of how to iterate over an array. Let e.g. map or traverse worry about that, and you're free to switch the data structures too.
I thought this was yet another video telling me that I code the wrong way, but it was actually very instructive. Tail call optimization in particular is a new and interesting concept for me.
I'm glad you enjoyed it!
It's worth noting that SQL is a functional language, it has no loops, and is the back-end of any website, business application, or other large scale system. And they are chosen for their robustness and *speed* improvement they offer.
Lots of people seem to think that the micro-optimisation of iterative over recursive is proof that iterative is better, but the truth is that when it comes to data processing functional is chosen nearly every time. The biggest exceptions are when you use GPUs to process data, and then it's mostly a moot point as you then work within the GPUs model which doesn't have the same width of languages to choose from.
Have a look at Futhark.
The main technical reason not to use loops is avoiding the inherent conditional jump, which prevents CPU pipelining though most of the alternatives had the same or more conditional jumps anyway and loops are often really easy to predict branching on (as they will only exit once).
On the other hand, the whole reason why we have the stack is the relatively minuscule amount of storage in the CPU registers from which data is actually processed. Ignoring this restraint can easily make a function run ten or a hundred times slower due to the speed of cache or memory fetches.
my favorite CS prof taught use a wonderful mnemonic for making sure our recursive functions had both halves. The two components you need to make it work are a "base case" and a "smaller caller".
I love this! That's a great mnemonic.
From a theoretical standpoint a reduction and a fold are very different things. A reduction basically uses divide and conquer, where it always bisects the array and then recursively calls reduce on those parts again. How many parts are in each half of the bisection is up to the implementation. In a fold, either the left or right half is always only 1 element large (depending on if it's a right fold or left fold) so they are a more specific version of a reduction, while a reduction is more general.
This difference means all three only give the same result if the operation you're performing is associative and sometimes even very simple things you would expect to be associative aren't. As an example float addition is not associative, so all three, left fold, right fold and reduction, can get you different results. In general folds are usually used with single threaded tasks, while reduction is used for multithreaded tasks, as you can compute a lot of operations in parallel.
The Haskell fold will usually be turned to a reduce if the operation allows. Most times, we assume addition of floats to be associative and commutative because we just ignore overflowing and rounding errors, as long as you can bound the errors, it's probably fine.
Good to know. Thanks!
As always, great content. Really enjoyed it. Thank you 😊
Very clear and concise explanation. Bravo.
The semi-oxymoronic conclusion of "One iteration closer to a loop free lifestyle" made me smile.
It wouldn't make a bad sweatshirt slogan.
Dang didn't catch that one, that's funny 😁
Would you share a course, how to create tutorials, visual implementation like this?
The answer is in map/reduce/filter/ecc... >>unless
There are also functional combinators for Promises, (or Futures depending on a language), e.g. All/Any.
Promise/Future themselves are already monadic in nature :)
I already knew all of this but stayed because damn it is satisfying to watch!
Excellent coverage of thr topic, thank you for making this!
Glad you enjoyed it!
Haskell has `foldM_` which does what a regular for loop with sideeffects does in other languages.
I would avoid recursion in even functional languages when alternatives like fold can be used. It is really easy to accidentally make something not tail recursive.
Judging by the name 'foldM_' does not seem like something intended for use by the programmer, since underscore at the end, from my experience, is used for incapsulation. Also, saying the recursion is always bad, no matter the language and use case is just as wrong as saying you should stop using loops.
The underscore is a convention for functions that return monads. If there is an underscore at the end of the function name, then it returns a unit value within the monad rather than a regular value within the monad.
Interestingly, I'd like to note that Kotlin supports a tailrec keyword on functions that will cause the compiler to error out if it can't perform TCO on it.
This is sensible. Scheme also has a set of rules for where tail calls are guaranteed.
It reminds me of SystemVerilog's always_ff/comb/latch, telling the synthesis tool what to expect and to alert the designer if the expectation is not met.
Vectorization is another useful tool for replacing loops, that also allows for parallelisation. You would typically use it for math-heavy computations in the form of vector and matrix operations. In some programming languages, or with specialised vectorized libraries, it makes all the difference in the world wrt. performance, and your code becomes much more compact. For example, in Matlab, a vectorized image processing function can be orders of magnitudes faster than for loops. Otoh, the code can be more difficult to write and understand, unless you are very familiar with this type of thinking and formulating algorithms.
This was a very concise and well-written explanation of using recursion over loops. I had a professor in the '80s that said "iteration is merely compiled recursion." And this video shows that. One thing missing is that (I believe) a binary tree recursion may not be a candidate for "compiled recursion" because it has 2 recursive calls, only one of which is tail recursion.
Nicely done, friend. Continued Success!
08:00 warning: do not overuse map and filter in javascript because they create new arrays
Which is completely fine 99.9% of the time. You're in JS!
I have news for u .. functional languages makes only new data structures, never mutate ;)
So they are useless by your metrics?
This is perfect for chaining, creating easy and readable code. Also the reason why React has something called states to manage this better.
@@jsonkody It really depends. If the compiler uses a memory arena to avoid repeatwd system calls for memory allocation and desallocation, then it might not be as bad. However, this is still suboptimal in comparison to only creating the data structures you need and there is still a reason for which functional languages aren't used in big projects unless for small things where safety becomes the number one priority.
This is JavaScript for you. To be fair though you should definitely should know this when you use these. They don't act on your source array.
It should be noted that JS is fairly inefficient in how map filter and reduce work. Each time you call one it's a separate loop and it's creating a new object (new Arrays in the case of map and filter). Compare this with other languages that do lazy evaluation of a map filter reduce chain, They will wait to the end, then do a single loop and do all the operations at once.
You meant filter and map? Reduce can implement both in a single iteration, but then it doesn't look "nice".
One problem I have with recursive functions is that when you look at the assembly instructions, you are constantly needing extra instructions to move data in and out of registers. Aside from possibly blowing up your stack, the performance of recursive functions can be slightly slower due to this overhead cost. When using loops, this isn't the case because all of the used variables are already in the stack frame memory.
I guess you have not watched the video until the tail call optimization.
Is the interpreter you use available? I don't recognize it and I've seen you use it alot
(I am infact new to linux and it seems like its linux based which would explain why i couldn't find it before)
There is nothing wrong with GoTo.... The GoTo eliminates overhead and is true to how the underlying assembly works. The only concern is if you are GoTo outside of scope and what's on the stack, for example, gets out of sync... So fine, constrain GoTo to within scope like the same function. Suddenly, you get much higher performing and smaller code size operations. You can also do nice things like make various points GoTo a common exit point from various places. So you can handle memory deallocations or various other end-of-function operations... even layered one after another... It's useful, efficient, and clean... I wish people would stop maligning GoTo. They have always been wrong.
Yes and also: The ability to assign a variable is equally as "dangerous" as a goto. Here is a very useful proof that code with no gotos can be worse than code with gotos. I will explain it as modifying some code from some using only gotos to some without any. I will assume a language like C
before the first line of the program insert:
****************************
XYZZY1 = 1;
XYZZY2 = 0;
while (XYZZY1) {
switch(XYZZY2) {
****************************
make a counter that will count up from zero we will insert as
For each line of the code that isn't goto insert
***********************************
case :
XYZZY2++;
break;
*******************************
If you see a goto, go find the label of it and find the on its case
case
XYZZY2 =
break;
**********************************************************************
For any halt, set XYZZY1=0
You now have absolutely perfect code with no gotos in it at all.
Good luck trying to understand it
The issue is that in the past it was used in ways for which better alternatives now exist. Naturally, it took a while before everybody was consistently using those alternatives, so people started shouting "stop using goto". Goto still has its place but people are still shouting that. It's just like this video's title: "never write loops". It's nonsense. You should use the right tool for the right job and sometimes that is goto, and sometimes which tool is right is merely a matter of personal style.
If you're replacing all your loops with recursion you probably learned to code from a toll-free number in a Cracker Jack box.
Luckily he never said you should replace all loops with recursion 🤣
@@Eutropios Yeah he just called his video "Never write another loop again", crossed out the words "for" and "while" in the thumbnail and presented recursion as a far superior alternative (according to him), but true, he never said we should, smh.
One thing to mention is that the immutability enforced by functional programming and recursion is key to parallel code execution.
This is because the loop equivalents can be executed at the same time on different CPUs without the need for shared memory.
That is a great explanation, thank you very much.
functional programmers love to talk about functional programming until its time to build scalable production apps
Like, Facebook's antispam, or Github's code highlighting? They couldn't have implemented that in Haskell, right?
@@user-yb5cn3np5q Barely any actual code is written in functional languages. Even the haskell compiler itself is in large parts written in C.
Nobody talks about non-functional programming! That wouldn't get very many views at all! "This video is going to talk about a failed program I made, and I'll tell you exactly what to do to get it this dis-functional," not great content!
Bro, you should learn what the term "functional programming" means. It doesn't just refer to "code that works", but specifically refers to a certain style of coding. Generally, you will use either functional programming or object oriented programming. I'd recommend you google the difference between those.
@@HenrikMyrhaug I'm aware. Thanks though for the heads up anyway! However, I was attempting at humor, unfortunately it would appear though that I have failed to indicate this clearly, and instead have misled people to believe I am ignorant of the topic at hand, this is unfortunate, I will attempt to do better going forwards.
I like to roll with loops and have fun with them so I always --funroll-loops. Recursion is the road to stack overflow.
Yes, and a segfault can be really hard to track down.
Higher order functions are invaluable when you need to bracket some code unknown at compile time with standard boilerplate code, for example acquiring and releasing a mutex for thread-safe access or beginning and committing a database transaction. For example if a collection is to be used from many threads the map(), filter() and fold() methods can take care of acquiring/releasing the collection's mutex before calling their procedural argument. Same thing can be done in for-in loops because in most languages the implementation of these loops requires an iterator object to be created which is implicitly destroyed when the loop finishes so the bracketing points are in its condtructor/destructor.
While loops are also just an abstraction over jump instructions.
You don't need any compiler tricks for tail call optimization, just call the function and reuse the same stack frame. I think that also makes it clear why those restrictions apply (must be final call, cannot have state left over)
Approved by a programmer having 7+ years of experience with Elixir and Haskell.
To further explain the comment above in your example of array sum calculation, you can right it like:
int sum(int xs[], int length, int total = 0) {
if (length == 0) {
return total;
}
// here xs, length and total variable are basically the state.
// By passing the state to the call, there is no reason for the
// compiler to maintain the calling stack frame.
return sum(xs, length - 1, total + xs[length - 1]);
}
How do you "reuse the same stack frame"?
@@ikemkrueger To do that, you just jump to an earlier instruction. This is why God made the GOTO :) :) :)
@@kensmith5694yeah: so to eliminate loops we use a goto.
And to pretend we're not using goto we write recursion and trust the compiler to substitute in the goto.
Yuck, goto 🤢
Higher order functions can be implemented in C and C++ quite easily through function pointers.
The quicksort function of stdlib of C uses exactly that so the user can decide what comparision to use.
Interfaces can be used in a similiar way.
So I disagree this being a concept only in pure functional langues or a pure functional language concept.
I personally also don't like higher order fucntions, because the performance hits are non-obvious.
The only time I find them useful is for multi-core optimization, because it's easier to see the atomic parts of the operation.
Also I really hate immutable arrays, except for very basic operations like print, or calling a function which each element.
If I won't modify my array, why would I iterate over it? The resulting data is redundant because it can be constructed from the array.
In my opinion using this kind of code is either for statistics or because you call a function with a side effect, e.g. print or send.
But I think in most cases it's rather the wrong way of representing data, as the way you need the data is different from how you store it.
E.g. if you need the students-grade data depending on the class the student is in, you should probably save the data per class.
While this is not possible for multi-dimensional filtering. I think query languages are much better at solving such solutions in an elegant way.
But I have to say I'm programming in an OOP Style (but avoiding inheritance and cascading objects to deep) and my interface design could maybe be transmuted into a higher order fucntion solutions, so maybe I'm just solving these issues in a different manner without being aware.
E.g. I always do trees as object-nodes with each node having a list of childs.
Function pointers are not a very good substitute for first class functions. They both can't carry information to distinguish what to work on, leading to the infamous void *userptr extra arguments with error prone casts and frequently redundant space allocations, but also force use of indirect calls and can't be inlined. I'm sure there's some workaround pattern in C++ these days but the library is an utter horror to try to read.
I just recently wrote a python script providing what I thought to be an elegant solution to an algorithmic problem with recursion. It failed due to insufficient memory. I then took the exact same function and simply returned the information necessary for the recursive call and did the other calls in a while loop. It completed in well under a second
Let's do things more like Haskell - that'll catch on XD Bwaha.
When *not* to use recursion:
- I need to mutate data structures in place because performance matters and want a prayer of debugging that shit.
- Async, recursion, debugging - good luck.
- The language doesn't support it.
- The language supports it but its not optimal.
- The compiler claims to support it but it doesn't actually.
- The compiler supports it on the dev platform but not the target plaform.
- The code works on my machine on test data but when deployed overflows the stack.
- When I need to be able to tell at-a-glance the loop is not infinite.
- When I need fault tolerant error handling and logging which alters program control flow. Recursion and filter functions always seems to get way more messy.
- When I need to debug anything non trivial.
- When I need to implement recursion for another language.
When to use:
- Playing code golf.
- For simple data transformations, sometimes.
- Hobby projects to learn more.
- Walking certain kinds of data structures but only sometimes.
- Some algorithms, but only sometimes.
- To fail code reviews creatively at work for sport.
- To discourage people from touching a section of code.
I love your vids, but you're triggering me lol. Good stuff!
Okay recursion works in some use cases, but the general solution is really loops. That's misleading and a bad idea to suggest to replace loops by recursion
While I don't _avoid_ loops per se, I absolutely make use of higher-order functions any time I can. In the PHP/Laravel world, it's common to create methods on your database models so that you can do very expressive chaining on collections of those models. Stuff like a 'noVerifiedEmail':
$users->reject->hasVerifiedEmail()
->each->sendAccountDeletionNotification()
->each->delete();
And to me, that is absolutely gorgeous.
And also, going over a collection twice for no reason at all when it could've done all the actions in one single loop...
that's actually very beautiful
Yup, nightmare fuel. Why write a simple for loop with a single if statement and 2 function calls. When you can build your entire system to be dependent on a whole ORM and then do things like this that only make sense in the context of the ORM.
Great example of it only making sense in the context of the ORM. Boscodomingo thought it was going over a collection twice. It's not, it's going over it 3 times. Once for the reject filter, and 2 eachs. It's 3 loops to accomplish the same thing as 1. On top of that it's also creating a whole new collection at the point of reject. Making it even less efficient.
Your example also seems to be intentionally nicer looking than the actual syntax. Wouldn't it be something more like:
$users->reject(function ($user) { return $user->hasVerifiedEmail(); })
->each(function ($user) { $user->sendAccountDeletionNotification(); })
->each(function ($user) { $user->delete(); });
Suddenly looks a lot uglier. And this is the reality I often face with these functioning chainings. They all expect an anonymous function to call. So the dirtier the anonymous function syntax & the more complex the function call itself is, the worse off the whole thing becomes.
In javascript land it's just *okay* because the anonymous function syntax is short enough that it's not a huge pain. Plus you can use typescript and make it about a million times better. But in PHP land it's genuinely disgusting.
And I'm not even a PHP or Laravel hater. I use both professionally. But I am an ORM hater. And I don't like trying to fit a square peg in a round hole. And this whole function chaining & functional programming just does not work well in PHP.
If you want functional programming. Just use OCaml or a back end language made for it. Stop trying to force it in a language that doesn't even have generics.
@@boscodomingo What's the problem with going over a collection twice, instead of once and doing twice the work for each operation?
It's at most a constant factor overhead. And many compilers for many languages support an optimization called stream- or tree-fusion (which is essentially the same as loop-fusion in imperative languages.)
@ In this case? It's just a really dumb way to write it. Hidden by how "nice" the code looks. Dude could've just made a function that both sends the notification and deletes and only needed a single each call. That would lose 0 clarity and compiler creators could sleep a little sounder at night.
But this type of function chaining encourages naive programmers to make non-performant code in really stupidly obvious ways. And then everyone goes "Well the compiler creators will handle it".
As if
foreach ($users as $user) {
if (!$user->hasVerifiedEmail()) {
$user->sendAccountDeletionNotification();
$user->delete();
}
}
Is so hard to read in comparison to:
$users->reject(function ($user) { return $user->hasVerifiedEmail(); })
->each(function ($user) { $user->sendAccountDeletionNotification(); })
->each(function ($user) { $user->delete(); });
Which again, could've just been:
$users->reject(function ($user) { return $user->hasVerifiedEmail(); })
->each(function ($user) {
$user->sendAccountDeletionNotification();
$user->delete();
});
And even further, could've just been:
$users->each(function($user) {
!$user->hasVerifiedEmail() &&
$user->sendAccountDeletionNotice() &&
$user->delete();
});
I have now subtracted the creation of a new collection, 2 anonymous functions, and 2 iterations over that new collection.
And is it really any less readable? No.
Explicit, external, internal variants of iteration or explicit recursion or abstracted away into higher order functions doesn't matter, it's still either a loop flow wise, or some other control graph that contains loops. If a compiler is built well enough, and the language provide specification and information enough, pretty much any formulation of one should be able to be written with more or less hassle as the other, as long as the language permits branching out of the loop in some way. Though finding a language and compiler that is commercially viable that can do it is a( whole )nother story...
Now writing non-trivial code in CPS to take full advantage of tail call optimisation, that is not an easy task.
cool video, didn't know that's how functional programs did it, or that theres a way to effectively do infinite recursion in c++.
thanks for making this.
you know theres an argument to be made about doing programing without loops can ever be a thing, because even when you use recursion that gets transformed into looping assembly jump statements. so technicalley you can never get away from it.
loops are literally the only thing we should be writing
according to who? you? why won't you just use while everywhere? or you know, only jumps and goto's while we're at it (no pun intended)
@@av-gb5cpLocal commenter tries to understand the concept of a personal opinion
@@enzoqueijao I will wholly and unequivocally resist the attempt to spew such opinionated nonsense!
@@av-gb5cp If you're trying to do that by talking the regular kind of nonsense instead then you're doing a real good job so far
according to hardware and caches... what are you even talking about @@av-gb5cp
At my company I'm not allowed to chain map and filter and instead have to use a reduce in those cases. For huge arrays and very performance minded applications that might make sense but it that doesn't apply to our typescript apps 😭
You can use streams (lazy evalutated function chains). For a given code using map, filter or reduce:
let acc = { };
let result =
array.map(x -> mapped_value(x))
.filter(x -> filtered_value(x))
. reduce(acc, x -> reduce(acc, x), acc);
Without streams the map, filter and reduce look like this. Which creates 2 copies of array along with 3 separate iterations.
let mapped_array = [];
for (int i = 0; i < array.length(); i++) {
mapped_array.push(mapped_value(x));
}
let filtered_array = [];
for (int i = 0; i < mapped_array.length(); i++) {
if (filtered_value(x)) {
filtered_array.push(x);
}
}
let acc = { };
for (int i = 0; i < filtered_array.length(); i++) {
acc = reduce(acc, x);
}
However, with streams the same code performs one iteration with zero copies depending on the situtation.
let acc = { };
for (int i = 0; i < array.length(); i++) {
let y = mapped_value(x);
if (filtered_value(y)) {
acc = reduce(acc, y);
}
}
Just write a wrapper function which filters and maps using reduce, this way you won't have to write reduce boilerplate every time you need to do these operations together.
@@shubhamsingh3068 You have it backwards, filter should go first so you avoid creating another reference (most likely with side-effects) altogether. Otherwise your solution can perform worse than filter-map chain in certain inputs/outputs.
@@ra2enjoyer708 no, filtering will be performed on mapped value not the actual value stored in array, therefore the order is important.
another useful functional language feature is called closures. in some languages, closures are all you have to make any kind of data structure. how do closures avoid issues like stack overflow, then, though?
8:51 In Dart there are both. The reduce function needs at least 2 elements otherwise throws an error. The fold function has a start value before making iterations. I believe they work like that as well in other languages.
I believe you're mistaken. Dart list reduce requires a minimum of one element, like a semigroup rather than a monoid (which can produce an empty value). This is similar to Haskell's foldr/foldl vs foldr1/foldl1, or BQN monadic vs dyadic fold or insert.
A good programming language is the one that can understand the programmer intent and then optimize it in binary form. The problem is, the intent should be explicit for a rock with lightning inside of it to understand.
The solution is either to have Mechanical Sympathy and take control of every instruction like in ASM and C, or to create programming language with many rules so the compiler can understand the programmer intent like Rust
While loop is just a syntactic sugar to loop{} in rust where you dont have to type if condition then break
loop{} is just syntactic sugar for jump
jump is just syntactic sugar for jmp.@@boblol1465
@@boblol1465 All flow control is just syntactical sugar for a conditional jump, tbf
Thank you so much for breaking the silence on beard kits and men's gift lists
Funnily enough, I've converted to primarily using higher order functions in Rust, but I ran into a bit of an edge case where a loop became necessary.
See, writing a tool to replace the password cracking tool known as Hydra (for ethical purposes only, obviously) came with the caveat that I wanted to stop as soon as I had found a valid combination, instead of just writing it out to a file. However, the use of iterators and higher order functions made this a little tricky, as I'd have to have some weirdness with external flags to avoid printing things out and - yeah, it quickly became very, very messy.
So what I did was I actually had a loop that called the result iterator's "next" function and processed results accordingly, with the ability to break out when certain conditions were met. Definitely a bit unusual in a language that loves iterators, but hey, you gotta do what you gotta do.
I use map/reduce/filter all the time for quick and dirty scripts but for stuff that needs to evolve you end up constantly needing to rewrite because these are all just a subset of what a basic while loop can do.
IDE's can trivially transform range/for/while loops into one another, but the only IDE I know of that can *sometimes* transform functional into procedural loops and back is rider with C#
It's just not worth it for serious software projects imo
any purely functional program can be expressed as a series of folds/reductions. function composition is, in fact, a reduce. as long as the inputs and outputs of your reducers are deterministic, you can express any computation in terms of reduce, and map and filter are just special cases of reduce.
@@celiacasanovas4164 I did Haskell for a couple years, I already know this. Reduce is fine for very simple stuff like sums, anything more complex looks significantly less readable than procedural code.
For me reduce is actually just a massive red flag that you didn't have the right functional tools for the job and should've just written procedural code.
Serious projects make great use of map/reduce-like operations. The notion that they are only for quick and dirty prototyping is nonsensical.
@@MikeKrasnenkov It's called an opinion? I explained it in the OP. Admittedly it makes a bit more sense in a Lang like Rust or python or real functional lang's where this stuff is kinda made to be kinda fast, but if you use map/filter in js you're just a bad person and should feel bad
@@pokefreak2112 I work closely with Java, C# and Swift, and higher order collection operations are used ubiquitously there. “Serious projects” do not end with JS. Even C++ has lambdas for quite some time now.
Repeat after me,
The stack is not infinite,
The stack is not infinite,
The stack is not infinite
Repeat after me - CPS is an equivalent of an SSA. So stack is irrelevant, really.
@@vitalyl1327
It's not equivalent, but share some aspects. CPS straight forward semantics, but a semantic for SSA must carry path history along as phi-nodes have no local meaning (you must know where you came from).
@@chudchadanstud Nope, it's quite easy to prove equivalence (and to translate one into another, which a lot of compilers do these days). See R. Kelsey, 1995, "A correspondence between continuation passing style and static single assignment form".
So, strictly speaking, SSA is a subset of CPS. Not any kind of CPS can be translated directly to SSA, but any SSA can be translated to CPS.
@@vitalyl1327 Theoretical equivalence isn't the same as practical equivalence. In practice the stack is not irrelevant. Because in practice it is fairly easy to get a stack overflow with recursion even in a purely functional language with tail call optimization. Almost all of theoretical computer science assumes an idealized computer with infinite storage, which makes a lot of the results only partially useful, considering the fact that most computers I know don't have infinite storage and usually even several orders of magnitude less stack space than main memory.
@@timseguine2 I said CPS. In CPS all calls are tail calls, no exceptions.
Beautiful. I like the VSauce-esce approach of hooking me with an interesting premise and teaching me different things along the way to the solution.
While I don't want to live a loop free live I did enjoy the video.
In my opinion the main advantage of loops is that they make it easy to optimize because the exit condition is more clearly defined and it's not as easy to accidentally make an endless loop when you think you're being smart.
Though I also prefer higher order functions when the performance isn't necessary.
I dont even know how to code, and im watching this from a SouthAmerican Jail.
and I'm watching you cristo from the security camera
@@spacecowboyofficial An I'm watching you from my mother's basement
Rust manages to weird in that sacrificing performance to more closely mimic other languages is actually _less_ readable than equally functional but faster code. The reason for this is `collect`, which is just about the slowest operation on a Rust iterator and is used to convert it into a more traditional data type. If however all you're doing is turning it back into another iterator, you can delete the collect call for faster _and_ more readable code with the only cost being losing the ability to name the type of the let-binding. In total, there seem to be 5 calls which can be removed for a free speedup as long as you also delete the two `: Vec`s.
I use mostly map, filter and (relatively rarely) reduce a lot in my everyday (js) programming, but I very rarely use hand-written recursive functions, I sometimes use index based for loops, particularly when I am going to do something that involves a lot of parallel random access in several arrays at once; particularly if I'm generating data from counters that doesn't necessarily step 1 at a time (where generating a temporary array [0..n] to map is more unreadable than a for loop) but even then I more often use map and the index argument to access other arrays more often than a for loop. I almost never use for each loops, because map works better, and I practically never use while. Whenever I consider using a while loop I usually realise I've created an infinite loop, or a potential infinite loop depending on input data; or otherwise realise it was a mistake and a regular for loop or a higher order function is more readable. To me it almost seems like the sole purpose of while loops in programming languages that have other alternatives, is to make the outer loop in a non-terminating interrupt based application; and in languages with events these are much better represented with event listeners than a non-stop polling while loop (even though internally that might be how the events are implemented in the interpreter).
Manual recursion and index-based for loops are so unusual that to me they signal something unusual is going on and you need to read the code more carefully; so in cases where I could potentially abuse map to do something where I'm not really mapping over an array of data (like creating a temporary range, filter it, and map it, to create odd indexes to look up those indexes or offsets to those indexes in several other arrays or multidimensional arrays or something); I would rather use a for loop or manual recursion to make it obvious that this _isn't_ just mapping an array.
Recursion uses stack memory, replacing loops with recursion is a very bad idea and waist memory space. Although many programming languages can optimize this for you it is still bad way of writing code (writing inefficient code and relying on code optimizer to take care of our code).
Recursion should only be used if you actually going to take advantage of calling and returning order otherwise you should alway either use for loop or while loop.
The example shown in this video is a great showcase of why functional programming is not a good way to think and design code.
Is that why you stick to Java and C#? lol
@@martinnorberg7940 As opposed to elixir, a bitcoin of programming languages, and haskell, a literal toy language?
The only use of a functional lang in production that I am aware of is OCaml, Jane street apparently uses it almost exclusively.@@ra2enjoyer708
"relying on a compiler" is literally the point of a higher level language. Do you think your CPU has a lexically scoped loop instruction or some shit?
@@JohnnyJayJay Hexagon enters the chat.
Man, this channel is gold!
Thank you!
replacing loops with high order functions is sometimes more readable. BUT I very very rarely use them because they are:
- much less convenient to debug.
- often slower.
also the first example that come to my mind of languages without loop is assembly not functional languages.
I'm a loop free programmer. Most of the time I use map, filter, reduce when coding Java and kotlin. I use for loops just when I code in golang
Avoid recursion at all costs. It's the very last option you should consider. Do it if a) you're hungover and you can't think of a proper solution b) the code really doesn't matter. Otherwise, barge pole.
What do you use for the animations in your videos?
ForEach, Filter, Map, Reduce or whatever you wanna call it are also loops, just using callback functions to perform operations on explicitly given data (no need to manually access array[index]). I am pretty sure in JS, in engines like V8, they are actually implemented using for loops. In other words you are still writing loops, just with different syntax.
I see no sense in using the more complex recursion stuff vs the compiler-optimized for loops we already use. Recursion is way harder to reason about.
Now, imagine your surprise if you were to find this pattern on older, "legacy" codebases, reading code from this one developer who refused to use loops. Do you and your's project future maintainers a favor and stick to loops.
They're often optimized to the same thing depending on the language and how your write them. Also recursion isn't hard once you do it enough, same as any programming concept. I'd argue writing a good loop is harder actually. Also the benefit is that when you or someone else comes back and reads the code, they're not faced with a loop to decipher but a (hopefully) well named function (e.g. sum, filter, map etc).
Make a program that walks a binary tree in-order and print it, only using for loops.
@@dakata2416 of course you shouldn't use for loops for everything. That's not what i said. But you definetly should use loops most of the time, and use recursion only when necessary.
@@dakata2416 Only needs 4 variables for an entire procedure, instead of between 4 and 4 * n + unknown amount of memory for the call stack + unknown amount of space in the error stream once it throws an error. And we are talking about real use cases, right? Aka the binary tree is so big it's impossible/unfeasible to store in RAM and therefore it has to be stored at least on a file system (and all the serialization/deserialization overhead it ensues). Which means no "just don't write erroneous code" cope because there is no such thing as asynchronous code without errors.
When people are no real developers,think recursion is error free, no stack overflow will ever happen. Stop listening to novices. Hiding loops in assembly level, solves nothing. Clean code is for academics and far from real applications. These are no hiring skills.
Based.
In the real world you either have a choice of using total functional approach, which is surprisingly powerful, or to limit yourself much more severely with the static upper bounds and other similar requirements as in the full MISRA-C rule set. Both ways are painful, but the latter hurts way more.
The call stack will overflow lmfao
Although I will not stop using loops or not even actively trying to reduce the usage, it was a good and interesting video.
🤦♂🤦♂🤦♂
Yeah... u can make everything more complicated using recursion... or less performant... or less readable.
Recusive programming is beneficial except in situation where it's not (about 99% of situations)
Hard disagree
@@ratfuk9340 Do the future maintainers of your current codebase a favor and just use loops instead of recursions, except you have a very good reason to do otherwise (like graphs or to solve certain concurrency related problems)
Max call stack size exceded lol
On many machines you just get a segfault and it is up to you to work out that the stack did it
Thank you i finnaly understand those imbricated functiun thingy i always stayed far from them cause i always found them hard to understand and was doing fine without it but now i will still do fine without but can understand them wich is better
The longer I watched the video the more of a clown show it became.
As soon as you brought out goto I was done.
Seriously.
There’s a reason why recursion isn’t used.
Computers don’t “work” like that.
Recursion is one of the worst concepts ever taught to anyone, it causes an incredible amount of overhead just so some chad programmer can say “look how elegant this is.” Yes, even in functional languages.
Your own examples in this very video shows how damn slow functional language recursions are in comparison…
Track a state and use a loop… far more memory and CPU efficient.
This is a horrible thing to advocate for.
You might want to ask yourself why every major language is moving if this direction if it's so 'stupid'.
@@adambickford8720 ...they aren't.
Recursion *is* bad.
Computers dont work like that. To compute a recursion it needs to either accumulate each intermediate step and then join them together (i.e. why you get "stack overflows") or do "tail call optimization" which is... effectively turning your "chad recursion" into a loop.
Just use loops.
It's what the computer knows how to do.
Recursion is what every first year CS student thinks is "genius" when it isn't. Learn how the hardware actually works, and you'll understand why.
I highly recommend Ben Eater's DIY breadboard PC series to learn how computers *really* work.
Then why your C++ compiler is converting every single function into a pile of mutually recursive functions first, before it can even start optimising them?
@@adambickford8720 You might want to ask yourself why is it that you think that languages are moving in this direction now. They already were there. C makes heavy use of this pattern and was heavily criticised by the mainstream "experts" at the time. Look at the sort function, which is a higher order function that you love so much, not to mention macros that can take a function and perform a transformation over a set. And after that was shunned, years later, people are now following the new "experts" who are claiming this is the best thing ever and that they have invented something new. I'm sorry, can't you see how absurd the situation is? Choosing to be completely on the side of only using recursion or only using loops is absurd. It's like people have forgotten how to code. Both constructs exist for a reason, why can't anyone remember this anymore? This used to be basic knowledge, how has this become so arcane and obscure that people have to act like it's the holy grail?
Every loop is a goto under the hood
Heh. long long ago, in a university far far away, I had to, for an on-campus work job, perform a recursive algorithm in Fortran 77, which, well, didn't support recursion.
Basically, I did what you suggest -- I managed to do all the operations as a part of a loop. It defacto saved its state in an array, then looped around, pointing at the next location of the array, until it met its exit condition, after which I just needed to resolve the contents of the array.
With C/C++ is there a function annotation or compiler feature flag so compilation fails if a function fails tail call optimization. Something like a -Wpedantic.
Please help if you have advice for what I'm getting at.
I remember seeing this in college, the professor didn't know how to explain the "why" to use recursive functions.
i remember when i first learned sbout recursion, i loved every topic of programming,
but didnt understand recursion.
thats because i looked at it linearly,
cause the examples i was given were linear examples (factorial, fibonaci)
these examples are awful at showing you how to think about recursion.
they make it seem like you need some kind of mathematical formula to be able to use it, and even then it can be difficut to follow the chain of calls.
if you see it for what it is a tree, where eqch node is the state of a smaller problem (represented through the parameters of the function)
and eatch line between nodes is a function call.
you get an intuitive idea of what is happening.
the tree of sub problems gets traveled depth first, up until it reaches a leaf, which represents returning an answer for a simple base case.
then it goes up a node, and continues to travel.
returning result for simple case,
calling for sub problems,
combining the results and returning that.
the arguments for a recursive function should contain all the information necessary to convey the problem /sub problem.
as in if you had to describe this puzzle what data would you need to do so.
+ arguments for sending data if required.
(you might care about some global thing such as how many levels deep you are)
dynamic programing is simply storing and retreiving results from recursive calls. its a neat optimisation that cuts off huge branches of the tree.
there you go, that's my knoledge about this topic. i have no idea why i wasnt though about the tree view from the start, it would have made this much easier to understand.
What do you use to make the motion graphics?
9:48 the functional/iterator version is HARDER for me to read. is this because i need to better familiarize myself with functional language? or should i conclude that functional simply fails at the goal of being easier to read?
Just reminding: if your compiler add loop - you assembler will convert it to jmp command....
Anyway - you cannot say you prefer readability over performance in vid you prefer recursion over loop.
Loops are the go-to from very good reason.
Yes but what if your higher order functions don't allow for the transformation you need? On occasion I find myself writing some loops in my Scala functions because the standard library apis don't provide the abstraction that I need.