int factorial(int n) { if (n == 1) return 1; else return n * factorial(n1); } 
int main() { int k = 4; int f = factorial(4); cout << f << endl; return 0; } 
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(k1); 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() 
n
as
input and returns the value of 1^{2} + 2^{2} +
3^{2} + ... + n^{2} .
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:
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;
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(n1)Great! Now I've got my recursive case!
sumsquare(k1)
help me figure out the
answer to sumsquare(k)
? Well, all I'd need to
add to the result of sumsquare(k1)
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 α 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 Class 15 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.