So if we already know how to compute , then we can compute by multiplying it by .
This naturally leads to a recursive solution.
Now consider the problem of finding the sum of all numbers from to .
We can define it recursively:
So to compute the sum up to , we first compute the sum up to , then add .
The Fibonacci sequence is defined as follows:
So each value depends on the two previous ones. This definition can be translated directly into recursion.
Suppose we want to compute , where is an integer and is a non-negative integer.
A direct recursive definition is:
So the recursive implementation is:
This works in time.
We can improve the previous method.
If is even, then:
So instead of reducing the exponent by each time, we can sometimes reduce it by half. This gives a much faster recursive solution.
The time complexity of this version is , because at many steps we divide the exponent by instead of subtracting .
int factorial(int n) {
if (n == 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
int sum(int n) {
if (n == 0) {
return 0;
} else {
return n + sum(n - 1);
}
}
int F(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return F(n - 1) + F(n - 2);
}
}
int Pow(int a, int n) {
if (n == 0) {
return 1;
} else {
return a * Pow(a, n - 1);
}
}
int Pow(int a, int n) {
if (n == 0) {
return 1;
} else if (n % 2 == 0) {
int A = Pow(a, n / 2);
return A * A;
} else {
return a * Pow(a, n - 1);
}
}