Recursion as programming knows it is all about
divide and conquer. Briefly stated
if a problem is too complex you chop it up in smaller instances of itself, fiddle
a bit with the results and you're ready. If the program instance is very simple there
is no need to chop it up but you solve it directly. This is the 'sentinel' condition.
A canonical example is the binary tree; you can recursively define a binary tree
as either nothing at all (the sentinel condition) or a node having two binary trees
as its two children.
Given this simple recursive definition a lot of problems are just corollaries thereof.
e.g. the number of nodes in a tree either equals zero (the sentinel condition) or
one plus the number of nodes of both of the children. In C this translates easily to:
-
int nof_nodes(tree_t* node) {
-
if (node == NULL)
-
return 0;
-
return 1+nof_nodes(node->left)+nof_nodes(node->right);
-
}
-
Another example: the depth of a tree is the length of the longest path from the
root of the tree to a leaf node; this translates to C as:
-
int depth(tree_t* node) {
-
if (node == NULL)
-
return 0;
-
return 1+max(depth(node->left), depth(node->right));
-
}
-
Note the similarity of both functions. There is a simple rule of thumb: the depth
of the stack must not exceed O(n) where n is the size of the problem. For nicely
balanced trees this rule is true. Not so with a recursive definition of another
problem: the factorial of a number either equals one if n equals 0 (the sentinel
condition) or the product of n times the factorial of n-1. This translates to C as:
-
int fac(int n) {
-
if (n == 0)
-
return 1;
-
return n*fac(n-1);
-
}
-
The depth of the stack will aways be O(n) and this function is better expressed
in an iterative way:
-
int fac(int n) {
-
int result= 1;
-
for (; n > 0; result*= n--);
-
return result;
-
}
-
Although this code looks more 'mechanical' it doesn't use any stack at all for its
calculations. This rule of thumb doesn't work for functions with two or more
variables; a famous example is the
Ackermann function:
-
int act(int n, int m) {
-
if (n == 0)
-
return m+1;
-
if (m == 0)
-
return ack(n-1, 1);
-
return ack(n-1, ack(n, m-1));
-
}
-
This little monster uses a horrible amount of stack space and it can't be written
in an iterative way without using any form of a stack. A closed form of this function
does exist but it needs the 'Knuth operator' or similar to be expressed in this
closed form. A bit of theory on recursive functions and computability as well as
Turing decidability can be found
here.
kind regards,
Jos
884
