Recursion
google gets it
What is Recursion?
The simplest way to think of recursion is a function that calls itself until the problem is solved. This usually involves what is referred to as a "base case." A base case is the point in which the problem is solved at.
Recursion is hard, I struggled
Do not feel bad if you are finding recursion hard. We will try to go over as much as we can to make this as clear as possible. I also promise you, once you understand it, it will become trivial. Its such a weird feeling...
Unfortunately, before we can ever proceed to anything more awesome, we have to know and understand recursion.
The simplest example
// I always hated this example, but I think its the simplest
function foo(n: number): number {
// Base Case
if (n === 1) {
return 1;
}
// We shall Recurse!
return n + foo(n - 1);
}
Lets draw what is happening here
- don't forget to describe the 2 steps to recursion
Questions?
I want to make sure we are clear here first. I want to make sure we are clear here first, as I said, the rest of this class is going to be heavy on recursion.
Its ok if you don't quite get it yet, this example never helped me. But it is also the simplest way to display recursion.
The biggest mistake of recursion
Don't put it into the 2 steps.
- Base Case
- Recurse
Lets work through a problem that helped me understand recursion
I think its best to do something that we can understand, together. (to the whiteboard) (program a bit and white board a bit)
Hopefully you at least somewhat understand recursion better
When do I use recursion
- its not able to be done via for loop