- In this video, we're going to discuss
one of the most exciting, dangerous,
and most controversial topics
in computer programming: recursion.
So let's talk a little bit about the math part of recursion,
because its name comes
from a mathematical concept called recurrence relationship.
In a nutshell, recursion is a process
in which a function calls itself.
It is based on recurrence relationship
in mathematics as follows.
This is an example of a recurrence relationship,
because in order to generate a series of numbers
using this formula,
you are using the numbers themselves
in order to bootstrap the process.
Here's a specific example.
An, meaning the n-th number in the series,
equals the previous number in the series
plus the one previous to that.
So in order for me to kickstart the process,
I must know the first two values,
namely A0 and A1.
Once I know those two, A2 can be computed
by adding A0 and A1,
so one plus zero is one.
A3 is A2 plus A1, which is zero plus one,
which is one.
A4 is 2 because of the sum of the preceding two,
and so on.
This is a series of numbers generated
by a recurrence relationship.
Let's see what does this mean
when we translate the concept in C.
A recursive function,
simpler than the recurrence relationship before,
looks like this.
The header function
is just like a typical function.
In this case it returns no value, it's void,
and needs one argument for its int parameter num.
Inside the body of the function, called func,
we are calling the function again,
this time I'm adding one to num.
In essence, I'm passing to the function
the value of its parameter plus one,
and then I'm printing the function.
In order to kickstart the process,
I'm going to have to start with some initial value.
In this case, I decided to start it with func(1),
this means I'm first sending one to the function,
num becomes one, then the function calls itself
with num+1, meaning two, and so on,
until the process...
What do you think?
It never ends.
There is nothing here from preventing this to go
on and on forever,
and hence the controversy.
Recursion does something very dangerous to computers.
Each time a function calls itself,
it creates a copy of itself in the computer memory.
If there's nothing to stop this process,
functions will be continue to duplicate themselves
until either the computer memory is exhausted
and your computer will crash,
or if you're lucky,
you're using a modern operating system,
in which there is a safety feature that recognizes
that a function calls itself so many times
that the operating system intervenes
and halts that function.
Let's see what happens in the actual C code.
I created four functions so we can experiment
and see what are the effects
of stopping and non stopping recursion.
First there is a function called numberSeries,
which is a very, very simple function.
All it does, just like the one from the previous example,
it has an argument called k,
it prints k, that's the first step, on line 33,
and line 34, it calls itself with k+1.
There is a warning in line 31,
"DO NOT DO THIS",
I'm only doing this to illustrate the process
and so you can see what happens.
I'm going to run the project.
And notice that this goes,
and for no apparent reason,
it stops at k of a value of 262,000.
So without noticing, within a few milliseconds,
this function calls itself 262,000 times.
It's such a large amount of memory wasted
that the console of Eclipse can't even display
because it's very limited in the amount
of memory it can handle.
Hence my warning.
Do not do this.
I'm going to comment this function out,
so it is being ignore.
And I'm going to uncomment another function,
also recursive,
that does something very different.
It also has a variable k, which is int,
that's being printed each time the function calls itself.
In addition, it has another variable called val.
At each recursive call of the function,
the function sends to itself the value of val
divided by two.
Let's see what this does.
It is hard to notice, again,
because it was so fast,
this time, it stopped at
174,669 recursive calls,
but you can imagine that any number
that you divide by two 174,000 times
eventually it's going to be very close to zero.
So it is not very helpful
to use a recursive function that doesn't stop.
So let me introduce a new concept
which is actually also the concept
covered in the next video,
but this concept is absolutely essential
to the use of recursion.
And I'm gonna use this explanation
as a bridge between this video and the next.
This concept is called an if statement,
a logical decision.
And it's very simple.
Line 47, I am telling the function,
if k is less than 20,
then call the function with the next increased value of k,
and that's it.
The moment k reaches the value of 20,
the recursive call stops.
Let's do that.
I'm going to uncomment the function numberSeriesStops
and run the program.
As you can see,
the program started with k equals one,
at every step of the recursion,
k was added one in line 34,
the function went back to its beginning to line 32,
printed k, and so on.
The function calls itself,
but I told it to stop.
The only way to use recursion is if you can stop it.
Let's see one more time what happens
with the recursive half,
we'll do the same exact thing,
and now you can see.
We started with 1,000,
and then at every recursive call,
that 1,000 get chopped in two
500 to 50 and so on,
and you can see it's very quickly
getting close to zero.
I stopped it after 20 steps.
In the upcoming video, we'll talk much more about
if statements, and we'll see how it can be used
to make decisions of all kinds.