- We're going to wrap up the discussion of functions
with the topic of recursion.
We have seen the topic before,
and now it's a good time to revisit it.
We call a recursive process
those processes in which a function calls itself.
We are going to stay true to tradition
in programming and computer science classes,
and we are going to look at the Fibonacci series
as an example of a recursive computation.
The Fibonacci series is a great example
because it is powerful,
it is simple, and it has
a lot of information that we need to talk about.
So, the Fibonacci series in a nutshell
is a series such that one element in the series
equals to the sum of the preceding two.
That's it.
The only ones that are different are the first two
because the first and the second
don't have two preceding ones.
So, we need to treat them specially.
So, the Fibonacci series received an index, n,
and based on that index
computes the series.
If n is zero,
which is the first element in the series,
the function will return zero
because there's nothing else to compute
so by definition, we define
that the zeroth element in the Fibonacci series is zero,
and the first element, so number one, is one.
Other than that, we can now use the formula
that's listed in the return statement.
We are going to return the sum
of the previous two.
So, in this case, it would be one and zero.
If you look at the recursive process,
it occurs when you see the name of the function
being referred to inside the function definition.
So what happens here is that
when I say return Fibonacci(n-1),
the function doesn't even go to the Fibonacci(n-2).
It goes back to the top,
and instead of n, it now uses n-1.
So obviously, n is coming from somewhere else.
If you look for the down under main,
the command printf, it prints the result
of computing the Fibonacci,
in this case for number 10.
So, if 10 is being passed onto
the Fibonacci header function,
then it is not zero, it is not one,
therefore, Fibonacci(n-1), which is nine,
it's now being sent to the function.
Nine, again, it's not zero,
it's not one, and it becomes eight,
it becomes seven, it becomes six,
five, four, three, two,
now it becomes one.
If it's one, the function quits
and now it goes to the other Fibonacci(n-2).
So we have this, sort of, a yo-yo movement
where we start with Fibonacci(n-1)
and there's a loop that happens
between those Fibonacci(n-1)
and the header of the function.
When that loop can no longer work,
it switches for one cycle to Fibonacci(n-2),
but then immediately switches back
to Fibonacci header and Fibonacci(n-1).
So that back and forth
until everything is exhausted.
Let's take a look at the code
and see how this works.
Notice, first of all, that there is no main yet.
It is all the way at the bottom.
I just did that to show you
that it really doesn't matter where you put main,
it's more of a convention, habit,
whichever you want to call it.
It is a function.
Main is just a function like any other function.
The only thing that's special about it
is when the compiler creates executable code,
it is expected for one function to exist
that is called main.
And this is the function where execution starts.
Other than that, it can be anywhere.
Now, what we did with that,
notice there's no prototypes here
because the two functions,
Fibonacci and the one that calls the series,
are being defined in the order
that they're being used.
So, there is no problem of us needing to use
a function before it has been defined.
Let's go to main and see how it all starts.
So, I have a function called generateFibonacci,
which I would like to use to generate
the first 25 numbers in the Fibonacci series.
Line 32 is the header of that function.
So, I'm receiving the 25,
and now, I'm starting a loop.
So numbers, which is the parameter of the function,
is now 25 because it was passed on from line 48.
We start the loop from zero to 24,
and inside that loop I have another counter.
If you notice, the n starts at zero
outside the loop and at every cycle of the for loop,
I am increasing n by one.
So, n now equals zero.
I'm running Fibonacci with zero,
but I'm doing this 24 times.
So, for each end I'm running
the Fibonacci loop 24 times,
and whenever I say in line 30 end
that I'm calling Fibonacci,
I'm actually going
to a recursive function of Fibonacci.
So, I have a loop.
Inside that loop, I have a call
to a recursive function.
So that recursion is in itself a loop.
We haven't mentioned that
the first time we discussed recursion
because at that point,
we haven't learned about loops yet,
but now it's a good time to see
that all recursion is, it's a loop
without saying it is.
So, this function computes the Fibonacci series,
and there's another interesting line there
that I commented out, which is line 22.
If you want to follow everything that this function does,
I encourage you to print those values.
So uncomment line 22.
Let's push run and see
what the Fibonacci sequence looks like.
And, just to make the output a little bit more readable,
I put the brackets and I formatted it.
So, here are the first 25 numbers from zero to 24,
so we start at zero, 24.
It goes from zero and the last, the 24th cycle,
which is actually number 25.
In Fibonacci, it's 46,368.
If I was to uncomment that line
and run this program,
as you can see,
now you can follow all the evolution
inside each cycle.
So each time you see a number in brackets,
this is the next Fibonacci.
This is the recursion at work.
So, all of this happens
until there's some number in brackets.