double power(double x, int
n);
that computes powers. It must be recursive, so
don't use any loops. Remember: find a base case and ask
yourself how making a recursive call to power
with a smaller exponant could help you define the function.
Write a program that that tests your function by taking in an
x
and a n
from the user and printing
out the result of power(x,n)
.
Turn In a printout of your program and a screen capture
showing your program run on x = 3.5
and n =
8
.
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)
|
int sum(int k) { int p = 0, ans = 0; // Base case if (k == 0) return 0; // Recursive case p = sum(k-1); ans = p + k; return ans; }The base case here is reached when
k
is
zero. Moreover, no matter how big the number in our initial
call to sum
, we must eventually reach our base case,
because the argument to our recursive calls keep getting smaller
and smaller, until they finally reach zero. If we call
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()
|
So, to be a properly defined recursive function you must have a base case, i.e. a way for the function to return without making a recursive call, and your recursive calls must work towards the base case.
n
as
input and returns the value of 12 + 22 +
32 + ... + n2 .
Not a very interesting problem, but so simple that we can
concentrate on problem solving 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. If we're going to solve this recursively, we have two big questions:
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;
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; }To start thinking of recursion the "right way", we're going to use the debugger to run through sumsquare(10), being carefull to step over the recursive call ... because after all we're just going to press the "I believe" button and assume it's going to do what it should. This program should help you do that.
A
and
B
(okay, he was greek, so it probably would've
been alpha and beta ...) 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 Class 17,
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.