While trying to solve the problem,
I found obstacles within obstacles.
Therefore, I opted for a recursive solution.
— a student
To understand recursion,
we must first understand recursion.
— anonymous
Many computational problems have the following property: every instance of the problem contains a smaller instance of the same problem. We say that such problems have recursive structure. To solve an instance of a problem of this kind, we can use the following method:
solve it directly (use brute force if needed);
reduce it to a smaller instance of the same problem,
apply the method to the smaller instance,
return to the original instance.
The programmer only needs to show how to obtain a solution of the original instance from a solution of the smaller instance; the computer will do the rest. An application of this method produces a recursive algorithm.
Table of contents:
To illustrate the concept of recursive algorithm, consider the following problem: Find the value of a largest element of an array v[0..n-1]. (This problem has already been mentioned in one of the exercises in the Arrays chapter.)
Notice that the problem only makes sense if the array is not empty, that is, if n ≥ 1. Here is a recursive function that solves the problem:
// After receiving v and n >= 1, the function // returns the value of a largest element of // the array v[0..n-1]. int rmaximum (int n, int v[]) { if (n == 1) return v[0]; else { int x; x = rmaximum (n-1, v); // x is largest in v[0..n-2] if (x > v[n-1]) return x; else return v[n-1]; } }
The correctness analysis of the function takes the form of a proof by induction. To begin with, consider an instance in which n is 1. In this instance, the function returns the correct answer, v[0]. Now consider an instance in which n is greater than 1. In this instance, the array has two nonempty parts:
v[0..n-2] and v[n-1].
We may assume that the function solves correctly
the instance v[0..n-2] of the problem,
since this instance is smaller than the original one.
Therefore,
after the line x = rmaximum (n-1, v)
,
we may assume that x is
the value of a largest element of v[0..n-2].
Hence, the solution of the original instance is the larger of
x and v[n-1].
And this is precisely the number that the function computes and returns.
This concludes the proof of correctness of the
rmaximum function.
For a recursive function to be undestandable, the author of the function must state what is it that the function does. And he must state it explicitly and in detail, as I did above in the comment that precedes the code of the function.
How does a computer execute a recursive function? Though relevant and important, this question will be ignored for now. (But you can see the appendix The execution stack of a program in the Stacks chapter.) We shall only examine an example of execution. If v[0..3] is the array 77 88 66 99 , we shall have the following sequence of calls to the function:
rmaximum(4,v) │ rmaximum(3,v) │ │ rmaximum(2,v) │ │ │ rmaximum(1,v) │ │ │ └──────────── returns 77 │ │ └────────────── returns 88 │ └──────────────── returns 88 └────────────────── returns 99
Performance. Some people believe that recursive functions are inherently slow, but this is just an urban legend. The legend may have its origin in some careless programming, as in some of the exercises below. (Not all is rosy, however: the memory space that a recursive function consumes for bookkeeping can be large.)
return v[0]by
return 0? Does it make sense to replace
return v[0]by
return INT_MIN? Does it make sense to replace
x > v[n-1]by
x >= v[n-1]?
int rmaximum (int n, int v[]) { int x; if (n == 1) x = v[0]; else { x = rmaximum (n-1, v); if (x < v[n-1]) x = v[n-1]; } return x; }
int rmaximum (int n, int v[]) { if (n == 1) return v[0]; int x = rmaximum (n-1, v); if (x > v[n-1]) return x; else return v[n-1]; }
int maxim1 (int n, int v[]) { if (n == 1) return v[0]; if (n == 2) { if (v[0] < v[1]) return v[1]; else return v[0]; } int x = maxim1 (n-1, v); if (x < v[n-1]) return v[n-1]; else return x; }
int maxim2 (int n, int v[]) { if (n == 1) return v[0]; if (maxim2 (n-1, v) < v[n-1]) return v[n-1]; else return maxim2 (n-1, v); }
The function rmaximum discussed above reduces the instance v[0..n-1] of the problem to the instance v[0..n-2]. Instead, we can write a function that will reduce v[0..n-1] to v[1..n-1]:
// Upon receiving v and n >= 1, this
// function returns the value of a
// largest element of v[0..n-1].
int
maximum2 (int n, int v[])
{
return rmax (0, n, v);
}
The function maximum2 is just a wrapper
;
the job proper
is done by the recursive function rmax:
// Receives v and i < n and returns the
// value of a largest element of
// v[i..n-1].
int
rmax (int i, int n, int v[])
{
if (i == n-1) return v[i];
else {
int x;
x = rmax (i + 1, n, v);
if (x > v[i]) return x;
else return v[i];
}
}
The function rmax solves a problem more general than the original one (notice the parameter i). The need to generalize the original problem arises quite often in the design of recursive algorithms.
As a matter of curiosity, here is another, perhaps surprising, way of applying recursion to the segment v[1..n-1] of the array. It uses address arithmetic instead of the extra parameter i.
int rmaximum2b (int n, int v[]) { if (n == 1) return v[0]; int x = rmaximum2b (n - 1, v + 1); if (x > v[0]) return x; return v[0]; }
if (x > v[i])by
if (x >= v[i])?
int rmaxx (int p, int r, int v[]) { if (p == r) return v[r]; else { int q, x, y; q = (p + r)/2; // p ≤ q < r x = rmaxx (p, q, v); y = rmaxx (q+1, r, v); if (x >= y) return x; else return y; } }
// Receives an array of size n and returns // the sum of the elements of the array. int sum (int v[], int n) { return sss (v, n+1); } int sss (int v[], int n) { if (n == 1) return 0; return sss (v, n-1) + v[n-1]; }
int ttt (int x[], int n) { if (n == 0) return 0; if (x[n] > 100) return x[n] + ttt (x, n-1); else return ttt (x, n-1); }
int X (int n) { if (n == 1 || n == 2) return n; else return X (n-1) + n * X (n-2); }
double f (double x, double y) { if (x >= y) return (x + y)/2; else return f (f (x+2, y-1), f (x+1, y-2)); }
int ff (int n) { if (n == 1) return 1; if (n % 2 == 0) return ff (n/2); return ff ((n-1)/2) + ff ((n+1)/2); } int main (void) { printf ("%d", ff(7)); return EXIT_SUCCESS; }
int fsc (int n, int depth) { for (int i = 0; i < depth; ++i) printf (" "); printf ("fsc(%d,%d)\n", n, depth); if (n = 1) return 1; if (n % 2 == 0) return fsc (n/2, depth+1); return fsc ((n-1)/2, depth+1) + fsc ((n+1)/2, depth+1); }
int XX (int n) { if (n == 0) return 0; else return XX (n/3+1) + n; }
F(3) F(2) F(1) F(0) F(1)What is the sequence of calls to the function produced by the calculation of F(5)?
int Euclid (int m, int n) { int r; do { r = m % n; m = n; n = r; } while (r != 0); return m; }
. . - . -- . - . --- . - . -- . - . ---- . - . -- . - . --- . - . -- . - .
Answer: No. The additional parentheses are redundant because the operator == takes precedence over ||.