

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)

You can see that the stack of functions awaiting the return of the most recently called function simpy keeps growing and growing ... and there's nothing there to stop it from growing further! This function has an infinite recursion, meaning that recursive calls are made over and over again, without any mechanism to stop the process. A proper recursive function must always have a base case, meaning a way to return without making a recursive call, which is the mechanism that stops this process of ever more recusive calls and an ever growing stack of function calls waiting on the return of other function calls. Moreover, this base case, i.e. this way of returning without making a recursive call, must be something which we'll eventually hit. Once we hit it, we can start taking function calls off the top of the stack and returning from them.
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;
}
Check the full code.
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 14 homework,
write a recursive function void factor(int n);
that
prints out the factorization of n
to the terminal. 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.
line
. In particular, something like line(10)
will print out *'s as shown below.
**********
*********
********
*******
******
*****
****
***
**
*
Take a look at the solution
Sierpinski gasket

Fern

Escher (Circle Limit IV Heaven Hell)

Natural language processing
