@@911Salvagea surface level understanding that helped me complete coursework is different than feeling connected to the underlying principle! everyone processes info differently my friend
you know what man, you put so much effort into your videos with the edits and research and clear explanations, you deserve more views. im sure it's just a matter of time until you blow up, your vids are very good fr
One problem with this approach, aside from a potential stack overflow as others have mentioned, could be: 1. _Use a high-level language_ 2. _Enter very large number_ 3. _Program hits max recursion depth or overflows stack_
A function is called with three steps: 1. Push to the stack where to return after the function 2. Go to the function's beginning 3. When the function returns, it basically takes the return location out of the stack and goes to it PS if you have a recursive function with only one place of it calling itself, then you can always turn it into a loop. So with a few tricks you can convert the recursive version of Fibonacci to the loop version, just if you make it with linear complexity
I would say avoid recursion like the plague, it can cause stack overflows and it's also slow since you're making so many function calls which depend on each other and making many stack frames, only use it if its better than alternatives for example when iterating trees.
A lot of functional languages have tail-call-optimization, so it won't continuously create stack frames for each recursive call. JS was supposed to have this years ago, but not sure it ever got implemented.
but you can always solve the problem iteratively, just create a stack and push what you need there. However, there are langs that do this for you, so using recursion instead of using iteration ends up being the same thing in certain languages
@@prathamrathore776 take an example about the fibonacci number problem. This problem itself actually has 3 ways to solve: recursive, recursive with memoizaiton and dynamic programming approach. And that DP approach is how we solve that problem in an iterative way. I've solved a lot of these problem and the recursive solution is always the easiest solution to come up with
Wow, even phd professors in our colleges don’t have the talent to teach us like that..!! I already subscribed because i am impressed by your skills, looking forward to your videos giving us free knowledge, insights and skills..
func recursionIsDangerous(n): if n < 0: return -1 # an error code if n < 2: return 1 # let's say n = 5 p = n # p = 5 product = n # product = 5 count = 0 while (p > 2): # 1 and 0 are done p -= 1 # p becomes 4 - 3 - 2 count += 1 product *= p # product is (5*4), (20*3), and (60*2) if count > 1000: # always break an out-of-control self-running function print("runaway loop detected in recursionIsDangerous()") break return product # returns 120
I had a professor who said, "if you don't have a conditional in your recursive function, it's probably a bug." You have to be sure you write the function properly. n * factorial(n - 1) vs factorial(n - 1) * n can have wildly different run times, depending on the language and compiler/interpreter.
A downside to consider is that, in contrast to a loop, recursion does increase the stacksize of the program and may cause stackoverflow errors if the recursive chain becomes too large. Im addition recursive functions are often harder to read and debug, so in general its better to just use a loop if possible.
My understanding of any loop or recursive piece of code is that you must always provide the program a way to escape out of the loop. That's the only rule.
This is still very mind-f***** , there's gotta be a good understandable way to explain this strange mechanic of a function that calls itself... 🤔 I'll wanna see a video with an explaination like that, both intuitively and technically. (My English is terrible, hope that i made myself clear... 😅)
There are very few real life scenarios I've had where recursion is better than loops though of course there are exceptions. Usually the examples that are used to explain it would run faster without it.
Yep that is indeed recursion, but I think that some people may still be confused because they don't know that all the function calls are stored on a stack and that's why it can then go back and recursively solve all of the function calls right back until the original function call...
I just studied it, but I don't understand why I would ever use it. For small numbers like 5 the difference is unnoticeable, but for bigger ones recursion takes way more time and free space than any loop.
hey, clarifying your question, indeed this happens in the most langs, i guess. However, certain langs have something called tail-call optimization. I recommend you search this term for more informations if you want it. And keep in mind there's not a situation where you are obligated to use recursions, you can always create a stack by yourself and push just you need, instead stacking an entire function in the heap on each call
It's just another option to have. Certain problems just lend themselves to the recursive solutions being much simpler. For example, many tree traversal algorithms are _way_ easier to implement recursively and also easier to read.
@@zico6892in this case it's possible and it will keep multiplying it by itself subtracted by one and stopped because of stack overflow, this is why I'd like to use
Please don't use n === x when doing recursion or any test that measures an upper or lower bound. Who knows if that number suddenly increase or decreases past your limiting factor.
One thing i never understood is how the input number in this case for example decreases after each call, like if i input 5 how does calling itself replaces 5 with 4 without needing another input (i know it returns n-1 but still, usually a function doesnt save previous input), i may sound dumb right now.
Asymptotically, recursive solutions are usually the same (except for occasional extra space used on the call stack). Practically, it can be a tad slower in some cases, although I don’t think I’ve ever seen 5-10x slower, at least for anything taking a meaningful amount of time. This just comes from the extra complexity of a function call vs a loop, there’s just more assembly instructions generated. That said, compilers are really smart. A well optimized compiler will oftentimes produce the exact same output or nearly the exact same output for many simpler recursive solutions such as those using tail recursion.
This realy depends. Condionals like the if in the clip can realy slow down compared to no conditions like in the iterative solution because of pipelining...but true, a good compiler care about this
Nice explanation but the two codes work different: The first one is fine, even if it shouldn't be funny putting a negative number there😂 (but I know it was just an example so ok) The second one instead doesn't work even where the factorial is defined. It should be: if (n===0) { return 1 } ecc.
Time complexity is the same. Although recursion oftentimes has a worse space complexity due to space taken on the call stack (but this can in many cases be mitigated with techniques like tail recursion).
I'm pretty sure this is the exact same explanation you get from any programming related class. You might need a few more example cases to understand it better. Plus, some understanding of what it does to the 'stack' and why it's not always the best idea.
This is not true. The proof that any recursive function can be written iteratively is actually fairly straightforward. Essentially you just implement a call stack manually and process it iteratively. The ackermann function is not primitive recursive. This means it cannot be implemented with only for loops of predetermined size. However, using constructs of “complete” modern languages it can be implemented iteratively (although it is way more complicated than doing it recursively).
As a "curly brace on the next line" guy I'm saddened by this. I get recursion. I don't get this curly brace penchant. Yeah, I've heard the "it's more readable" and "it saves real estate". No on the first and not nearly enough to make a difference (change the font size) on the second.
It's a language convention. JS uses this, C++/C# uses curly braces on new lines, python uses indentation (the latter case, however, is not a convention but a strict language rule).
Be careful with recursions, they have the capability of dropping your server if badly written since some recursions can become quite complex in real world and if not well thought through or tested, will 100% place your job on the line when you drop an entire companies operations.
Nope. You can branch recursion calls, unlike the loop. You can call 4 recursions in one function, for example, to find a shortest path on a rectangular plane with barriers.
Dude I’ve struggled with recursion since I was introduced to it a year ago and this short made more sense than my college course. Much appreciated !
Watch Kunal kushwaha recursion series. Very clear explanation
this video didn't help you learn recursion though.
You need that much time to grasp such a trivial basic concept? 😮
Same experience here. Recursion is pretty cool.
@@911Salvagea surface level understanding that helped me complete coursework is different than feeling connected to the underlying principle! everyone processes info differently my friend
you know what man, you put so much effort into your videos with the edits and research and clear explanations, you deserve more views. im sure it's just a matter of time until you blow up, your vids are very good fr
Thanks! Glad you enjoy them 😀
One problem with this approach, aside from a potential stack overflow as others have mentioned, could be:
1. _Use a high-level language_
2. _Enter very large number_
3. _Program hits max recursion depth or overflows stack_
youll most likely reach 64 bit integer limit before then
@@chickenbobbobba A lot of languages cap max recursion depth a lot lower.
@@Zandercraft im sure it can handle 20 recursion layers. thats not a lot, comparatively.
You can do recursion in assembly easily. I don't understand the first point
@@maxencegitton377 A lot of high-level languages have an artificially low max recursion depth (E.g., Python).
A function is called with three steps:
1. Push to the stack where to return after the function
2. Go to the function's beginning
3. When the function returns, it basically takes the return location out of the stack and goes to it
PS if you have a recursive function with only one place of it calling itself, then you can always turn it into a loop. So with a few tricks you can convert the recursive version of Fibonacci to the loop version, just if you make it with linear complexity
I would say avoid recursion like the plague, it can cause stack overflows and it's also slow since you're making so many function calls which depend on each other and making many stack frames, only use it if its better than alternatives for example when iterating trees.
Finally somebody who coded his own function in asm. But recursion makes the code cleaner, and more readable in my opinion.
Agree, it should only be used if there's an intuitive sub-problem and an unintuitive/impossible iterative alternative
It makes the coder look smart though.
A lot of functional languages have tail-call-optimization, so it won't continuously create stack frames for each recursive call. JS was supposed to have this years ago, but not sure it ever got implemented.
Use a real language that has tail call optimization.
You forgot about the edge case when n == 0. Because you can send 0 in the first call 0! = 1
And negatives I think, you should make the return statement not work after factoring 0, such as making a Boolean if trigger
It’s not an edge case, you just set the base case to 0! = 1, then 1! = 1 * 0! = 1
@@armandcaringi is correct. Just replace the 1 with a 0 and you're good to go.
I think the guy is just talking about recursion. The factorial is an example, not the focus
@armandcaringi what do you mean, he did forget 0! in his explanation.
This is your best video so far.
Wow, what a clean explanation, good work man 💯
Recursion make life easier. But only solve problem with recursion if you cant find a way to do it in an iterative way
sometimes the recursive way is even more efficient than the iterative
but you can always solve the problem iteratively, just create a stack and push what you need there. However, there are langs that do this for you, so using recursion instead of using iteration ends up being the same thing in certain languages
@khelix5017 this is literally never the case, function calls are slower than iteration
how the hell can you do backtracking problems iteratively
@@prathamrathore776 take an example about the fibonacci number problem. This problem itself actually has 3 ways to solve: recursive, recursive with memoizaiton and dynamic programming approach. And that DP approach is how we solve that problem in an iterative way. I've solved a lot of these problem and the recursive solution is always the easiest solution to come up with
One improvement in this cse assuming this is in the context of a interpreted language: make the base case n
Wow... You just help me get that right easily. Thanks!
U just a earned subscriber , I used to struggle understanding recursion thanks for this animations and explanation
Thanks alot was struggling with this
Very clear and concise explanation! Keep up the good work!
Used this method in my Python practical, multipled N*I in a for loop and it worked
Thank you this was very neat
Man tqsm, always been confused with recursion u made it very clear and simple. You earned a subcriber✌️👍
Wow, even phd professors in our colleges don’t have the talent to teach us like that..!! I already subscribed because i am impressed by your skills, looking forward to your videos giving us free knowledge, insights and skills..
func recursionIsDangerous(n):
if n < 0:
return -1 # an error code
if n < 2:
return 1
# let's say n = 5
p = n # p = 5
product = n # product = 5
count = 0
while (p > 2):
# 1 and 0 are done
p -= 1 # p becomes 4 - 3 - 2
count += 1
product *= p # product is (5*4), (20*3), and (60*2)
if count > 1000:
# always break an out-of-control self-running function
print("runaway loop detected in recursionIsDangerous()")
break
return product # returns 120
subbed. I think you can use 2 as the base case.
I had a professor who said, "if you don't have a conditional in your recursive function, it's probably a bug."
You have to be sure you write the function properly.
n * factorial(n - 1) vs factorial(n - 1) * n can have wildly different run times, depending on the language and compiler/interpreter.
Best explanation I’ve seen
A downside to consider is that, in contrast to a loop, recursion does increase the stacksize of the program and may cause stackoverflow errors if the recursive chain becomes too large. Im addition recursive functions are often harder to read and debug, so in general its better to just use a loop if possible.
This the best explanation
My understanding of any loop or recursive piece of code is that you must always provide the program a way to escape out of the loop. That's the only rule.
explained perfectly!
And then someone tries factorial(0) or less and hits an infinite loop. There's multiple ways to better handle this. For instance I usually do
and also i think instead of clearing old output it just stacks over so if u make really big number i think you can get stack overflow
My teacher couldn't teach it in 40 min and you did it in 60 second
This is still very mind-f***** ,
there's gotta be a good understandable way to explain this strange mechanic of a function that calls itself...
🤔
I'll wanna see a video with an explaination like that, both intuitively and technically.
(My English is terrible, hope that i made myself clear... 😅)
You earned a subscriber.
Bro is teaching FP in JS. This is basically how a do while loop works for people who take a more imperative programming approach
Bro, thx for the tips. As a person that is bad at math. This really help. Thx. Make more math content. 😅
bro rizzed in 60 secs(including me ) subscribing
There are very few real life scenarios I've had where recursion is better than loops though of course there are exceptions.
Usually the examples that are used to explain it would run faster without it.
Just for good looks:
const factorial = (n) => (n===1 ? 1 : factorial(n-1))
Do you think negative numbers have factorials
Thank you.
just do
function factorial(n):
return (n
good explanation
Yep that is indeed recursion, but I think that some people may still be confused because they don't know that all the function calls are stored on a stack and that's why it can then go back and recursively solve all of the function calls right back until the original function call...
Return 1?
Holy crap. I can understand it so easily. Thanks 😂
His base case fails when someone puts 0 in or a negative number in assuming the type is signed.
immediately subscribed
return n == 1 and n or n * factorial(n-1)
Smooth got 1 subscriber ❤
Base case, aka a guard clause.
I just studied it, but I don't understand why I would ever use it.
For small numbers like 5 the difference is unnoticeable, but for bigger ones recursion takes way more time and free space than any loop.
hey, clarifying your question, indeed this happens in the most langs, i guess. However, certain langs have something called tail-call optimization. I recommend you search this term for more informations if you want it. And keep in mind there's not a situation where you are obligated to use recursions, you can always create a stack by yourself and push just you need, instead stacking an entire function in the heap on each call
You missed an opportunity to make this shorts video loop in a seemingly recursive manner!
What if n < 1 ? You have to put every cases
function factorial(n) {
return n * ((n == 0) ? 1 : factorial(n - 1));
}
no one has ever explained recursion this simple
I am a beginner why would we use recursion over a loop
It's just another option to have. Certain problems just lend themselves to the recursive solutions being much simpler. For example, many tree traversal algorithms are _way_ easier to implement recursively and also easier to read.
did i get myselt mixed up in a js course? man im not learning that abomination any time soon
It should be (n
I'm subscribing now.
20 seconds: 1) have an initial function, 2) the recursive step that breaks the problem down and 3)terminating condition. There
I wounder what would happen if I put -1 in the function :)
That’s the finest thing u don’t
-1! Is not a thing
@@zico6892in this case it's possible and it will keep multiplying it by itself subtracted by one and stopped because of stack overflow, this is why I'd like to use
broo respect
Try factorial(0) or any negative number
why the need for THREE equal signs?
to prevent type conversion
no clue what that is @@_.luminosity._ but ok
Why did he put a triple = sign instead of just double = at the base case?
recursion limit: hello
Please, check "impossible" cases, like n being zero or a negative number. Check if n < 2 in this case
Fun fact, 0! Is 1. But yeah definitely check for negatives
Also it can be negative, just not a negative integer
Please don't use n === x when doing recursion or any test that measures an upper or lower bound. Who knows if that number suddenly increase or decreases past your limiting factor.
BUG! What if you try factorial(-1)? It might eventually finish if you're usuing an integer type that 'rolls over' once it gets large enough...
One thing i never understood is how the input number in this case for example decreases after each call, like if i input 5 how does calling itself replaces 5 with 4 without needing another input (i know it returns n-1 but still, usually a function doesnt save previous input), i may sound dumb right now.
Whats the purpose of recursion for?
This is the easiest example of recursion
Making few projects in C I've seen that often recursion is 5 to 10x slower than iteration, but why?
Asymptotically, recursive solutions are usually the same (except for occasional extra space used on the call stack). Practically, it can be a tad slower in some cases, although I don’t think I’ve ever seen 5-10x slower, at least for anything taking a meaningful amount of time. This just comes from the extra complexity of a function call vs a loop, there’s just more assembly instructions generated.
That said, compilers are really smart. A well optimized compiler will oftentimes produce the exact same output or nearly the exact same output for many simpler recursive solutions such as those using tail recursion.
This realy depends. Condionals like the if in the clip can realy slow down compared to no conditions like in the iterative solution because of pipelining...but true, a good compiler care about this
Nice explanation but the two codes work different:
The first one is fine, even if it shouldn't be funny putting a negative number there😂 (but I know it was just an example so ok)
The second one instead doesn't work even where the factorial is defined.
It should be:
if (n===0) {
return 1
} ecc.
Wow. im wandering if the time complexity is the same as a simple loop with if condition.
Time complexity is the same. Although recursion oftentimes has a worse space complexity due to space taken on the call stack (but this can in many cases be mitigated with techniques like tail recursion).
@@ConnerArdman oh , i get it now . thx
Is "i =+ 1" also recursive?
Technically, the base case should be n == 0 with 0! being 1 as well.
I'm pretty sure this is the exact same explanation you get from any programming related class. You might need a few more example cases to understand it better. Plus, some understanding of what it does to the 'stack' and why it's not always the best idea.
I like it!
I get that it's just an example but this would break if you input any non positive number or any non integer value
What if n = 0 , this code will throw segmentation fault due to stack overflow.
Just a question. Why use recursion instead of using a loop?
to implement divide and conquer philosophy...
generaly, if u can, avoid recurtif function.... it's lot of lot slower than for-loop
When i learned recursion it was easier to me to write recursive functions than normal lmao
Conner loves JavaScript. 😮
I literally cant wrap my head around recursive functions
how did i understand this in just under a minute
Fun fact, there are some problems that can only be solved recursively, and not iteratively. Ackerman's function is one example.
This is not true. The proof that any recursive function can be written iteratively is actually fairly straightforward. Essentially you just implement a call stack manually and process it iteratively.
The ackermann function is not primitive recursive. This means it cannot be implemented with only for loops of predetermined size. However, using constructs of “complete” modern languages it can be implemented iteratively (although it is way more complicated than doing it recursively).
@@ConnerArdman today I learned, thanks!
Oooo…high risk recursion! What if you pass a decimal or a negative number in your factorial function?
function factorial(n) {
return (n == 1) ? n : factorial(n-1);
}
factorial(0)
What what are the three === because i usually do == . Or this is not the language i think it is?
=== means strict equals, which checks for value and type. For this example i would use == instead, since n should always be a number.
it is because every recursive function must to have an itself call and a condition to stop.
Got this reel to late, A month after my AP CSA exam😢😢😢
I this case the for loop is much fast because of the condition
Its better to use for loop for that but yeah.
if n == 0 would be more accurate
Fair enough, been a minute since I took a math class lol 😅
@@ConnerArdmangreat video either way
Well you'd return 0 and the return value would be 0 * n! which is wrong
@@nytr No 0! = 1. Thats what he meant. Theoreticaly the function needs to be called until 0! is the last factorial.
@@coredeadman5980 yeah you're right, sorry :D
As a "curly brace on the next line" guy I'm saddened by this. I get recursion. I don't get this curly brace penchant. Yeah, I've heard the "it's more readable" and "it saves real estate". No on the first and not nearly enough to make a difference (change the font size) on the second.
It's a language convention. JS uses this, C++/C# uses curly braces on new lines, python uses indentation (the latter case, however, is not a convention but a strict language rule).
Be careful with recursions, they have the capability of dropping your server if badly written since some recursions can become quite complex in real world and if not well thought through or tested, will 100% place your job on the line when you drop an entire companies operations.
So it’s just a different way to loop? And can’t I just use a while/do loop instead or how wrong am I?
Nope. You can branch recursion calls, unlike the loop. You can call 4 recursions in one function, for example, to find a shortest path on a rectangular plane with barriers.
This is some dangerous code here, should be checking n
is it java ?
That kinda easy and useful but I can't see myself using it in other things then math
What's factorial(-6) gonna give me?
Why three equal signs