Recursion Simply Explained

In this video we will cover recursion and break this pretty complex concept down in a simple and straight-forward way.

◾◾◾◾◾◾◾◾◾◾◾◾◾◾◾◾◾
📚 Programming Books & Merch 📚

🌐 Social Media & Contact 🌐

Timestamps:
(0:00) Intro
(0:55) Theoretical Basics
(5:43) Example - Counting Zeros
(14:40) Example - Finding Minimum
(18:47) Example - Fibonacci
(24:29) Setting Python Recursion Limit
(27:25) Outro

[marcuswest]

The best recursion tutorial I have seen, by some margin.

[wko_]

Thks for the video. I always wanted to know more about it.

🇧🇷

[mhashmi]

Keep up the good work. Nicely explained.

[SVSingam]

@NeuralNine. Please make videos where you are discussing Algorithms and Data Structures for technical interviews in Python. Btw, love the content you publish.

[crazychicken]

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.

[DENZELLLLLL]

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)

[gge]

thoose are all quite simple recursions im working on a problems with intense tree structures and recursion and i feel completly lost xd

[muhdmairaj]

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?

[kennedywaweru]

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

[saivivek]

Plz help me bro how to extract information from pdf with table to csv

[FilipCodes]

"Recursions are awesome!" - said no one