take home Continuation passing style might be the only generic way out there that allows you to transform any code into a form that uses only tail calls hence reducing space complexity of recursive calls from O(n) to O(1)
2:49 to rephrase the given code: factorial(n) = factorial(n, 1) factorial(1, x) = x factorial(n, x) = factorial(n - 1, n * x) as compared to simple: factorial(1) = 1 factorial(n) = n * factorial(n - 1) hahaha, that's basically encoding the looping variables inside the function call itself. this is exaclty what: * i inferred while trying to write binomial coefficients recurcively, and later * an article said about tail rec: "it's effectively using fxn calls to implicitly control the repetitions, rather than using explicit loops"
this is basically like creating an interface - which seems good on outside but in internal inolementation, the structure of the problem at hand is butchered. which is one of the key selling pt of recursion: easily replicate the problem structure. but yeah, other benefits to recursion still exists: its functional & stateless nature.
Tail recursion doesn't work in javascript, in fact trying it on a simple factorial example it would blow up the stack faster than just recursion. Not all languages support this kind of optimisation, or they perform it by default and you just don't realise so it looks like no optimisation happened. I'm sitting here having to reinvent recursion to move it off the stack and onto the heap, I've only had one hour to do it and so far it works better (I can do 10^7 recursions just fine) untill I run out of heap size. It's partially fixable by flagging my nodejs script to run with a bigger heap size but ram is not infinite, I will find a more compact solution eventually.
I kid you not, what you did in 6 minutes is more effective than a 50 minute class I just took. I'm a North American university, btw.
The description, the transformations, the visualization WOW!
Glad I found this gem of a channel, life will be simpler now :)
Thanks a lot for your support! Am very glad the video was helpful :)
Love computer science, there are so many interesting concepts to learn.
Helpful and straight to the point , thanks !
take home
Continuation passing style might be the only generic way out there that allows you to transform any code into a form that uses only tail calls hence reducing space complexity of recursive calls from O(n) to O(1)
2:49 to rephrase the given code:
factorial(n) = factorial(n, 1)
factorial(1, x) = x
factorial(n, x) = factorial(n - 1, n * x)
as compared to simple:
factorial(1) = 1
factorial(n) = n * factorial(n - 1)
hahaha, that's basically encoding the looping variables inside the function call itself.
this is exaclty what:
* i inferred while trying to write binomial coefficients recurcively, and later
* an article said about tail rec: "it's effectively using fxn calls to implicitly control the repetitions, rather than using explicit loops"
this is basically like creating an interface - which seems good on outside but in internal inolementation, the structure of the problem at hand is butchered.
which is one of the key selling pt of recursion: easily replicate the problem structure.
but yeah, other benefits to recursion still exists: its functional & stateless nature.
Excellent. Just what I needed
Glad it is :)
Woo finally video after 1 week 😅
Well yeah, I work full-time, so I upload once a week at the same time (banner has the timings)... Sorry can't upload more atm 😥
Tail recursion doesn't work in javascript, in fact trying it on a simple factorial example it would blow up the stack faster than just recursion. Not all languages support this kind of optimisation, or they perform it by default and you just don't realise so it looks like no optimisation happened.
I'm sitting here having to reinvent recursion to move it off the stack and onto the heap, I've only had one hour to do it and so far it works better (I can do 10^7 recursions just fine) untill I run out of heap size. It's partially fixable by flagging my nodejs script to run with a bigger heap size but ram is not infinite, I will find a more compact solution eventually.
I am very thankful!
Thank you! Glad I could help :)
Thank you so much. Very helpful :)
Glad it was helpful :)
Need multithreading playlist
Nice!
Geek stuff.
Thanks!
✌👍👍