why is recursion bad?

Do you remember the first time you coded a recursive function? The time when you finally understood what recursion meant, and were able to use it to calculate Fibonnachi's sequence. Well, I've made mistakes too. Recursion is cool, but in embedded systems, it's actually something you SHOULDN'T BE DOING. Recursion uses memory more than you think, let me explain.
🔥🔥🔥 SOCIALS 🔥🔥🔥
Low Level Merch!: www.linktr.ee/...
Follow me on Twitter: / lowlevellearni1
Follow me on Twitch: / lowlevellearning
Join me on Discord!: / discord

[@peterdecroos1654]

OP: stop using recursion Me: WTF recursion is an excellent way for handling certain problems! OP: in embedded. ME: si amigo

[@machineman8920]

poetry

[@mr.mirror1213]

lmao

[@phoenixshell3772]

This was me I got click baited hard

[@じゅげむ-s6b]

i haven't encountered said certain problems. what are they?

[@capsey_]

@@じゅげむ-s6b i think handling tree-like structure is very easy in recursive. for example, something like html elements tree and you want to change some attribute of all text tags. you write a function that changes the attribute if given element is text tag, and then iterates over all children of the element and executes this exact function for every child, which will execute function for all of tree elements under first one.

[@altairbueno5637]

Wait until he learns about tail recursion optimization

[@AJewFR0]

@@Wariowa345 compiler does some execution reordering to eliminate reliance on putting functions waiting for return values on the stack

[@yashdiniz]

@@Wariowa345 How I understood tail recursion optimisation: the compiler detects tail recursion, and optimises the code to convert it into a simpler loop.

[@Seltyk]

@@Wariowa345 removing the calling function from the stack before the called function is executed, leading to recursion without adding to the stack. Only viable when the result of the called function is dropped

[@ArmaganSalman]

@@Seltyk or an accumulator is used for the result.

[@ravish-shankar]

Yes, SICP

[@lordlucan529]

"Only 20,000 bytes of ram" - that sums up the capabilities of all machines I used in my first decade of programming. And that included doing recursion in LISP.

[@jhoughjr1]

think lisp machines had 1 mb of ram with maybe 20k free

[@vimtheprotogen2855]

Lisp has really good tail call optimization though right?

[@scheimong]

I once heard this excellent saying: "all recursive functions can be written with loops, since CPUs, as far as we know, cannot yet clone themselves." Edit: okay okay. To every computer science undergrad student here shouting "aCKeRmaN" (or maybe you just watched a Computerphile video, I don't know), I understand you want to show off that bit of fancy maths you just learned about. Chill alright. I said "can be written", which means EXACTLY THAT and NOTHING MORE. It doesn't mean you should (or shouldn't), or it's a good idea (or not), or whatever you imagine it's saying.

[@hackvlix]

But how is having more CPUs connected to recursion?

[@morphles]

This is absolutely incorrect, see i.e. Ackerman function, though that one is a bit contrived thing. But recursion is way way more powerful than looping.

[@climatechangedoesntbargain9140]

@@hackvlix a cpu executes all code iteratively. You can always emulate the behavior of a cpu

[@climatechangedoesntbargain9140]

@@morphles ackerman function can be implemented without recursion as well, just look at stackoverflow for examples

[@morphles]

@@climatechangedoesntbargain9140 Just did, and its a bit bs with regards to this:) still uses stack, so in essence all same problems apply that are mentioned in video, so some recursive problems, like ackerman function will require loads of memory regardless. And recursion is way simpler to write.

[@playeronthebeat]

During my apprenticeship, I came across a Linux dev who's rather "old" (I guess mid to late 50s). He explicitly taught us programming on high end Linux machines and even though they were enterprise machines with tons and tons of ram he specifically taught us to find ways around recursion. He'd always show us different ways on doing that. His motto? "People were going to the moon with less resources. Nowadays, we're just slapping more hardware on to the machine!" This was his critique on Game Development just as well as his critique on the company and other devs who usually didn't care. It was a very great and pleasing experience and it still sticks with me. Roughly two years later, I'm still trying to avoid every recursion I can. Not that I don't like it but why using up more resources than necessary or overfill any buffer etc?

[@pascal_case]

Dude sounds like a good teacher

[@javierflores09]

that is a very narrow view, with tail call optimization being a thing there's substancially no problem in using recursion and as for why, the reason could simply be ease of implementation

[@znefas]

@@javierflores09 For me, recursion is definitely useful with tree-like data structures, where you need to, for example, look for a file, or create a deep copy of a JSON-like structure.

[@ArnabAnimeshDas]

@@znefas Recursion has very niche use case and that too when directly modifying data on the storage (where only the current state should be present in the stack) and not on RAM. When modifying data on the RAM recursion should 100% be avoided in production apps. Even for tree like data structure it is possible to write an iterative approach although it might be harder. TL;DR: If you need to worry about recursion depth, you should not be using recursion in the first place.

[@znefas]

@@ArnabAnimeshDas As you said, if you need to worry about depth, you shouldn't be using recursion. But in most game engines, you won't have so many nested files to look through that you'll have to worry about recursion depth if you're using recursion to do something to every file in the structure.

[@Ganerrr]

I WILL calculate ackermann(4)(4) on an ESP32 and it WILL work

[@nathano7698]

I always find you on the most unexpected of videos

[@Ganerrr]

@@nathano7698 Mostly tech stuff im guessing

[@darkfire2703]

So I absolutely agree with not using recursion for the exact reasons explained in the video. A non recursive implementation is faster and uses less memory most of the time. That being said, it should be noted that most modern optimizing compilers can perform tail-call-optimization. So if you have a tail-recursive function (last statement is the recursive return call) it will be optimized to not allocate new stack frames.

[@ajinkyakamat7053]

But that would require embedded folks to turn on optimization. A huge proportion of embedded ppl never bother to do that or are just plain afraid.

[@gvcallen]

@@ajinkyakamat7053 I don't think that is the case at all.

[@ArnabAnimeshDas]

@@gvcallen actually some levels of optimization may kill certain opcodes thus introducing bugs

[@gvcallen]

@@ArnabAnimeshDas I'm not sure in what situation that would be. If your code doesn't work under optimizations it isn't written well.

[@ArnabAnimeshDas]

@@gvcallen I have encountered a code performing differently in different optimization levels of C. It is rare, but it is there.

[@averagegodotenjoyer]

I made a recursive path finding loop for a godot game. I was so proud then the stack overflow appeared and the whole thing had to be rewritten non recursively.

[@zondberg]

or add cache

[@Bratjuuc]

My inner Haskeller cries. I try to console him, saying that he has monads,arrows and lenses - He brightens up a bit

[@biskitpagla]

You should've mentioned how in some cases the compiler can optimize away recursion into what is effectively the same as plain old iterative loops. If I remember correctly, there have been some major advancements in optimizing recursion in the functional space recently.

[@silverasdf2055]

I was told in my DSA class that some compilers literally convert all that into iteration though tbh I’m not too knowledgeable on CS yet.

[@aleksandertrubin4869]

Usually those only work on non-branching recursions which often can be turned into for-loop with nex to none changes to code. In case of i.e. Fibonacci sequence I'm almost certain such optimization won't happen (although there are some fun ways to turn it into for-loop, and fastest of them for calculating F(n) involves multiplying 2x2 matrices and works in just log2(n) multiplications)

[@mskiptr]

@@aleksandertrubin4869 The lazily-evaluated Fibonacci sequence is t-c-optimized, though I don't know if it is even possible to translate that into anything suited for embedded programming fibs : List Integer fibs = 0 :: 1 :: zipWith (+) fibs (tail fibs) This essentially defines `fibs` to be a list starting with 0 and 1, and then all the other numbers are created in the following way: `fibs` ([0,1,…]) is zipped with `tail fibs` ([1,…]) and each pair of integers is added together (that's why we passed plus into the `zipWith` function). Maybe one can write it with Rust's generators. They are lazy right?

[@formbi]

@@aleksandertrubin4869 Scheme: (define (fib n) (define (fib-iter current next n) (if (= n 0) current (fib-iter next (+ current next) (- n 1)))) (fib-iter 0 1 n))

[@bozingo]

generally speaking the major feature of functional languages is that they perform a lot of complicated transformations that make functional code not horrible for performance and resource usage.

[@JasonDoege]

It would be worth mentioning the exception that is tail-call recursion and its associated optimization which does not use up the stack.

[@maltefgerdes]

Yep, TCO is nice, but in languages like C it's not guaranteed afaik.

[@jucom756]

I assume this means overwriting the "unnecessary" stacks from steps ago?

[@maltefgerdes]

@@jucom756 TCO replaces the recursive function call with a jump so it's basically a loop. But this only works if the recursive call is in tail position.

[@TheBilly]

@Niles Black Mega cringe

[@bozingo]

TCO is just when the compiler recognizes that your recursive function should have been a loop to begin with because it isn't getting anything out of the recursion, the function calls are more expensive than loop iterations, and it risks blowing the stack, so the compiler changes it into a loop under the hood so it's more performant and doesnt crash. i love functional programming and i love recursive functions but people act like tco is special when it's really the compiler telling you "you had no reason to write this recursively so im going to turn it into a loop instead because that's more efficient than what you wrote". there are lots of interesting uses for recursion but obfuscating loops in c-like languages is not one of them

[@Paralellex]

Something fun and barely related to the video: the fibonacci sequence has a closed form equation, so you don't need recursion to solve for the 1,000th one. You can just do this: function fibonacci(n) { const sqrtFive = Math.sqrt(5); return Math.round((1/sqrtFive)*((Math.pow((1 + sqrtFive)/2, n) - Math.pow((1 - sqrtFive)/2, n)))); }

[@digama0]

FYI, that implementation will run out of precision around fibonacci(78). By the time you get to fibonacci(1000) you have forgotten most of the digits of the number, although the video wasn't precise about whether we want the approximate order of magnitude (which the double precision method does calculate, although it fails around fib(1500)) or the low digits (which requires integers and modular arithmetic instead of math.pow) or all the digits (which requires bignum arithmetic).

[@bogdyee]

Pow is of logarithmic complexity so its not constant time there. You can use matrix multiplication for n-th fibbo and solve 1000000 fibbo number in about 20 * C steps (where C is a small constant) and also with maximum precision since your generating function looses it quite early on.

[@WilcoVerhoef]

{ 0, 1; 1, 1 }^n * { 0; 1 } gets you the nth (and n+1) fibonacci number exactly. Only limited by the size of your ints. (it's a matrix exponentiation and a matrix-vector product)

[@ayulin9577]

I feel like if you implement recursion safely, it is especially useful on embedded systems because you can usually write more compact assembly and space for code is generally very limited as well.

[@davidhayward1426]

I totally agree. Even on hardware with lots or RAM, the stack size of secondary thread can be quite limited. For example on macOS the stack size it only 512k for the secondary threads.

[@savagesarethebest7251]

Often this is not a problem as the compiler will convert a recursive function into a loop

[@Thebiggestgordon]

@@savagesarethebest7251 I don’t think you want to rely on the compiler to do something that your code already doesn’t do, as it may not do it every time or on every system.

[@savagesarethebest7251]

@@Thebiggestgordon most compilers does this on most system, tailcall optimization. It is a really basic optimization, why would you turn it off except in your debug builds?.. (or even then) 🤔

[@BruceNJeffAreMyFlies]

@@savagesarethebest7251 Why would you need to worry about memory allocation when Python just does it for you? Because programming is full of exceptional cases.

[@shail0124]

@@savagesarethebest7251 You are wrong Try to take factorial of huge number using loop and using recursion. You program of recursion will crash at some point and it will be alot slower as compared to function which will use loop

[@Skatinima]

There is a feature in some languages that make recursion just as effective as iteration, if used correctly: tail recursion. Tail recursion is having the recursive call as the last thing the function executes. By having the call as the last instruction, at a low level, the same stack frame is used instead of creating a new one.

[@spidersinmykeyboard6367]

Yep, was going to say this.

[@flutterwind7686]

Tail recursion is only efficient because it is optimized into an interative form before reaching assembly. No different than being iterative to begin with

[@Nofxthepirate]

Even in the "infinite" memory you usually get with Software Engineering, I've actually never used recursion in a practical way. As my Operating systems professor said: "If your solution is recursive, you should probably find a different solution"

[@redcrafterlppa303]

I wrote an inheritance tracing algorithm that was recursive and I think that's good, since it made it a lot easier and if someone has over a hundred levels of inheritance I don't think my recursive algorithm is the problematic code😂

[@EngineerNick]

I have always found recursive code really difficult to reason about anyway, except when traversing hierarchical / tree data structures

[@maltefgerdes]

That's true, recursive algorithms are best suited to data structures that can be defined recursively or inductively. One example that many people don't know about are inductive graphs, they are really nice :)

[@AnyVideo999]

I spent a lot of time tutoring functional languages and recursive tree algorithms, and the most common reason one may be an excellent programmer and find recursive algorithms difficult to reason about is that they prefer imperative algorithms compared to declarative, where the former is often more common in constrained situations like the example in the video. When I first learned recursive algorithms, I had a hard time reasoning when I tried to think of what each sub return would do rather than what it would produce. Once I stopped worrying about how the function worked and only cared about what it produced, reasoning became a lot more straightforward and you know you don't have to worry about the inner workings of the recursive calls. Of course, constrained situations can force you to think about these for memory or time efficiency which varies function to function as to how in-depth you have to convert to imperative to understand.

[@jeffspaulding9834]

I once spent a few weeks coding in nothing but Scheme, which uses recursion for almost everything. Then I had to write something in Perl and had a hell of a time switching my brain back to thinking in loops. You just have to train your brain to work with it. Once you do, it's not really any harder than reasoning about loops. There's exceptions of course, but there's always exceptions.

[@Anon.G]

@@jeffspaulding9834 lambda calculus vs Turing machine

[@g_cxl4511]

literally use a stack, its way cleaner and you can actually keep track of shit vs losing memory of whats what. const stack = [ root ] while (stack.length) { let node = stack.pop(); // do some processing with node if (node.left) stack.push(node.left) if (node.right) stack.push(node.right) } Easier to read.

[@UReasonIt]

I have never been a superfan of recursion in general. With loops and FSM coding, you can lose it. Back in the way-back days (the 90s), I did a nonrecursive tree library for a Z80 embedded system I had built.

[@anujmchitale]

I think recursion only exists because it drives up the endorphins in some. 😅 It's not even straightforward to understand logic in a recursive style logic.

[@macicoinc9363]

@@anujmchitale Completely agree, if the recursive code is longer than a few lines or has to interact with previous values, good luck.

[@FlameRat_YehLon]

Math use recursion to describe ideas rather often, but in programming usually that wouldn't be needed. Some programming languages do work on the idea that you SHOULD write recursion and let the compiler compile it into a non recursive loop (effectively replacing while) though.

[@anujmchitale]

@@FlameRat_YehLon yes.

[@UteChewb]

@@anujmchitale , when it was introduced to me it was, "this is how humans think so it is more intuitive." Ha, no it isn't.

[@ttamttam1522]

A few things I've learned when trying to squeeze every last byte out of memory: - You can shrink down on your stack frame size of recursive functions by using statics in places you can get away with it. Of course if your code base is huge - and only a handful of functions are on the stack at once - this will hurt you. But in general most functions on embedded systems are run many times continuously. So statics can help shrink the stack frame size and help you fail faster if you are using too much memory (ie higher base memory usage but lower peak memory usage). - In addition tail recursion, as already mentioned in the comments, can be pretty helpful. - On some architectures like AVR you can move large constants like strings into program memory to save space. - Reuse your strings: if you have the same message appear 100 times in your program, make it a global static constant (or put it into program memory for AVR) and reuse it. - Keep debugging strings minimal: I tend to shoot a lot of different status messages over any free bus I have available. Instead of sending strings directly, encode your messages using something like an enum for a status code, send that, and decode it into a string on your end. - Favor high CPU usage over high memory usage : micro controllers may be slow, but they're probably faster than you think. You may be surprised by just how much they can do. Say you have a temperature log and you want to take the integral. In some scenarios it may be tempting to calculate the integral once and store it to another data set. If you're short on memory, that's a huge resource sink. Just take the integral up to the point your concerned with every time you want that data. Sometimes that will not perform fast enough, but I've been surprised by just how much my microcontrollers can do before being bogged down (the biggest thing that makes them feel slow is usually io), so try it first and see if it fits your performance constraints. - Ignore these optimizations if you aren't short on memory: sometimes you can afford to be wasteful, and your code will be better if you follow best practices for maintainability instead of memory footprint.

[@otesunki]

as a hobbyist compilerdev and pure functional programmer, i feel mildly obligated to pop in here: firstly, the title is. uh. slightly misleading? secondly, i agree, recursion is apocolyptic if your call stack has a maximum size of 4..... ....which is why people who had to use very limited memory had to figure out workarounds. tco is the most well-known one (handles the most cases, including what you showed in the video), ssa is slightly more obscure, cps is more obscure still, and aps is extremely obscure. these are all techniques that can be used to turn recursive code into non-recursive code (yes. even ackermanns function.) and sometimes even into faster code than a human could write. thirdly, recursion actually has a chance of reducing bugs, since the base conditions act as built-in unit tests. with all that said, i do agree that you should at least be weary, but this is way too overthetop.

[@javierflores09]

I am not sure of what you mean by those styles being obscure, cps (continuation passing stye) as well as aps (accumulator passing style) are very common practices in programming and ssa (Static Single Assignment) is a common feature in optimizing compilers as well however I don't understand what is the point in mentioning those, to me it just seems like a bunch of buzzwords put together that don't help validating your statement as to why recursion is good

[@jimmyneutron129]

"firstly, the title is. uh. slightly misleading?" That is called a clickbait

[@hackvlix]

Recursive functions are great in theory, since it is easy to prove the correctness of recursive programs (almost by construction, as recursion builds on the principle of induction), and once you're used to recursive functions, it's also often easier to understand a recursive program. In practice however, recursion should be avoided for the very reasons described in this video. Every recursive program can be replaced by an equivalent loop program in principle (Turing equivalence of mu-recursive functions and WHILE language, if I remember my theoretical comp sci correctly), but this might also be very hard to do in practice if the recursion is not of a particular kind.

[@morphles]

Again, this (avoiding recursion) can be very true for embeded, but in general IMO it is one of worst advice ever, but then people go around programming in imperative, or OOP... Recursion is declarative, in many cases considerably easier to reason about correctness, and with fancy languages there are lots of things that compiler can do, automatically for you.

[@hackvlix]

@@morphles Alright, I admit the blanket statement "avoid recursion" may be too simple. I suppose it's a matter of weighing efficiency against clarity.

[@anujmchitale]

@@hackvlix Yes, though majority of recursion lovers don't even think on those grounds. That's the problem. If the language forces us to use recursion then there's no choice. But if it doesn't, it means there is ALWAYS a non-recursive way to achieve the required functionality.

[@davidwuhrer6704]

@@anujmchitale That non-recursive way will also use up the stack.

[@anujmchitale]

@@davidwuhrer6704 Yes.

[@echo5327]

I just had an interview question regarding this the day after I watched it, KZbin can officially predict the future

[@ubruminations]

The video overstates the case. While it is true that recursive functions can grow the stack, most well structured recursive functions need not. Others have mentioned tail-call optimization. It turns out that this optimization is very easy to do _manually_ in C. What this means is that you can write a tail call recursive function and then easily convert it to simple iteration without losing the recursive feel of the algorithm.

[@monad_tcp]

0:23 bro, just get a proper optimizing compiler with tail recursion reduction. In embedded you can have recursion, as long as its always tail call recursion.

[@Horgitage]

Until I learned about divide and conquer algorithms, I didn't know much about recursion or how to do it properly, if you end up in cases where you compute a lot of the same problems you can use memoization to speed up the process, this does also apply to normal iteration.

[@MIO9_sh]

My biggest hate on recursion is that it's so hard to keep track of states in the debugger, you have a hell load of states tracked backwards with recursion, definitely not want to use it unless it's tree traversal, but even for trees i'm still looking for a better way for that than recursions

[@MrTomas7777]

"Calculate the Fibbonacci sequence using recursion" Oh no... here goes naive O(2^n) algorithm

[@williamdrum9899]

Running fib(3) on sega genesis: done in less than a second Running fib(1000): it's been 10 minutes and I don't know if it crashed or not lmao

[@ChristianKoehler77]

There are two classes of recursive functions: a.) Those that either return the result of the recursive call (recursion is the very last step in the function) or don't recuse at all. This is called 'tail recursion'. Fibonacci is an example. Such a function can be easily transformed into a loop without recursion and without additional memory requirements. Programming languages that heavily rely on recursion (LISP) usually do this optimization automatically. b.) Everything that is not just tail recursion (and cannot be rewritten that way). Such algorithms rely on temporary data that cannot be discarded before the recursive function calls itselfl. A typical example is Quicksort. You need to remember what needs to be sorted later. If you rewrite such an algorithm without recursion you will need additional (and dynamically growing) memory anyway. If that is more or less efficient than a recursive functions that puts that data on the main processor stack depends on the circumstances. Using a static array for an iterative Quicksort can be very efficient. Using a stack that uses a linked list and dynamic memory allocation for each item can be much slower, use more memory and lead to memory fragmentation, very bad in the embedded world.

[@DelgardAlven]

Nice example, thanks

[@AlessioSangalli]

Came to the comments to see mentions of tail recursion and it seems we have enough CS people here 🤣 In truth, I love recursion as I studied LISP (Scheme) before even C, but that is another story. Hey next time try to lower the volume of the music 😅

[@AlessioSangalli]

@Niles Black can You rephrase? I am not sure what you mean. Are You familiar with tail recursion ?

[@maltefgerdes]

Recursive algorithms tend to be easier to formally reason about. In safety critical embedded systems this is a nice feature. And your argument gets irrelevant if TCO is used.

[@simivb]

Formal reasoning doesn't seem to be very relevant in practice, as safety critical systems, like the automotive industry, explicitely FORBID recursion because it is harder to understand. (See MISRA-C guidelines). I also gotta say that since the straight up fetishism of recursion in functional language during unversity, I haven't really seen any use for it besides the places where it just comes naturally (like tree traversal or something like that). Tail call optimization always felt a bit weird to me, because it's like "Yay we got the exact same efficiency as iterative, unless the compiler goofs and misses the fact that it can apply TCO here" (I believe scala had problems with this when I worked with it). Like, just write it iteratively then and cut out the middleman. And, of course: Not all recursion is optimizable with TCO.

[@maltefgerdes]

@@simivb I just looked into the MISRA-C Guidelines (the 2004 one, because I couldn't find a 2012 one) and the stated reason for banning recursion is indeed because of potentially consuming up all stack space. BUT this isn't a problem of recursion in itself, the problem here is that we are talking about the C programming language and no C Compiler guarantees TCO (there might be Compiler specific directives for that though). So to me this says nothing about the difficulty of formal reasoning about recursion, just that C is bad at supporting it. This may very well be the reason why formal methods may not be used that much in practice. It's sad though.

[@Ma1ne2]

Loving this type of short informative video zoomed in on one specific topic, more please! Also, great visual support for your explanations!

[@killerkiller5160]

I am currently working with 8051 assembly to reverse engineer math functions in keil microvision i notice keil compiler is replace assembly call instruction by using long jump in recursive function so no stack operation is involve. so it depends on your compiler algorithm😁. But good video bro i love your contents thank you so much keep it up (the real man create any thing in assembly😎)

[@anand.suralkar]

I did basic programs in keil using c and 8051 assembly basic ones like decimal to binary etc using 8bit display. its was so fun.

[@davidhand9721]

There are cases when that won't work. I mean, call is just push and jump, yes, but there are often important reasons for that push. You can only replace call with just jump if it's effectively a tail call.

[@ducodarling]

This is really a compiler issue. A proper implementation of tail-call recursion should only use a limited amount of space.

[@teoontube]

Indeed.

[@timurtheterrible4062]

You can't always use tail-call recursion.

[@nachobounty8947]

@@timurtheterrible4062 Are you sure I thought there is always a tail recursive solution?

[@kartonrad]

@@nachobounty8947 if the result of the recursive call is combined with local state, the stack frame is required So this use of recursion essentially uses the call stack to avoid using an actual dynamic datastructure

[@driden1987]

Thank you!

[@Requiem100500]

Actually, regardless of how much RAM your PC have, stack size is still very limited. On Linux for example, it's a constant set during kernel compilation, and is generally 8Kb, 16Kb, or 32Kb. Edit: as comments said, that is true for kernel space, not userspace.

[@catocall7323]

@Esiarpze or you can iterate, making more readable code, that the runs just as fast or faster and doesn't necessitate messing with stack sizes.

[@maltefgerdes]

@@catocall7323 Readability is subjective. It totally depends on your background.

[@catocall7323]

@@maltefgerdes although this is true, I bet the vast majority of programmers aren't that familiar with recursive heavy functional programs.

[@maltefgerdes]

@@catocall7323 sadly true :(

[@SurenEnfiajyan]

Do you mean for userspace applications or for kernel/driver?

[@zinsy23]

Interesting. I've primarily used recursion for carrying a number with an addition related function or getting the determinant of a matrix represented array. That's good to know what happens at a lower level! Subscribed as I planned on learning lower level concepts this year!

[@AnonymousAnonymous-gh5fs]

Renaming proposal: "Recursion is bad (in some contexts)"

[@empireempire3545]

I hate recursion, for me recursive code is just 10x less readable and intuitive than looped.

[@ZygalStudios]

I was once told: "Can you do recursion on embedded systems? Sure you can! But not for anything useful" 🤣 Great video! It succinctly explains the concept and its effects.

[@GuRuGeorge03]

I only once ever used recursion (not in embedded systems) because I was tasked to use some legacy code, without changing any legacy code (emergency room software that needed 100% guarantee to be backwards compatible). I built a rather complicated design pattern comprised of visitor, decorator, facade, adapter and proxy in order to get it to work. the main thing of it was having the visitor pattern being called within the proxy and facade. I felt super clever when I did it and it was the first time in my job that I really needed to dig deep into the classic software architecture stuff that I learned in university. When i was able to present the result and I got the merge request approved from some serious senior engineers, I felt so good, lol

[@ashtentheplatypus]

I never much liked recursion. It feels equivalent to using a non-renewable resource that could run out before the program is complete. Whereas using loops would simply reuse the same resources forever and ever until the program is complete.

[@anujmchitale]

Exactly, recursions are wasteful, most times.

[@alex_jellymath]

Sidenote for people like me (saw the randomly recommended video, watched it with some confusion, noticed the channel name only afterwards) - it might not be the case for your favorite programming language but I guess it's correct in the context of this channel. Like some languages can be pretty smart about optimizing recursion-related stuff (like Haskell and other languages that prefer pure functional style), some can provide things to explicitly optimize recursion (like tailrec and DeepRecursiveFunction in Kotlin). So in that context the proper solution might be just to use whatever is more comfortable for you. That being said, in the context of embedded systems I would guess that it's actually more complicated.

[@anujmchitale]

It's a death trap in embedded systems. I never found any appeal in recursion but then again, my mindset is of the embedded systems and closer to hardware.

[@davidwuhrer6704]

@@anujmchitale It makes code simpler, and helps avoid bugs. But only if the compiler knows how to avoid using the stack for recursion, which most embedded C compilers don't. So you have to do the computer's job by hand. C is not as close to the hardware as most people seem to think it is. For example, C does not have a way of reading the CPU's overrun register. You have to write an elaborate boundary check which the compiler then translates into a single assembly instruction. C _is_ a high-level language. And with today's code generators for embedded setup and configuration, you're sometimes closer to the hardware with shell script.

[@anujmchitale]

@@davidwuhrer6704 Most C compilers allow for directly including assembly instructions into the code. So not sure about the elaborate method part you mentioned. Yes C is a high level language but when one has to work with very limited resources of a microcontroller, recursion is hardly ever used.

[@davidwuhrer6704]

@@anujmchitale Do you always garnish your C code with "extern(asm){" when you check for integer overflows? It is possible to do stackless recursion in assembly, too. That's often how loops are implemented. (Fortran and shell script don't use a stack for recursive calls either.) But when you try that in C, chances are the compiler will still use the stack.

[@anujmchitale]

@@davidwuhrer6704 I mentioned about asm only because you said a single assembly instruction required lot of logic in C. Well, there's an option to use asm. Generally, overflows are avoided by static compile time checks, and coding standards. In case they still exist, I guess there's no protection within the code, as far as I have come across in many of the different embedded sub-systems. This may be poor quality standards but that's how so many of reputed international companies program. As for assembly, every single recursion is ultimately converted into a loop. There is no other way to do it.

[@familyshare3724]

Recursion is useful and maybe even necessary when each iteration needs to retain state or for branching logic .. both of which require lots of stack memory.

[@GrimTheDestroyer]

Video : stop using recursions Me who doesn't understand recursions: I am 4 parallel universes ahead of you

[@theillegaltaco6]

The first language I learned was C++ and I was only very briefly introduced to recursion before being told "it is always less efficient than a non-recursive solution." I have never once used recursion because of that; I used it so little that I can't even recognize a situation where recursion would be a good option. I really feel like I'm missing out on elegant solutions since my brain doesn't even consider them, but I suppose it is nice to know that it is technically more efficient in most cases (assuming the compiler doesn't just optimize it for you).

[@matthewkolar7560]

Recursion is good primarily for reducing the written complexity of node-graph traversal algorithms that lack a concrete bound. Note as said above, these can generally be written as tail recursive.

[@Bravo_0-7]

I encountered this issue with python when i was making (surprise surprise) a fibonacci term calculator. It worked using recursion and storing all values found to a list. It all worked beautifully until I tried calculating a term that required over 1000 recursions (the default depth limit for python). The next thing I knew was that I created an equation that takes in the current size of the list of fibonacci terms as well as the recursion limit that python is currently set to. I modified this function to calculate what the biggest fibonacci term was that you could calculate with the current size of the fibonacci list, and approximately how many times you'd have to manually call the fibonacci function before getting to the number you wanted. Ironically, the mathematical function for the maximum fibonacci term uses recursion. Basically, y_{m+1} = 2x-7+y_m, given that y_m is the current size of the fibonacci terms list and x is the current recursion limit. The highest term is just y_{m+1}-1, or 2x-8+y_m (yes, those equations are written in latex). Either way, that's how I dealt with recursion lmao

[@zackyezek3760]

As an actual systems programmer, my heuristic is to use function recursion for highly STATEFUL recursion logic (like recursive descent parsers & encoders for JSON, XML, etc.) and loops for everything else. Basically, for things like recursive parsers the cleanest & simplest implementation is usually a small number of stateless, recursive functions that call each other. Logic that you could only implement with pure loops by writing your own de facto program stack (a stack of structs storing the current state & previous ones, which is what “the stack” really is). Having tried both, the recursive functional approach really is better unless you’re so resource limited you can’t (I.e. no RAM). For nearly everything else plain old loops are better. Especially for things like computing Fibonacci numbers or other “map reduce”-like logic where you only need to track minimal state, like the running sum or last index.

[@SpeedingFlare]

I tried testing what happens when I have a 3k byte array local to the setup function on my Arduino with 2k ram. The compiler doesn't warn, and it corrupts the Arduino when it runs. I had to re-burn the bootloader to recover it

[@LowLevelTV]

There's a chance your stack allocation overwrote the area mapped to bootloader flash.

[@AlessioSangalli]

Whatever happened it doesn't really have much to do with recursion?

[@SpeedingFlare]

@@AlessioSangalli oh but it does ;)

[@AlessioSangalli]

@@EmbeddedSorcery did that CPU have cache memory? 😭

[@AlessioSangalli]

@@EmbeddedSorcery DMA is really peculiar when you have to use it with cached memory areas that require to manually flush and invalidate 🤣🤣

[@xxbongobazookaxx7170]

When I write a recursive function I am well aware that it sucks, there's just 1 problem, I'm writing in python it was doomed from the start

[@dvoid4968]

I figured this out the hard way when I made a tree with 1000+ cylinders in blender and every application I had open crashed

[@Axman6]

“Stop using recursion if your language of choice is bad at recursion” “Stop using X if your Y is bad at X”

[@coder_foo]

Funny enough, Fibonacci is a pathological recursion case. The computation time explodes exponentially.

[@yetanothertroll]

And if you use memoization to deal with that, you may as well just do it iteratively. EDIT: Pathological recursion cases usually turn out to be dynamic programming cases

[@DrewTNaylor]

I've literally never even heard of recursion in this context, and I've been programming since 2012.

[@EidosX_]

Haskell programmers: *panic*

[@Amy_A.]

I've never seen a recursive function that couldn't be done cleaner and more effectively with a loop.

[@bloxrocks5179]

once i thought about using recursion for something. it ended up taking like 5 variables 3 of which just decided what sub-function to spin off and i knew this was a stupid approach.

[@FalcoGer]

Any problem that can be solved recursively can also be solved in a loop. Function calls don't just allocate stack space, stack space is more limited than heap space (though generally faster). It's also harder to read in most cases. Some problems are very elegantly solvable with recursion, but most of the time it's a mess that you need to wrap your brain around at least 3 times to figure out what it does. On top of that function calls are slow. The processor has to save the registers, in particular the old stack pointer and return address, allocate stack memory and execute a jump. At the end it needs to unroll it all. If you do something like fibonacci, that's a complete waste of resources. You only need to store 2 integers and run a for loop to update them, not assign kilobytes of memory just to get the 1000th number. Instead you can get away with 12 bytes (the aforementioned 2 numbers and the function argument for which number you want). Even with gigabytes of ram, the stack size is fixed. In linux the default maximum stack size is 10MB in windows it is 1MB. If you do something complicated that requires lots of stack space per function call or recurse too deep you're going to run into a blockade if you rely on recursion. That's also the reason why you should put big data structures on the heap and have only the pointer to that address on the stack. I just compared the naive, recursive approach for fibonacci with an iterative loop. unsigned long long fib_rec(unsigned long long n) { if (n == 0) { return 0ull; } if (n == 1) { return 1ull; } return fib_rec(n - 1) + fib_rec(n - 2); } unsigned long long fib_it(unsigned long long n) { if (n == 0) { return 0ull; } if (n == 1) { return 1ull; } unsigned long long parent = 0ull; unsigned long long grandparent = 1ull; unsigned long long result = 1ull; for (unsigned long long i = 0; i < n; i++) { result = grandparent + parent; grandparent = parent; parent = result; } return result; } in c++. running a loop from 0 to 50 took 160 seconds for the recursive function and 0.1 seconds for the iterative one. Compiled with g++ -O3

[@bootmii98]

thank you for not showing b-roll of a fractal or other strange loop/improper hierarchy

[@modolief]

I program at the application level, usually using JavaScript or Ruby. Several years ago I had a good use case for recursion. I had a tree data structure that I needed to step through, and found that recursion was the most intuitive way to look at the problem. I only ever had data trees that went no more than a dozen or so nodes deep, so I was definitely not worried about blowing up the stack.

[@Shadow__X]

When I calculated the Fibonacci sequence the first time I just calculated the next number by shifting numbers around variables and adding the two most recent together

[@owenwexler7214]

As a web developer don’t think I ever use recursion outside of job interviews and school myself. Almost certainly, a library, framework, or other dependency I use uses recursion under the hood though.

[@davidwuhrer6704]

If you avoid recursion in JavaScript, you're slowing down the VM JIT. This video is about embedded programming, where the machine isn't virtual, and the HLL is not as portable as you'd like.

[@traywor]

Ever heard about tail recursion? Yeah, me neither.

[@CobaltSpace]

If you are doing a "recursive" math function, you should first see if there is an O(1) method. Search fibonacci sequence closed form for example.

[@DanielBrice7f58a6]

Sure, but for that to be O(1) you need to use floats, which starts giving wrong answer after about n=50, IIRC? If you want actual usable answers, you need a variable-length data structure for integers, which means you're going to be at least O(log(n)), but it's worse than that because then you can't even use the closed-form version of Fib, because you can't divide or sqrt those integers. The best method is a matrix multiplication version that uses O(log(n)) time and O(log(n)) memory (constant memory relative to the number of integers we need to track, but those integers have an O(log(n)) footprint).

[@Kynatosh]

Ocaml is sometimes used in some embedded systems, and it's paradigm is recursion. But yes, it's normal. I thought this was always tought in courses, especially when you have to find out the memory complexity

[@SILVERF0X13]

I like the max depth idea for cases when recursion just makes the most sense. That's the kind of solution I'd probably overlook myself. I've never worked with super limited systems myself so I usually don't have to worry about things like this all that much when I code, but it's still interesting to learn about optimizations like this.

[@jlc5639]

Literally anyone: Stop using recursion Me: ok.

[@simjans7633]

This is so contextual to the programming language you're using. You could write a compiler that uses continuation passing style functions and you'd have recursive functions that don't use the stack. (This is assuming you've got tail call optimization which all the most used programming languages have)

[@xybersurfer]

@Werse Varsity C# does have it actually, in 64-bit release builds. interesting, i didn't know that about it being in the JS specs

[@miles7267]

I love this. I optimize memory sooooo much. I actually never use recursion, even if I'm programming for a machine with 16 gigs of ram. The Ackerman function is my mortal enemy.

[@richardwelsh7901]

I don’t use recursion because it makes my brain hurt

[@CallousCoder]

Stack overfloooooow Even when you have systems with GB of RAM you still need to tune the kernel. Linux’ default stack size limit is 8MB per process.

[@jonshouse1]

I've been writing C for 30 years, I have never had need to call a function from within itself.

[@softwarelivre2389]

What about the MiniMax algorithm?

[@jonshouse1]

@@softwarelivre2389 I had to google it, not the kind of code i've ever been asked to write. I am not going to pretend I know what I am talking about, but a search for 'non recursive minimax' seemed to find working examples.

[@softwarelivre2389]

@@jonshouse1 you could probably allocate a tree-like structure and work iteratively on it and you'd had a non-recursive minimax, but I've never seen anyone doing it and I don't know if it is feasible.

[@kandlerziv4733]

@@softwarelivre2389 have a stack data structure where you push tree nodes into and pop from. This will allow you to iteratively go over the tree. So you first push the head of the tree, pop it and push it's children, so on and so fourth. If you want you can even scan the tree by height with a queue.

[@softwarelivre2389]

@@kandlerziv4733 never thought of using stacks or queues in a tree, I always saw both stacks and queues as linear, while trees could be branched. But it is a really interesting view and I'll take a look on that soon. Thanks for the info!

[@3Cr15w311]

When I taught CS102 and taught recursion, I did use the factorial example in the textbook but after showing the class how it worked, I mentioned that it was the example in the textbook because of it being a simple example to teach, but in reality, it was something you wouldn't want to write and was a horribly inefficient way to compute it and showed them the simple loop that would likely run much faster. I showed some examples where the complexity of each case down the recursion gets reduced by a factor of 2 where recursion was a better fit than were it only gets reduced by 1 each time.

[@johnsports_iii]

On non-embedded systems, I wonder what going through a lot of stack frames does to your cache hit rate.

[@RedMushroomPanda]

It depends... You would have to study access pattern of the recursive code to see if it has worse cache performance than iterative code. For example: FFT with recursion performs better than purely iterative FFT (mainly due to less cache misses). But as a rule of thumb iterative code tends to have better cache performance.

[@0x1EGEN]

Not sure if it makes much of a difference on cache. The stack will always have a limited memory space regardless. If anything it's branching that would have a bigger impact on performance.

[@SurenEnfiajyan]

I think the memory access pattern in stack is usually (assuming that you mostly access local variables of the current function) cache friendly because after function call or return you just increment or decrement by the size of he stack frame (the memory allocated in stack for local variables when calling a function) which is usually small. So usually it doesn't cause random accesses from distant memory locations.

[@SurenEnfiajyan]

@@RedMushroomPanda If by iterative you don't imply "in place" (ie, you can still use an array as an auxiliary stack) , iterative will be almost certainly faster (and also require less memory) because you only push the data you need. In contrast, before a function call or return a preparation is often needed (such as storing the values of volatile registers or retrieving the values of non volatile registers) and also push/pop additional data (return address, "red zone", etc) which are additional overhead.

[@azophi]

Please explain this to my algorithms professor

[@atomiccoding]

Love its function nature, everything is immutable and variable are treated as state

[@Fractal227]

This is why we should not (for example) move what people call boiler plate from Java, when we keep removing core understanding of what a program does abd how it runs people lose touch with it, there needs to be a balance of what the program does and how "high level" it becomes. I dont program often program, but i often need to teach programmers that what they do affect network traffic and the hardware they work on because they simple lose touch with these things with (for example) python. Very nice video

[@simonmaracine4721]

1:08 You made a mistake there. The function *foo* has actually 5 integers on the stack: a, b, x, y and bar. Parameters are local variables too.

[@leoduboin]

In x86_64, the first four arguments of a function call are actually passed through registers, additional arguments are indeed passed through the stack. Though it is the case for x86_64 I’m not quite sure about other architectures, so feel free to correct me if I’m wrong.

[@phantombeing3015]

He most likely converted code to assembly using gcc.

[@vytah]

@@leoduboin When doing a call, all registers with parameters have to be pushed onto the stack to save, so it ends up the same. Unless the compiler figures out that it can optimize it.

[@leoduboin]

@@vytah oh yes that’s true I forgot about that

[@0x1EGEN]

@@leoduboin Doesn't this depend on the C ABI tho. cdecl is what you're describing but there's other's like Microsoft's fastcall which only use 2 registers.

[@yiuminghuynh5252]

Actually, it doesn't even need to be in embedded systems. Python, for example, has a maximum recursion depth before it errors out. Nice video tho :)

[@Player_X_YT2]

Memoization is the easiest way of avoiding the problem, it turns your O(n^2) Fibonacci function into O(logn), same for memory

[@kamertonaudiophileplayer847]

Certainly you are ready to program Mars mission now.

[@colbyboucher6391]

The irony is that the people who really get recursion are generally working in environments where it's not a good idea.

[@sakul_the_one4821]

0:30 This is exactly why a Sorting Algorythm I copied from the Internet didnt worked on my Calculator!

[@j0code]

never heard of Stackoverflow? that's a safe guard that prevents you from filling your whole RAM :)

[@alastor--radiodemon7556]

20,000 bytes is 20Kilobytes and if you try to say a kilobyte is 1024 bytes ill bite you, thats a kibibyte and im dying on that hill

[@ac3_train3r_blak34]

Very cool! As someone learning about similar topics in college, I love to see how well-explained this was.

[@CJ-ff1xq]

Recursion isn't "bad", it is just slightly less space efficient due to using the call stack. It's useful for understanding certain concepts. If your recursive function is exceeding the max depth then something is wrong with your code... and there are ways to optimise such as memoization.

[@SIStefanov]

To iterate is human. To recurse is divine!

[@TheRythimMan]

In my programming journey i learned about while loops first. Then i learned about for loops and concluded that they were basically just a fancy way of doing while loops. Then i learned about recursion and concluded that it was essentially a clever way of doing for loops. I'm not fancy. I'm not clever. I use while loops for everything (except in situations where the features of the language optimizes the writing or execution of for loops, like with iterables in python).

[@yetanothertroll]

Implement a quicksort without recursion. Maybe use a priority queue?

[@stapler942]

You mean I can't reprogram my coffee maker to compute the two-argument Ackermann function of (4, 2)?

[@theAmazingJunkman]

Oh thank god, I was worried that I wouldn’t be able to use Quicksort any more

[@david2am]

I think it's not that recursion is bad, it's just about if the language we are using support tail recursion optimizations, which reduce the stack calls to one, Ocaml is a good example

[@rothbardfreedom]

But it's always good to remember tail call optimization. You can write a recursive function, but it can be executed without recursive calls.

[@evan_game_dev]

Well, when making a game, even for old PCs running even like Windows 7, it's pretty safe to assume you have infinite memory. I've never programmed for embedded systems though, so I'll take your word for it

[@BeansEnjoyer911]

Couple of things... Sounds like compilers and lowering really are what play in effect for the actual machine code. Also.. I code in functional languages... We don't have for loops. We have to use recursion or folding functions.

[@bartvrhijn]

I use recursion to retry all the missed API calls. It works great

[@marcux83]

ufff

[@colinmaharaj]

I actually wrote a scripting language, and the Fibonacci sequence was one test I wrote for the engine.

[@cornjulio4033]

I hate recursion. It was invented for things: A) computer science teachers want to torture us, and B) crawling your filesystem :D

[@rinodrummer-dev]

I thinks that biggest problem about using recursion it's when is used without knowing the impact on memory it has.

[@NoelmineZockt]

The moment you understand there is Space Complexity and not only Time Complexity is the moment you are better then 90% of Programmers out there in Algo.

[@kulkalkul]

Only complexity exists is trade-off complexity, aka general efficiency. If you are running that function once an hour, or dependent on user input on single machine, if the problem is better suited for recursion, go for it. No? Then don't. Simply as that.

[@NoelmineZockt]

@@kulkalkul Thats just not true. There is Space and Time Complexity. Yes there are certian cases where you have a space-time tradeoff, but most of the time there is just a better way for an Algo where you just have less Time or Space Complexity while maintaining the other Complexity the same.

[@kulkalkul]

@@NoelmineZockt But does finding or impelementing that algo, fine tuning it really worth the effort? That's what I'm talking about, if the tool you use accomplishes its goals, no need to perfect it further, unless that's a business requirement. So what I'm talking about is resource management, if the result is going to take an eternity to produce, it doesn't matter how fast it works. So, as an example, searching function of random website could be 2 seconds, you could create indexes, have clever algorithms to reduce it; but unless you are a search engine, those are probably not worth the time & money invested in. So, in practical terms, everything is real-world resources trade-off. That was what I was trying to say. Other than that, I do of course agree there is space complexity and time complexity, that's undeniable fact of computer science. But most of the time, practical realities do shadow those, so that's why I said "they don't exist", it was metaphorical. :D

[@illilya]

I was lucky enough to TRY to begin computer science in 1995, with the first language being Scheme, which is LISP. Horrible, confusing and ridiculous because it's a functional language that's nothing but recursion. Then, returning to get a CS degree at the same university many years later, I started with Java, learned C very well, and happened to take "comparative programming languages" where I learned LISP, Haskell and COBOL as an elective language. At this point, most CS students dread recursion because it's hard to conceptualize and they NEVER learn a functional language other than C. They have no idea why LISP is called "lots of idiotic silly parenthesis" and how it's a recursive nightmare to conquer. I like the video as a way to help people learn about new limits to consider but with a modern degree, you can learn your assembly AND dabble in ancient functional recursive stuff enough if you elect and this would be obvious. Don't ignore a chance to take that course.

[@johnchinte4774]

tldr; Noob: recursion is scary Student: recursion is so amazing! Expert: recursion is scary Functional Programmer: but tail recursion!

[@MyriadColorsCM]

Was it clickbait? Yes. Have I learned something new? Also yes.