Welcome to lesson on recursive functions.
Giving an explicit formula that calculates
the image of any element in the domain
is a great way to describe a function.
We will say that these explicit rules
are closed formulas for the function.
This is normally how functions are defined
in previous math classes.
Analyzing the table below,
let's see if we can determine the algebraic formula
for the function.
It may take some time, but in this case
we can define the function, f,
which maps the set of natural numbers
to the set of natural numbers
as f of n equals n squared plus one.
Which means we take the input, square it, and add one
to get the corresponding output.
This explicit rule is called a closed formula.
So again in this case, the closed formula
is f of n equals n squared plus one.
However, there is another useful way
to describe functions who's domain
is a set of natural numbers
that rely specifically on the structure
of the natural numbers.
We can define a function recursively.
For a function, f, which maps the set of natural numbers
to the set of natural numbers.
A recursive definition consists of an initial condition
together with a recurrence relation.
The initial condition is explicitly given
as the value of f of zero
and the recurrence relation is a formula
for f of n plus one in terms of f of n.
Which means to determine f of n plus one,
we do need f of n.
Where, for an explicit formula or a closed formula,
we only need the value of n or the input.
Let's see if we can determine the recursive function
for the same function shown above.
Again, we already know describe the function below
as the function that maps the set of natural numbers
to the set of natural numbers
such that f of n is equal to n squared plus one
but we can also describe the same function
using a recursive function.
Where to begin, we have f of zero is equal to one
from the first column in the table.
And the recurrence relation
is f of n plus one is equal to f of n plus two n plus one.
Which means to find f of n plus one,
we take the previous function value
and add two times n plus one.
So looking at our work below,
we know f of zero is equal to one
because that is given.
To determine f of one, notice n is equal to zero
since f of zero plus one is equal to f of one,
which indicates that f of one is equal
to f of zero plus two times zero plus one.
And we know off of zero is equal to one,
indicating f of one is equal to one plus zero plus one
which is equal to two.
Now that we know f of one, we can determine f of two.
Notice that for f of two, n is equal to one
giving us f of one plus one, or f of two,
which is equal to f of one plus two times one plus one.
Again, we know f of one is equal to two.
F of two is equal to two plus two plus one
which is equal to five.
Now that we know f of two, we can determine f of three.
To determine f of three,
notice n is equal to two, since two plus one is three.
Giving us f of three is equal to
f of two plus two times two plus one.
And again we know f of two is five.
F of three is equal to five plus four plus one,
which equals 10.
And now that we know f of three,
we can determine f of four.
Notice for f of four, n is equal to three
since three plus one is four.
Giving us f of four is equal to
f of three plus two times three plus one.
F of three is 10.
Two times three is six.
F of four is equal to 10 plus six plus one.
Which is equal to 17.
So notice the drawback on recursive functions
is that we do have to know
previous function value or values
to determine the next function value.
However, recursively defined functions are often easier
to create from a real world problem
because they describe how the values
of the functions are changing.
But as I just mentioned, this comes with a price.
It is harder to calculate the image of a single input
since we need to know the images of other,
previous elements in the domain.
Let's look at the three examples below,
Number one, we have the function, f,
which again maps the set of natural numbers
to the set of natural numbers
which gives the number of snails in your terrarium
in years after you built it
assuming you started with three snails
and the number of snails doubles each year.
The initial condition is f of zero equals three
since you start with three snails.
To get f of n plus one, we would double the number
of snails in the terrarium the previous year
which is given by f of n.
Which gives of f of n plus one is equal to two times f of n.
The full recursive definition contains
both the initial condition
and the recurrence formula or recurrence relation.
Given by f of zero equals three
and f of n plus one equals two times f of n.
For number two, we have the function g
which gives the number of pushups you can do n days
after you started your pushups challenge,
assuming that you can do seven pushups on day zero
and you can do two more pushups each day.
So we are told that on day zero you can do seven pushups.
Which indicates that g of zero equals seven.
The number of pushups you can do on day n plus one
is two more than the number of days you can do on day n
which is given by g of n.
And therefore we have g of zero equals seven
and g of n plus one is equal to g of n plus two.
And then for number three,
the function h is defined by h of n equals n factorial.
Recall that n factorial is equal
to one times two times three,
all the way out to times n minus one times n.
Which is the product of all the numbers from one through n.
And we also define zero factorial as one.
So we know h of zero is equal to one.
To get the recurrence relation,
think about how can get h of n plus one
which equals n plus one factorial from h of n
which is equal to n factorial.
If you write out both of these products,
you will see that n plus one factorial
is just like n factorial
except you have one more term in the product.
You have an extra factor of n plus one.
Which means we have h of zero equals one.
And h of n plus one is equal to n plus one times h of n.
I hope you found this helpful.