Recursion in 100 Seconds

Learn how recursion ♾️works in 100 seconds. fireship.io
#compsci #100SecondsOfCode
Install the quiz app 🤓
iOS itunes.apple.com/us/app/fireship/id1462592372?mt=8
Android play.google.com/store/apps/details?id=io.fireship.quizapp
Upgrade to Fireship PRO at fireship.io/pro
Use code lORhwXd2 for 25% off your first payment.
My VS Code Theme
- Atom One Dark
- vscode-icons
- Fira Code Font

[@oleksandrisaryk4728]

To understand recursion you need to understand recursion.

[@thisissyedbasim]

But for that you need to understand recursion which means you should know recursion

[@blocknboom9353]

which results in you having to understand recursion to know recursion

[@CoryJaccino]

Recursion understand to need you recursion understand to.

[@kingofyoutube9318]

That's a stupid saying. If that's true, then nobody would have learned recursion.

[@BurucuGaming06]

@@kingofyoutube9318 uhhh is this serious?

[@IAmAdamTaylor]

I was expecting the start of the video at the end 😔

[@leondu]

that's creative

[@asshivam8117]

kzbin.info/www/bejne/rpawlIqElJqkgZY This is awesome!! Clear all your doubts about Recursion and master it in just 15 minutes!! Watch now!!

[@CarbonaraDaiSuki]

To really understand recursion, you must first understand recursion.

[@metastag]

Our Lord has spoken

[@Ehatntmtntahe]

Wow there was a comment a month before this comment thats very very similar but got less likes.

[@zsczxcanme8956]

Yes but how do I learn Oh it's recurring ok Ok Ok Ok Ok Ok Ok Ok Ok Ok Ok

[@user-kx4xs2xd3k]

and recursive himself

[@asshivam8117]

kzbin.info/www/bejne/rpawlIqElJqkgZY This is awesome!! Clear all your doubts about Recursion and master it in just 15 minutes!! Watch now!!

[@irfanulhoque9348]

Nice video! But you made a mistake in your time complexity analysis. The recursive solution will take O(2^N), not O(N^2). There is a huge difference: O(N^2) means the complexity is bounded by a polynomial function, whereas O(2^N) means the complexity is bounded by an exponential function. These two functions belong to two different classes and their practical implication is quite significant.

[@farhanaditya2647]

nice insight 👍

[@anonymous_4276]

@@farhanaditya2647 you've got an interesting name.

[@MrBarberousse]

The time complexity is actually O(1.618…^n). 1.618… being the golden ratio.

[@bdfornever]

Ironically, the runtime complexity of this approach is the Fibonacci sequence itself

[@magne6049]

@Fireship

[@JoshuaVanAllen]

Might just be me and that i'm further down my career than others, but i'm kind of tired of recursion being explained by using the fib example. I think the community should come up with some real world examples like traversing a tree and why that is important

[@Fireship]

Point taken. I've used recursion in some real-world examples in past videos. It's hard to find minimal examples that don't get bogged down with other implementation details.

[@voicustefan9418]

And its also bad because its insanely unoptimal

[@adastraperlana]

my friend he tried to explain simply in 100 seconds....understand the purpose of the video

[@JoshuaVanAllen]

@@adastraperlana oh I know just every computer science course and every tutorial out there that talks about recursion uses fib as an example. I'm just saying in general I think we need to come up with a better example

[@Phrosen1]

In web design: creating breadcrumbs is a good, simple example for when to use recursion (depending on the CMS, I suppose).

[@aleksandarstevanovic5854]

I love those 100 sec videos, somehow those simple explanations are more clear than overcomplicating

[@asshivam8117]

kzbin.info/www/bejne/rpawlIqElJqkgZY This is awesome!! Clear all your doubts about Recursion and master it in just 15 minutes!! Watch now!!

[@yaroslavlukyanets1007]

O(n^2)? maybe O(2^n). Good video anyway

[@yipyip255]

Yeah, I was going to say the same thing. You can the recursive fib to O(n) with dynamic programming but his implementation in the video is O(2^n)

[@yipyip255]

stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence

[@Panure]

Θ(φ^n)

[@Fireship]

Good call, you'r right.

[@yipyip255]

@@Fireship free tshirt?

[@ericsuzuki8966]

The production of these videos is pure art. Really makes the concepts easy to grasp.

[@FurankieSama]

The dream analogy is too good. I've been searching for a better analogy than factorials. Thank you. I'm really grateful.

[@feelgood_cinematic1919]

I love these in 100 seconds videos, please keep em coming!! 📚

[@vaaski]

damn this 100s of [stuff] series is really good to get a grasp of things, keep it going!

[@asshivam8117]

kzbin.info/www/bejne/rpawlIqElJqkgZY This is awesome!! Clear all your doubts about Recursion and master it in just 15 minutes!! Watch now!!

[@dreamisover9813]

What a coincidence! Writing a recursive method for the Fibonacci sequence was an interview question I once had and I thought it was really good to test recursion knowledge. Great video

[@meco]

The animations in this one were extra complimentary

[@XxDarkCinisterxX]

These short and sweet clips are the reason I subscribed.

[@Fireship]

Glad to hear that! Many more on the way :)

[@asshivam8117]

kzbin.info/www/bejne/rpawlIqElJqkgZY This is awesome!! Clear all your doubts about Recursion and master it in just 15 minutes!! Watch now!!

[@salsamancer]

Recursive functions and binary trees were one of my favorite topics while learning programming. It's really fun to marvel at how the logic works.

[@vaibhavsinghnegi76]

Your video representation, background music, and the way u explain is awesome man👏👍

[@alienxxvi450]

this guy actually makes programming look fun

[@androdeveloper7261]

Finally a 100 second video of actually 100 seconds

[@misraaditya9213]

Recursion as an alternate way to write loops. Thanks for mentioning this early on, because the concept is a big gotcha when people learn functional programming.

[@gabrielbarrantes6946]

It is not... Some problems can only be solved by recursion, recursion is fundamentally different to loops, can certainly be used as loops tho...

[@Dan-zw2sc]

This is basically the MIT recursion lecture but as a summary. Wish I came here first would have saved some time

[@KayVirals]

by the time I settled down to watch the video, he said "thank you for watching"

[@j3y445]

I think that also talking a bit about the tail call recursion would be nice, since for the fibannaci problem it can make things significantly better with a time complexity of O(n) and auxiliary space of O(n).

[@asshivam8117]

kzbin.info/www/bejne/rpawlIqElJqkgZY This is awesome!! Clear all your doubts about Recursion and master it in just 15 minutes!! Watch now!!

[@Mehdital89]

The quality of your explanations has come a long way

[@azatecas]

where's de Memoization video :"(

[@anmolacharya309]

Where is it 😂

[@huebys]

psyched for memoization!

[@stith_pragya]

Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@MB-rc8ie]

Well it depends on the language implementation, in lisp iteration and recursion are the same thing and you don't have to warry about maximum recursion depth

[@Way_Of_The_Light]

Your videos make programming cool 😎

[@kolskytraveller1369]

You forgot to mention that in your example of dream function all recursion calls are tail calls, so the stack would never overflow with optimized compiler because we can omit pushing next ret instruction address and jump instead.

[@Rudxain]

But some languages like JS and Python don't use tail-call elimination, because they want to make debugging stack traces easier. That's why my bigint implementation of the Ackermann function uses explicit TC elimination, by converting the double recursive call, into a single call performed in a conditional loop

[@asshivam8117]

kzbin.info/www/bejne/rpawlIqElJqkgZY This is awesome!! Clear all your doubts about Recursion and master it in just 15 minutes!! Watch now!!

[@5Doum]

Looking forward to part 3: dynamic programming

[@DigitalDiamond1]

As some dude once said; “In order to understand recursion, one must first understand recursion.”

[@augusto256]

Just right now I was struggling with this topic.

[@Omerko]

Great Video!! Quick and Easy explanation..

[@timwhite1783]

it's O(2^n) not O(n^2).

[@legenduzo]

First 100 seconds video I'm seeing on this channel that's really 100 seconds by mathematical standards

[@pawewodarczyk1546]

It's also worth to mention a tail-call optimization. It allows to avoid stack overflow for bigger recursions ;)

[@lucassandre2419]

Unfortunalty not many languages have this optimization ;-;.

[@markuspfeifer8473]

How would that work for monadic recursion?

[@hil449]

i wonder tail-call optimization works under the hood

[@asshivam8117]

kzbin.info/www/bejne/rpawlIqElJqkgZY This is awesome!! Clear all your doubts about Recursion and master it in just 15 minutes!! Watch now!!

[@thetdg]

Great video as usual :)

[@notgiven3971]

has the memoization fireship video been made yet? I can't seem to find the video. I have other videos to reference for memoization but I like these types of videos for a brief rundown if I ever need a quick refresher

[@abhinavrai8430]

Fireship please dont stop ever!

[@InformaticageNJP]

Hi! Cool idea! But be careful, that implementation of recursive fib is not n^2 and not even 2^n but it's phi^n. With memorization you can make it linear and with matrix powers you can make it logarithmic.

[@SirM0linarius]

But only in time complexity. regarding to memory complexity your suggested algorithms are actually worse - which is a tradeoff often neglected. Still I would prefer your methods :)

[@marcogoncalves1073]

@@SirM0linarius Memoization is O(1) in memory complexity, O(n) time complexity. (You can save an array of O(N) elements if you want, but that's only helpful if you want to calculate the numbers multiple times)

[@Vaaaaadim]

@@marcogoncalves1073 Other way around.

[@marcogoncalves1073]

@@Vaaaaadim What do you mean? You literally only keep in memory the last 2 elements that were calculated.

[@Vaaaaadim]

@@marcogoncalves1073 As I understand, memoization is a top-down approach, and would cache results of function calls. Dynamic programming, is a bottom-up approach. The approach to computing fibonnaci numbers involving the continual update of a pair of fibonnaci numbers... is a bottom-up approach and hence dynamic programming rather than memoization.

[@whitenoisefocus7962]

I love these videos too. Who did the music for this? 🔥🛸

[@Name-is2bp]

did you upload the video on memorization you mentioned? i can't find it.

[@jst8922]

No, he did not. Here is next best thing with simple explanation Recursion, the Fibonacci Sequence and Memoization || Python Tutorial || Learn Python Programming kzbin.info/www/bejne/h5yTq4iQjJKIla8

[@kajalmishra6895]

Waiting for your next video on memoization...

[@aiSage48]

still waiting...

[@Vermilicious]

Recursion might be a confusing topic to some. It's really just about repetition. It doesn't really come up as a solution very often, but it happens. You just get used to recognizing situations where it makes a lot of sense. It's not the only way to solve such problems, and it's usually not associated with good performance, but it's elegant.

[@markuspfeifer8473]

I usually find a recursive solution almost instantly and then implement it iteratively or with higher order collection methods because of efficiency. Once you get the hang of it, recursion is conceptually really easier

[@sangchoo1201]

well, a nice way to calculate Fibonacci numbers is, using power of matrix. that has a complexity of O(logN)

[@MercyFromOverwatch2]

Jeff is still my favourite tech youtuber

[@-0-__-0-]

Im learning a lot in 100 seconds.

[@Phantom_Blox]

Good, now we have 10 functions and lets do recursion with those!

[@ServantOfLordKrishna.]

I'm more confused 🥳🥳really nice video

Memoization?

[@ambarmutha8504]

The implementation in the video has exponential complexity and not O(N^2). Correct me if I am wrong.

[@misode]

Yeah you're right. The time complexity is O(2^N)

[@Tlcunha81]

Oh yes!!! Dynamic programming

[@TheMaxZakh]

honestly I could use a 1000 second video on this topic

[@gamerkaue88]

I dare you to explain monads in 100 seconds.

[@raknjarasoa]

Great!

[@scottbisco6793]

As someone who is currently in a year index of 2023, I agree with this.

[@dhruvsaraswat9776]

I just noticed, the logo which you use is really similar to the logo of freecodecamp.org, is this KZbin channel associated with freecodecamp in any way ? I loved the simple explanation provided in this video ! 👍

[@PiLaunchpad]

Him: "index 2023" Me: WHAT how did he know?!

[@anupamdahal7029]

I have learnt a lot of new things that I have never worked with from your videos, like AWS, nginx, kubernetes, graphQL(and other dbs), typescript to name a few. One thing that I don't understand is how they work together. I would really love to see a video where you design a mock system using all of these (and possibly more) and explain each of their roles and why you chose it (kinda like your reverse-cloud migration video using raspberry pi). Whenever I think of a software architecture I think of them as several layers that interact with each other. However, I am unable to assign which layer what belongs to by watching a stand alone tutorial about a single tool. Btw, I am a college senior pursuing CS major and I love your content. Thanks for all the awesome contents.

[@boheem3451]

I didn't understand the background, invisible stuff - the stuff that was happening on the stack. That's why recursion looks so strange. It's difficult to visualize what you don't know about.

[@ravikeshkumar4950]

I think, there is one mistake in function you've written for fib sequence, you should return targetIndex in the base case not 1.

[@hyperspeed1313]

Still waiting for that memoization video

[@InspektorDreyfus]

Actually you want to avoid recursion. The point is, you can have recursion without noticing it, when several functions call each other in a circle. And if there is a stopping condition, it is hard to tell what exactly the stopping condition is.

[@asshivam8117]

kzbin.info/www/bejne/rpawlIqElJqkgZY This is awesome!! Clear all your doubts about Recursion and master it in just 15 minutes!! Watch now!!

[@diadetediotedio6918]

Nah, recursion is fine for various problems. Normally parsers and compillers use them a lot

[@Wasim17O1]

Recursion is like Newton's first law of motion

[@eshaan7_]

brooo...where's the memoization video

[@yersonlasso9754]

I can't believe there is not a link to this video in the description

[@MaxDiscere]

how's the background song called?

[@Donzw]

Does the memoization video still exist, i cant find it anywhere. Might be nice to put a link to videos you mention in the description.

[@crackwitz]

Awww shieeeet 0:30 wokies, being NPCs, can't dream. 💕 it!

[@totalmonkeyspeed260]

Did the memoization happen?

[@LowLevelLearning]

Ayyy niceuuu

[@MoguMogu818]

Every time I am told to do recursion, I shrivel up because how does something call itself. Wouldn't it go into a loop? Wouldn't n never approach the end of the array and instead approach infinity because it just keeps looking again and again. I am so dumb, but idk how I've made it this far by avoiding recursion.

[@monika.alt197]

Nice

[@JaviScript]

This is the best channel on KZbin. Like, ever.

[@rafadydkiemmacha7543]

No u

[@StrangeIndeed]

You know what they say, to understand recursion, you first need to understand that the real recursion were the friends we made along the way

[@k1ngjulien_]

I feel like recursion is not a topic which can be properly explained in just 100s. array map and reduce were good, but this is much more complex

[@shadowsbane171091]

Recursion is when a function calls itself. there that didn't even take more than 5 sec. jibes aside, recursion is a very simple concept, but its hard for people to get their heads arround it. like some people coming in from procedural languages have a really bad time understanding JS's async code, i.e Callbacks and Promises. Thankfully Async Await is pretty much bridged that gap.

[@Heeter]

I can't find the memoization video!

[@beinyourguard]

This channel makes me realize how shit I am on JS.

[@Exiide89]

It is programming equivalent of Inception.

[@kklowd]

I'm still waiting for the memoization video 2 years later

[@andyram27]

I get that these videos are made for newcomers but there are a lot of errors (and sometimes antipatterns) featured. Naive recursive Fibonacci is exponential time (2^n) not quadratic time (n^2). People think you're an authority on this stuff. Please fix it.

[@monumento.f.501]

hi is an authority on vaporwave.

[@user-vs3uu7mk5f]

where is the memorization video

[@vishwajithbarad]

Where is Memoization video. Please upload.

[@lodewykk]

Huh. Did that memoisation video ever get made?

[@devikakrishna4464]

0:14 me a cpp and c coder:thats a problem of the future

[@devikakrishna4464]

Use void functions!

[@dopetag]

Can someone explain: const sequence = [0n, 1n]; what do 0n and 1n mean?

[@kebien6020]

Those are bigint literals

[@tomiivaswort6921]

After my confirmation, I will buy a gaming pc. Then I'm going to make a program with a recursive function and wait until it used up all 16GB of RAM

[@randomeone100]

1:20 TC will be 2^n if I am not wrong

[@rahulsingh7508]

Is recursion helpful in solving majority of the chess problems?

[@ikezedev]

This is lovely...I already shared to twitter 🔥

[@ZipplyZane]

Oh. I saw that CS in the thumbnail and misread it as CSS. I was wondering how CSS could be recursive.

[@TheUntitledworks]

I get stuck on a recursive loop when I start thinking about lunch. How do I return out of the loop???

[@can_pacis]

you don't, you eat lunch

[@astralchan]

1:20 No, this is exponential time, not quadratic time. O(2^n) -- NOT O(n^2)

[@genta3424]

cool

[@welltypedwitch]

Well... as someone, who actually likes Haskell, I don't really like this explaination. Recursion is not only useful for trees and Fibonacci, but it is a general alternative to loops, that can be a lot cleaner and more functional (because it avoids any unnecessary mutation). When learning Haskell, a good exercise is to try and implement most standard library functions. Because in Haskell everything is immutable, you will have to use recursion a lot. After a while you really get into that mindset and now even my TS/JS code primarily uses recursion instead of ugly loops.

[@mona.supremacy]

Thank you for pointing out the way to replace loops with recursion in JS. I have to try, definitely

[@hamodeyDooba]

example requestAnimationFrame

[@gerritweiermann79]

Oh no, memoization is still not out :( (if I searched correctly)

[@hus2809]

There is an error in your code: When the target_index is less than or equal to 1 it should return target_index and not 1. That is because if the target_index is 0 it should return 0, where in you code it would return 1.

[@avinash-dhumal]

Like an Inception...😜😅

[@Volcott]

What a missed opportunity to put at the end "If you want to learn more about recursion, please see Recursion in 100 seconds" :c