Recursion is maybe one of the most confusing subjects in computer science.
If you get stuck at any point, keep studying the examples and
try to find some more examples until it sticks for you.
The idea here is to create a function that calls itself.
Here is a really basic example in pseudo code.
This code doesn't do anything interesting, but
it shows the main parts of a recursive function.
First of all, a recursive function needs to call itself at some point.
Second, a recursive function needs a base case.
You can think of a recursive function kind of like a while loop in
some regards.
You keep going through some code again and again and
again until you hit some exit condition.
In a recursive function, the base case is like the exit condition.
It let's you know when you need to stop.
Without a nice base case like this,
you could get stuck in something called infinite recursion.
That means your code keeps calling itself and executing again, and again,
and again, and again, and again.
But because you never tell it when to stop, it just keeps going infinitely.
The third thing a recursive function needs to do
is alter the input parameter at some point.
If you aren't altering the input parameter or
giving yourself some condition for
changing every time you iterate, you'll never really know when to stop.
And again, you end up in the same bad place with infinite recursion.
Okay, now we're going to go through an example.
This is the code that we're starting with, and
on this side, I'll write out each major line that we execute.
So we're going to start by calling the function with an input value of 2.
We'll start with this if clause.
Since our input value is 2, and
that's greater than 0, we move on to the else part.
We start by evaluating this before we assign anything to the variable output.
Okay, so input- 1, that's just 2- 1.
So we're going to call this function again, but
instead with an input value of 1 and not 2.
So this is the really confusing part.
Your computer knows that you still haven't finished that initial call
with the input value of 2.
You're just jumping into this part without finishing.
In its temporary memory, it will remember that.
However, it essentially makes a copy of all of this initial code, and
you have to do it again, but this time with an input value of 1.
I put an indent here to signal that we haven't actually finished this initial
call yet, but we're just doing a call inside of that right now.
Okay, so let's do this again.
This time, the input value is 1, but that's still greater than 0, so
we can skip down to the else block.
The same thing happens a second time.
Before we assign anything to output, we have to do this recursive statement.
This time, the input value's 1, so 1- 1 is 0.
And we have to call this recursive block again, but with a value of 0,
instead of 1 or 2.
Again, I indented to indicate that we still haven't forgotten about the fact
that we never solved this and returned anything, but we do need to move on and
start executing again.
All right, let's do this again.
So this time, we actually have something interesting here.
The input value is 0, so we never get to execute any of this else block.
We're just staying up here.
We return 0, so we see it pop up over here.
Now that we've actually returned something from one of our calls,
we can forget about this recursive with an input of 0 and go back to that
recursive with an input of 1 that we were looking at a minute ago.
All right, so we return to having an input of 1.
We evaluated this statement to 0, as I indicated over here.
Again, remember, we called the recursive block, we return 0.
So now we say that this whole thing evaluates to 0, and
we can assign 0 to output, great.
Now that call we did where the input was 1 actually
has a return value here, which is 0.
So now we can kind of forget about this recursive block and
move back to that original call, where our input was 2.
Okay, so back to the original call, this call,
which used to be recursive with an input of 1, got evaluated to 0.
So now we can say 0 is equal to output.
And again, we can return 0, and now even our initial call is done.
Great, so the initial call returns 0.
Recursion can be really confusing, because you start out with just this one
method, but you don't even know how many times you'll end up calling it.
When I'm trying to think through how a recursive function works,
I'll often write out a table or a list of steps like this, so
I can keep track of my values every time I hit the recursive block again.
I always used to think of it like my computer was just going on tangents.
I started with this initial function, and then I kept calling something else,
and doing something else, and doing something else, and
doing something else.
And eventually, I would get back to the thing I was talking about originally.
Remember, your code is going to go through these lines of code in order.
It's never going to assign this output any number
until you've hit the recursive block as many times as you need.
Remember to be really careful when you're writing recursive code.
If your base case doesn't make sense,
you could end up doing infinite recursion.
Let's say we change this base case just a little bit.
All I did was get rid of the less than or equal to and
replaced it with just equal to.
Now this code is going to run fine if we give it an input value of 2 or
1 or 4 or even 1 million.
But if the input value was actually less than 0,
this code's never going to return.
If you start out with -2, you'll skip the if block, and
you'll just keep subtracting 1.
Next time, your input's going to be -3.
Then you'll subtract 1, -4.
Subtract 1, -5, and so forth.
If I use less than though, if my number initially is -2 or
-50 or -1 million, I'll stop as soon as I hit the base case.
Remember to think about all the different input values your recursive
statement could have.
Lastly, if you're really not sure what your recursive block is doing,
you can use print statements wherever necessary.
By printing out intermediate values,
you'll get a sense of exactly what your code is doing at exactly which steps.