This idea can seem paradoxical when you're just getting started, so we'll go through an example of how the computer really handles it in order to explain away the paradox. The upshot is that we have the same function, yes, but it is one call of the function that in turn makes a separate call to the same function, but with different arguments.
|
|
The key take-away from this is that there is not contradiction in having multiple active calls to a function (like factorial). In particular:
factorial
may in turn make another
function call to factorial
.
factorial
function.
Consider this function:
int f(int k)
{
int a = k*k;
int b = f(k + 1);
return a + b;
}
Now, let us suppose that we start off by calling
f(3)
. The following table shows what happens as time
evolves a few steps:
call to ... | f(3)
| f(4)
| f(5)
| f(6)
|
awaiting return ... | main()
| f(3)
| f(4)
| f(5)
|
|
Q. Specify the base case of this function.
Answer: When
Q. Does every function call eventually hit the base case?
Answer:
Yes. No matter how big the number in our initial call to
|
sum(3)
from the main
function, the
following table shows how the computation evolves over time:
call to/return value | sum(3) |
sum(2) |
sum(1) |
sum(0) |
returns 0 | returns 1 | returns 3 | returns 6 |
awaiting return ... | main() |
sum(3) |
sum(2) |
sum(1) |
sum(1) |
sum(2) |
sum(3) |
main() |
Q. Does every function call eventually hit the base case, really?
Answer: Well, not really. For example, sum(-1) has
infinite recursion. It never reaches the base case. If we assume that the input
to the function is positive, the function works correctly.
n
as
input and returns the value of 12 + 22 +
32 + ... + n2 .
It is a simple problem that we can concentrate on using recursion.
When you're setting out to write a recursive function, you at least have a prototype in mind. In this case that'll be
int sumsquare(int k);
That part is easy, and no recursion is involved.
In other words, for what inputs can we automatically just spit out the answer without having to do any real work? In particular, without needing a recursive call?
For this problem, I'm asking what values of k
are particularly easy to give the answer to? Of course,
since we're assuming that k
is positive, the
easiest value for k
is 1. If k
is
one we can just immediately return 1. So that gives us our
base case.
// Base case
if (k == 1)
return 1;
How would the answer to a "smaller" problem of the same kind help get the answer to the original problem. In other words, if I just assume that the function (which I already have the prototype for) just "works" for smaller inputs, how will that help me get the answer?
For this problem, what I'm asking is this: How would the
answer to sumsquare(k-1)
help me figure out the
answer to sumsquare(k)
? Well, all I'd need to
add to the result of sumsquare(k-1)
is a
k
2, and I'd have the answer to
sumsquare(k)
. This then gives us our recursive
case:
// Recursive case
int p = sumsquare(k - 1);
int ans = p + k*k;
return ans;
sumsquare
would work right when
we called sumsquare(k - 1)
.
So, here's the complete function:
int sumsquare(int k)
{
// Base case
if (k == 1)
return 1;
// Recursive case
int p = sumsquare(k - 1);
int ans = p + k*k;
return ans;
}
For example, suppose I had a function
factorialSmall that computed the factorial of its
argument, but only for numbers less than 10. How could
I use it to solve factorial 10? Easy:
10*factorialSmall(9) |
Now, suppose factorialSmall worked for any number
less than some value n, but I'm not telling you exactly what n is.
How could I compute factorial(n)? Easy:
n*factorialSmall(n-1) |
Great! Now I've got my recursive case!
A
and
B
(okay, he was greek, so it probably would've
been α and β ...) are two integers with A >= B >=
0
then the GCD of A
and
B
is given by:
B = 0
then the GCD is A
B > 0
then the GCD is the same as
the GCD of B
and A%B
.int
firstfactor(int);
that you guys defined for me in the previous
homework, write a recursive function void factor(int n,
ostream& OUT);
that
prints out the factorization of n
to the output
stream OUT
. What's the base case? How could a
recursive call call to factor
with a smaller
n
-value help solve the problem?
Take a look at my solution.
**********
*********
********
*******
******
*****
****
***
**
*
Take a look at the solution
Sierpinski gasket
|
Fern
|
Escher (Circle Limit IV Heaven Hell)
|
Natural language processing
|