Note: NeuralNine might try to teach this later, but for those who want to know why anyone would use recursion, here's why... Hey, as a functional programming lover, Fibonacci and other recursive problems like it don't need to be inefficient. The way that one can maintain efficiency is via tail recursion optimization (TRO) or whatever other hundred different names one can call it. With TRO, the function shouldn't hang on itself by building on the stack. Instead it's cleared because all the edge cases are actually put into the function itself maintaining a linear recursive process instead of a tree recursive process. We would define our function with these edge cases as so def fib(edge1, edge2, n): But Since we don't need to call our edge case with different edges each time, we can actually wrap it in a higher--order function which automatically wraps the edges in our call to it. def fib(n): def fib_wrapped(a, b, n): if n == 1: return edge1 else: newa = a + b newb = a newn = n - 1 return fib_wrapped(a, b, n) return fib_wrapped(1, 0, n) Now when you call this, there's very little inefficiency because the stack is constantly being cleared. In fact, because technically we're changing the state on each call to fib_wrapped, this, while still being recursive is more representative of an iteration and people generally refer to these "wrapped" functions as iter functions because they're doing the real work while the wrapper is just making it easier for the user to use. And notice for a little more usability we can ditch the instantiation of new variables, since we're just using basic arithmetic to calculate the next "iteration" and also have a ternary for better readability. def fib(n): def fib_iter(a,b,n): return a if n == 1 else fib_iter( (a+b), a, (n-1) ) return fib_iter(1, 0, n) Now we have something succinct and in a language where we can separate our parameters with more whitespace(not sure if I can in python) between the parentheses it wouldn't look like clutter but even more beautiful in my opinion. And especially with things like factorial where you might have a basic algorithm but then some random mathematician finds even better edge cases, once you start converting math to code, you can make this recursive process even more (O(n)) fast. This is how functional programming with languages like Haskell still maintain speed with levels of even C or C++ NOTE: you will still need to change the recursion limit because in the python interpreter, no matter how much you've optimized. It's going to think it's kind of like an infinite loop despite the fact that you want a real number and it's not hanging up like a regular recursive process.
@NeuralNine. Please make videos where you are discussing Algorithms and Data Structures for technical interviews in Python. Btw, love the content you publish.
Hey, for the find minimum example, why not just do: def find_min(lst): return min(lst) I mean there is a built is function to find minimum of an iterable, and we use it in the recursive example... But why not just use it directly like above?
And for the first example you could use the inbuilt list method count() : mylist.count(0). The point is not to teach the best way to solve these specific simple problems, but to use them to illustrate a programming concept, such as recursion. We are not using the function for a minimum of an iterable in the recursive example. We are using the function min(x,y) to compare two integers. It so happens that this function is also implemented for iterables but we are not using that functionality.
@@phsopher alright that makes sense. I just thought it was strange to use `min` like that cuz you could just so the whole thing... like if youre using it might as well use it fully. Maybe you could show the example by using if lst[0] > lst[1]: ... else: ... Or smt like that
Hi @NeuralNine, I enjoy learning from your videos. In the second example where you find the minimum number in a list, it would be more elegant to use ternary operators as you did in the first example instead of using the min() function. Here's how I did it: def find_min(lst): min = lst[0] if len(lst) == 1: min = lst[0] if lst[0] < min else min return min min = find_min(lst[1:]) if find_min(lst[1:]) < min else min return min
The best recursion tutorial I have seen, by some margin.
Note: NeuralNine might try to teach this later, but for those who want to know why anyone would use recursion, here's why...
Hey, as a functional programming lover, Fibonacci and other recursive problems like it don't need to be inefficient. The way that one can maintain efficiency is via tail recursion optimization (TRO) or whatever other hundred different names one can call it. With TRO, the function shouldn't hang on itself by building on the stack. Instead it's cleared because all the edge cases are actually put into the function itself maintaining a linear recursive process instead of a tree recursive process. We would define our function with these edge cases as so
def fib(edge1, edge2, n):
But Since we don't need to call our edge case with different edges each time, we can actually wrap it in a higher--order function which automatically wraps the edges in our call to it.
def fib(n):
def fib_wrapped(a, b, n):
if n == 1:
return edge1
else:
newa = a + b
newb = a
newn = n - 1
return fib_wrapped(a, b, n)
return fib_wrapped(1, 0, n)
Now when you call this, there's very little inefficiency because the stack is constantly being cleared. In fact, because technically we're changing the state on each call to fib_wrapped, this, while still being recursive is more representative of an iteration and people generally refer to these "wrapped" functions as iter functions because they're doing the real work while the wrapper is just making it easier for the user to use. And notice for a little more usability we can ditch the instantiation of new variables, since we're just using basic arithmetic to calculate the next "iteration" and also have a ternary for better readability.
def fib(n):
def fib_iter(a,b,n):
return a if n == 1 else fib_iter( (a+b), a, (n-1) )
return fib_iter(1, 0, n)
Now we have something succinct and in a language where we can separate our parameters with more whitespace(not sure if I can in python) between the parentheses it wouldn't look like clutter but even more beautiful in my opinion.
And especially with things like factorial where you might have a basic algorithm but then some random mathematician finds even better edge cases, once you start converting math to code, you can make this recursive process even more (O(n)) fast.
This is how functional programming with languages like Haskell still maintain speed with levels of even C or C++
NOTE: you will still need to change the recursion limit because in the python interpreter, no matter how much you've optimized. It's going to think it's kind of like an infinite loop despite the fact that you want a real number and it's not hanging up like a regular recursive process.
Keep up the good work. Nicely explained.
@NeuralNine. Please make videos where you are discussing Algorithms and Data Structures for technical interviews in Python. Btw, love the content you publish.
Very insightful and on point
Thks for the video. I always wanted to know more about it.
🇧🇷
thanks it's crystal clear! even tho I don't get how it's summing the return values after each call (in recursive n°1)
thank you, this is what i need
thoose are all quite simple recursions im working on a problems with intense tree structures and recursion and i feel completly lost xd
Hey, for the find minimum example, why not just do:
def find_min(lst):
return min(lst)
I mean there is a built is function to find minimum of an iterable, and we use it in the recursive example... But why not just use it directly like above?
And for the first example you could use the inbuilt list method count() : mylist.count(0). The point is not to teach the best way to solve these specific simple problems, but to use them to illustrate a programming concept, such as recursion.
We are not using the function for a minimum of an iterable in the recursive example. We are using the function min(x,y) to compare two integers. It so happens that this function is also implemented for iterables but we are not using that functionality.
@@phsopher alright that makes sense. I just thought it was strange to use `min` like that cuz you could just so the whole thing... like if youre using it might as well use it fully.
Maybe you could show the example by using if lst[0] > lst[1]: ... else: ...
Or smt like that
Hi @NeuralNine, I enjoy learning from your videos.
In the second example where you find the minimum number in a list, it would be more elegant to use ternary operators as you did in the first example instead of using the min() function.
Here's how I did it:
def find_min(lst):
min = lst[0]
if len(lst) == 1:
min = lst[0] if lst[0] < min else min
return min
min = find_min(lst[1:]) if find_min(lst[1:]) < min else min
return min
Plz help me bro how to extract information from pdf with table to csv
"Recursions are awesome!" - said no one
BECAUSE THEY AREN'T
I'd say that
First comment
ok
I hate recursion
Smol brain
I hate I hate recursion
@@phsopher so deep