Recursive functions

[Keith Thompson]

Keith Thompson ha scritto:
But it *is* useful to know how to print a message to stdin from within
a real-world C program (it is done all time)...

I assume you mean stdout, not stdin. But that's not the main point of
the "hello, world" program. It's certainly one thing a student will
learn from it, but the main point is to learn how to write, compile,
and execute a program.

...whereas it is *totally* *useless* to know how to recursively
implement an algorithm which is 1) much, much better implemented
iteratively, and 2) already implemented by the standard library.

The point is not to learn how to compute the length of a string. The
point is to learn about recursion. Introducing the concept of
recursion via a simple task allows the student to learn about the
concept without a lot of extraneous details getting in the way.

How did you first learn about recursion?

 

[Richard Heathfield]

Keith Thompson said:

How did you first learn about recursion?

I found someone standing nearer to Douglas Hofstadter than me, and asked
him "how did you first learn about recursion?"

 

[Army1987]

I assume you mean stdout, not stdin. But that's not the main point of
the "hello, world" program. It's certainly one thing a student will
learn from it, but the main point is to learn how to write, compile,
and execute a program.

But it doesn't teach the students to invent a square wheel when the existing
round wheel performs much better. (Yes, using printf("Hello, world!\n");
isn't as good as using puts("Hello, world!");, but it is very far less
brain-dead than computing the length of a string by recursion.)

The point is not to learn how to compute the length of a string. The
point is to learn about recursion. Introducing the concept of
recursion via a simple task allows the student to learn about the
concept without a lot of extraneous details getting in the way.

But you should either choose one of the problems for which recursion is
*really* useful, or explicitly tell the students "This is just an example,
actually using a for loop for this would be much better". Otherwise, you'll
give the students that recursion is the right way to do that problem, or
(slighty less bad) that recursion is just an alternative to iteration, the
difference only being style. Usually, whenever iteration and recursion are
both possible, 99% of times iteration is more efficient, and 90% of times
iteration is much clearer and easier to understand. I don't object to using
recursion in teaching when it is clearer than iteration (e.g. Fibonacci
numbers, at least in C and similar languages; in languages which support
tuple assignment such as Python's (a, b) = (b, a+b) it's another story...).
But sometimes didactic examples of recursion, as well as being less
efficient than the iterative equivalents, are very, very much harder to
understand. What's the purpose of that, other than counfusing students?
Also, my teacher routinely did things such as (copied and pasted).

typedef enum {false, true} boolean;
boolean nondecrRic (int a[], int cont)
{
boolean nondecrRic_aux (int a[], int cont, int i);

return nondecrRic_aux (a,cont,0);
}

boolean nondecrRic_aux (int a[], int cont, int i)
{
if (i == cont-1) return true;
if (a > a[i+1]) return false;
return nondecrRic_aux(a,cont,i+1);
}
(this is the first one I found, but there were much worse ones, which made
me get a headache to figure out how they worked, while iterative algorithms
were much clearer...). Which I always refused to do. When he asked me to use
recursion to do that, I would use

boolean nondecr (int a[], int length)
{
if (length < 2) return true;
if (a[0] > a[1]) return false;
else return nondecr(a+1, length-1);
}

and I would have been tempted to add /*A for loop would do that better*/ if
I had been told to use recursion for a problem which solving recursively is
more than 1000 times harder than solving it iteratively. (He did solve
recursively such problems, but luckily he never asked us to do so.)

How did you first learn about recursion?

I've known that recursion existed since a long time, but I had never used it
in computing until I was first taught C in a class few months ago. Due to
the brain damage caused by my teacher, for a few weeks I found that the
natural way to implement a selection sort was recursion.

 

[Keith Thompson]

"Keith Thompson" <[email protected]> ha scritto nel messaggio


But you should either choose one of the problems for which recursion is
*really* useful, or explicitly tell the students "This is just an example,
actually using a for loop for this would be much better". Otherwise, you'll
give the students that recursion is the right way to do that problem, or
(slighty less bad) that recursion is just an alternative to iteration, the
difference only being style.

I think we're basically in agreement. I never said that the
instructor shouldn't tell the students that recursion isn't the best
way to compute the length of a string. I'm merely advocating using
small, easily understood examples to introduce the concept -- and
those small, easily understood examples typically are not realistic
real-world problems.

If you were teaching carpentry to someone who's never used a hammer,
you wouldn't ask him to build a house, just because that's a realistic
example of hammer use. You'd probably start with "Pound this nail
into this piece of wood.", or perhaps "Pound this nail into these two
pieces of wood."

Usually, whenever iteration and recursion are
both possible, 99% of times iteration is more efficient, and 90% of times
iteration is much clearer and easier to understand. I don't object to using
recursion in teaching when it is clearer than iteration (e.g. Fibonacci
numbers, at least in C and similar languages;

[...]

Fibonacci numbers are an interesting example. Yes, a recursive
solution is cleaner than an iterative solution, but it's much less
efficient.

 

[Charlton Wilbur]

A> But you should either choose one of the problems for which
A> recursion is *really* useful, or explicitly tell the students
A> "This is just an example, actually using a for loop for this
A> would be much better". Otherwise, you'll give the students that
A> recursion is the right way to do that problem, or (slighty less
A> bad) that recursion is just an alternative to iteration, the
A> difference only being style.

Way back when I was in college, I knew of a sophomore CS major had
absorbed the latter point very well. They had come to the point in
the data structures class where they were expected to write code to
implement binary trees -- one of the places where the recursive
approach to the problem is an order of magnitude simpler than the
iterative approach to the problem.

It was not pretty. I expect that student is in management now.

A> Usually, whenever iteration and recursion are both possible,
A> 99% of times iteration is more efficient, and 90% of times
A> iteration is much clearer and easier to understand.

I strongly doubt these percentages. As iteration can be expressed as
tail recursion and recursion can be expressed as iteration with an
explicit stack, there's less of a difference than you think; beyond
that, the transformation from one to the other is often performed
by the compiler. Further, any claim of "more efficient" without
specifying what's being conserved -- programmer time? CPU time?
lines of code? memory? -- is inherently suspect; and determining what
is "much clearer and easier to understand" is dependent as much on the
reader as the code.

A> I've known that recursion existed since a long time, but I had
A> never used it in computing until I was first taught C in a
A> class few months ago.

This probably has a great deal to do with your skewed percentages above.

Charlton

 

[Army1987]

I think we're basically in agreement. I never said that the
instructor shouldn't tell the students that recursion isn't the best
way to compute the length of a string. I'm merely advocating using
small, easily understood examples to introduce the concept -- and
those small, easily understood examples typically are not realistic
real-world problems.

If I'll ever have to write a book about C for beginners or teach a class C
from scratch, I won't spend more than a page or an hour about recursion. All
I would be going to say would be something like
"""In C, as in many other languages, a function can call itself. This is
called recursion, and such a function is called a recursive function. In
most cases, a recursive function can be replaced with an iterative function
(i.e. one using a loop such as for or while), and viceversa. For example,
Fibonacci numbers are [...]. The function:
int fibonacci(int n)
{
if (n < 0) return -1; /*invalid argument [1]*/
if (n < 2) return n;
else return fibonacci(n-1) + fibonacci(n-2);
}

can be written as:
int fibonacci(int n)
int i;
int a = 0, b = 1, a_new, b_new;
if (n < 0) return -1;
for (i=0; i<n; i++) {
a_new = b; b_new = a+b;
a = a_new; b = b_new;
}
return a;
}

When both iterative and recursive solutions are possible, usually the
iterative solution is more efficient."""
And I would use recursion later in the text only when it's really useful
(possibly never).

[1] Yes, Fibonacci numbers can be also defined for negative numbers. F(-n)
= -(-1)^n * F(n)
So I could rewrite that if with
if (n < 0) return fibonacci(-n)*(n%2 ? 1 : -1);

And this helps also in the second version. (The function will call itself
only once at worst...)
This, too, could be replaced with
if (n < 0) {
n = -n;
b = n%2 ? 1 : -1;
}
But with no significant avantage.

 

[Jean-Marc Bourguet]

I found someone standing nearer to Douglas Hofstadter than me, and asked
him "how did you first learn about recursion?"

Good Elusion, Buddy

 

[ymuntyan]

"Keith Thompson" <[email protected]> ha scritto nel messaggio

I think we're basically in agreement. I never said that the
instructor shouldn't tell the students that recursion isn't the best
way to compute the length of a string. I'm merely advocating using
small, easily understood examples to introduce the concept -- and
those small, easily understood examples typically are not realistic
real-world problems.

If I'll ever have to write a book about C for beginners or teach a class C
from scratch, I won't spend more than a page or an hour about recursion. All
I would be going to say would be something like
"""In C, as in many other languages, a function can call itself. This is
called recursion, and such a function is called a recursive function. In
most cases, a recursive function can be replaced with an iterative function
(i.e. one using a loop such as for or while), and viceversa. For example,
Fibonacci numbers are [...]. The function:
int fibonacci(int n)
{
if (n < 0) return -1; /*invalid argument [1]*/
if (n < 2) return n;
else return fibonacci(n-1) + fibonacci(n-2);

}

Given that it executes itself 20,000 times to calculate 20-th member
of Fibonacci sequence it would make recursion look like some totally
brain-dead technique. How about walking some tree-like structure (or
at least calculating some arithmetic progression if bogus examples are
needed)?

Yevgen

 

[Richard Harter]

If I'll ever have to write a book about C for beginners or teach a class C
from scratch, I won't spend more than a page or an hour about recursion. All
I would be going to say would be something like
"""In C, as in many other languages, a function can call itself. This is
called recursion, and such a function is called a recursive function. In
most cases, a recursive function can be replaced with an iterative function
(i.e. one using a loop such as for or while), and viceversa.

[snip reminader]

Recursion is more complex than that; the connection can be indirect.
For example, function X calls function Y which calls function Z which
calls function X.

Moreover saying that a recursive function can be replaced by an
iterative function is a bit misleading. In general, converting
recursion to iteration requires managing a stack or stacks. There are
certain situations, e.g., tail recursion and bounded memoization, where
a recursive function and be simply converted to iteration. In C that is
often the right thing to do; C does not guarantee cheap tail recursion
and does not support memoization.

 

[Charlton Wilbur]

A> If I'll ever have to write a book about C for beginners or
A> teach a class C from scratch, I won't spend more than a page or
A> an hour about recursion. All I would be going to say would be
A> something like """In C, as in many other languages, a function
A> can call itself. This is called recursion, and such a function
A> is called a recursive function. In most cases, a recursive
A> function can be replaced with an iterative function (i.e. one
A> using a loop such as for or while), and viceversa.

A> When both iterative and recursive solutions are possible,
A> usually the iterative solution is more efficient.""" And I
A> would use recursion later in the text only when it's really
A> useful (possibly never).

I expect that when you reach the point in your education where you
need to deal with tree or graph data structures, or certain types of
sort, you'll change your tune.

And I expect that some day you'll qualify "more efficient" in such a
way that it is not useless blather. Computer science and software
engineering are about *tradeoffs* -- when you talk about efficiency,
you need to quantify what you're conserving, and what the cost is.

Charlton

 

[Army1987]

A> Usually, whenever iteration and recursion are both possible,
A> 99% of times iteration is more efficient, and 90% of times
A> iteration is much clearer and easier to understand.

I strongly doubt these percentages.

[snip]

Choose 1000 random C function which either call themselves (directly or
through another function) or contain a loop. (They shouldn't need
interactive input, of course.)
Rewrite the former using loops and the latter using recursion.
For each one of them, write a main() which calls clock() and stores the
result in a local variable (let's say t0), calls the function 1000 times
(possibly even with different parameters), and then prints
(long)(clock()-t0) to stdout.
Compile them with several compilers, turning off optimizations. Run them.
If you find one compiler with which more than 10 of these functions are
faster in the recursive version, let me know. For curiosity, if there is a
way to do that with your system, check how much memory they use, too.
As for the human readability issue, I concede that it is subjective and
depends on the reader, but IMO most people would find something such as
void print_array(int array[], int length)
{
if (length > 0) {
printf("%d ", array[0]);
print_array(array+1, length-1);
} else
putchar('\n');
}
less "natural" than
void print_array(int array[], int length)
{
int i;
for (i=0; i<length; i++)
printf("%d ", array);
putchar('\n');
}

 

[Guest]

A> Usually, whenever iteration and recursion are both possible,
A> 99% of times iteration is more efficient, and 90% of times
A> iteration is much clearer and easier to understand.

I strongly doubt these percentages.

[snip]

Choose 1000 random C function which either call themselves (directly or
through another function) or contain a loop. (They shouldn't need
interactive input, of course.)
Rewrite the former using loops and the latter using recursion.
For each one of them, write a main() which calls clock() and stores the
result in a local variable (let's say t0), calls the function 1000 times
(possibly even with different parameters), and then prints
(long)(clock()-t0) to stdout.
Compile them with several compilers, turning off optimizations.

Why turn them off?

 

[Army1987]

Why turn them off?

Because they'd defeat the purpose of comparing loops with recursive function
calls, as compilers are allowed to turn them into each over and vice versa.

 

[Guest]

Because they'd defeat the purpose of comparing loops with recursive function
calls, as compilers are allowed to turn them into each over and vice versa.

The cost of a recursive function that the compiler changes into a
loop /is/ the cost of a loop. If you want to accurately test how fast
a recursive function is, let the compiler perform all the
optimisations it normally would. It won't do you any good to dismiss
certain uses of recursive functions for efficiency reasons if you're
not going to look at exactly how efficient they are.

 

[Charlton Wilbur]

A> Choose 1000 random C function which either call themselves
A> (directly or through another function) or contain a loop. (They
A> shouldn't need interactive input, of course.) Rewrite the
A> former using loops and the latter using recursion. For each
A> one of them, write a main() which calls clock() and stores the
A> result in a local variable (let's say t0), calls the function
A> 1000 times (possibly even with different parameters), and then
A> prints (long)(clock()-t0) to stdout. Compile them with several
A> compilers, turning off optimizations. Run them.

You're the one making the ludicrous claim after a few months of C
knowledge; if you want to make such a claim, backed with hard numbers,
it's up to you to show where the numbers came from, and handwaving or
trying to offset the burden of proof onto others is usually a strong
sign that you're wrong.

A> As for the human readability issue, I
A> concede that it is subjective and depends on the reader, but
A> IMO most people would find something such as

Yes, problems for which the iterative solution is clearer are much
easier to comprehend when the solution is written iteratively.

Do you have a point to offer that is not a tautology?

Charlton

 

[Chris Torek]

[I think this was Army1987 as well, although the attribution was
shaved off before I got here:]

I strongly doubt these percentages. [snip]

Choose 1000 random C function which either call themselves (directly or
through another function) or contain a loop. ...

Most of my recursive functions tend to operate on trees. For
instance, here are two I have lying around. (This is an old version
of some old code, dating back to the early 1990s and hence pre-ANSI-C.
I did a quick edit job just now to convert it, and may have damaged
it a bit in the process, although I hope not.)

"struct nvlist" looks like this:

/*
* Name/value lists. Values can be strings or pointers and/or can carry
* integers. The names can be NULL, resulting in simple value lists.
*/
struct nvlist {
struct nvlist *nv_next;
const char *nv_name;
union {
const char *un_str;
void *un_ptr;
} nv_un;
#define nv_str nv_un.un_str
#define nv_ptr nv_un.un_ptr
int nv_int;
};

/*
* Eval an expression tree. Calls the given function on each node,
* passing it the given context & the name; return value is &/|/! of
* results of evaluating atoms.
*
* No short circuiting ever occurs. fn must return 0 or 1 (otherwise
* our mixing of C's bitwise & boolean here may give surprises).
*/
static int
expr_eval(struct nvlist *expr, int (*fn)(const char *, void *), void *context)
{
int lhs, rhs;

switch (expr->nv_int) {

case FX_ATOM:
return ((*fn)(expr->nv_name, context));

case FX_NOT:
return (!expr_eval(expr->nv_next, fn, context));

case FX_AND:
lhs = expr_eval(expr->nv_ptr, fn, context);
rhs = expr_eval(expr->nv_next, fn, context);
return (lhs & rhs);

case FX_OR:
lhs = expr_eval(expr->nv_ptr, fn, context);
rhs = expr_eval(expr->nv_next, fn, context);
return (lhs | rhs);
}
panic("expr_eval %d", expr->nv_int);
/* NOTREACHED */
}

/*
* Free an expression tree.
*/
static void
expr_free(struct nvlist *expr)
{
struct nvlist *rhs;

/* This loop traverses down the RHS of each subexpression. */
for (; expr != NULL; expr = rhs) {
switch (expr->nv_int) {

/* Atoms and !-exprs have no left hand side. */
case FX_ATOM:
case FX_NOT:
break;

/* For AND and OR nodes, free the LHS. */
case FX_AND:
case FX_OR:
expr_free(expr->nv_ptr);
break;

default:
panic("expr_free %d", expr->nv_int);
}
rhs = expr->nv_next;
nvfree(expr);
}
}

In general, while it is possible to flatten out recursion, it is
often not a great idea -- expr_eval() would be considerably more
complicated if written iteratively. But there are special cases,
and curiously, expr_free() is one of them: it uses a mix of recursion
and iteration, with recursion handling left-hand sides, and iteration
handling right-hand sides, of binary operators (AND and OR).

 

[Army1987]

A> As for the human readability issue, I
A> concede that it is subjective and depends on the reader, but
A> IMO most people would find something such as

Yes, problems for which the iterative solution is clearer are much
easier to comprehend when the solution is written iteratively.

Do you have a point to offer that is not a tautology?

I mean that those problems are more common than the ones whose recursive
solution is clearer, at the very least among problems which an introductory
class is supposed to deal with.

I'm not saying that recursion should never be used, I'm saying that
recursion should not be used whenever iteration is best. And usually one
works more often with 1D arrays than with binary trees, and this is much
more true in an introductory class.
The fact that it's hard to cut down a tree with a knife doesn't mean that
you should pretend that cutting a pizza with a chainsaw is a natural
solution, or brain-damage your students into believing it is. At some point,
it is possible that the possibility of cutting a pizza with a knife won't
occur to them.

 

[Alex]

Then ask your instructor
why you have been given an idiotic assignment which
will not help you learn to program well. Recursive
functionshave a place, and this is not it.

It seems screamingly obvious (or at least to me as a teacher,) that
this exercise is being used as a stepping stone to get to something
harder. "First we teach them recursion, then we teach them about
trees, then we link them."

And, given the function for a string could be:

size_t lghofstr(char * s) {
if (s && *s) return 1 + lghofstr(s + 1);
else return 0;
}

(as demonstrated by the wonderful CBFalconer,) it's very easy to
modify it, to find the number of items in a tree.

size_t lghoftree(node * n) {
if !(n == null) return 1 + lghoftree(n->left) + lghoftree(n-

right);

else return 0;
}

So instead of seeing it as a stupid exercise, see it (as is usual in
education) as a stepping stone to something harder.

Alex Williams (please excuse my rusty C

 

[Army1987]

On Apr 1, 10:27 am, "Bill Pursell" <[email protected]> wrote:

size_t lghoftree(node * n) {
if !(n == null) return 1 + lghoftree(n->left) + lghoftree(n-
else return 0;
}

This isn't a thing so f***ing complicated that one won't understand it if he
hadn't done the one with strings before.
For the OP: have they taught you about binary trees in C yet?

 

[David Thompson]

Keith Thompson said:



I found someone standing nearer to Douglas Hofstadter than me, and asked
him "how did you first learn about recursion?"

<OT> Aside: IIRC IME the base case was Steele or maybe Minsky, but the
principle obviously is invariant under a 'translation' like that.

Do you mean distance(someone,Hofstadter) < distance(you,Hofstadter),
which is a good example of recursion, but should properly be written
in your sentence form with 'I', or ...

distance(someone,Hofstadter) < distance(someone,you) which is better
as an example of heuristic or at least depth-first search?

;-o </>