Recursive functions
Harry
1)I need your help to solve a problem.
I have a function whose prototype is
int reclen(char *)
This function has to find the length of the string passed to it.But
the conditions are that no local variable or global variable should be
used.I have to use recursive functions.
2)sizeof(int) is 2 bytes in turboC.It is 4 bytes in case of gcc.why
different compilers allocate different amount of memory?what is the
reason behind it?
Martin Ambuhl
> Hi all,
>
> 1)I need your help to solve a problem.
> I have a function whose prototype is
>
> int reclen(char *)
>
> This function has to find the length of the string passed to it.But
> the conditions are that no local variable or global variable should be
> used.I have to use recursive functions.
#include <string.h>
int reclen(char *s) { return strlen(s); }
no recursive functions are needed.
> 2)sizeof(int) is 2 bytes in turboC.It is 4 bytes in case of gcc.why
> different compilers allocate different amount of memory?what is the
> reason behind it?
Because different architectures and different compiler strategies lead
to different sizes and forms of pointers.
Barry Schwarz
wrote:
>Hi all,
>
>1)I need your help to solve a problem.
>I have a function whose prototype is
>
>int reclen(char *)
>
>This function has to find the length of the string passed to it.But
>the conditions are that no local variable or global variable should be
>used.I have to use recursive functions.
Let p be the name of the function parameter. If the character p
points to is '\0', then the string length is 0. Otherwise, the string
length is 1 + reclen(p+1).
>
>2)sizeof(int) is 2 bytes in turboC.It is 4 bytes in case of gcc.why
>different compilers allocate different amount of memory?what is the
>reason behind it?
Because the person who designed the compiler decided that is what he
wanted. When were the two compilers built? What systems were they
originally intended to work on? What conventions were typical for
those systems at that time?
Remove del for email
Bill Pursell
> 1)I need your help to solve a problem.
> I have a function whose prototype is
>
> int reclen(char *)
>
> This function has to find the length of the string passed to it.But
> the conditions are that no local variable or global variable should be
> used.I have to use recursive functions.
Ask your instructor what the function should do if its
argument is not a string. Then ask your instructor
why you have been given an idiotic assignment which
will not help you learn to program well. Recursive
functions have a place, and this is not it. It is
unethical and/or incomptetent of your instructor to
teach you how to mis-apply a useful technique.
Harald van Dijk
Why should this not be written as a recursive function? If you ignore
practical concerns which do not necessarily apply during the learning
process, do you have any reasons at all?
osmium
> 2)sizeof(int) is 2 bytes in turboC.It is 4 bytes in case of gcc.why
> different compilers allocate different amount of memory?what is the
> reason behind it?
Evolution, basically. Turbo C is quite old (ca. 1994) and the gcc compiler
you are referring to is quite modern. As hardware becomes more capable the
associated software evolves - sometimes excruciatingly slowly - to fit the
new hardware. The two bytes and four bytes you mention are the contemporary
_word_ sizes. This link may give some insight.
http://en.wikipedia.org/wiki/Word_size
Default User
> "Harry" wrties:
>
> > 2)sizeof(int) is 2 bytes in turboC.It is 4 bytes in case of gcc.why
> > different compilers allocate different amount of memory?what is the
> > reason behind it?
>
> Evolution, basically. Turbo C is quite old (ca. 1994)
Oh, older than that. Turbo C 1.0 was pre-ANSI. Borland came out with
the more or less ANSI compatible 2.0 in 1989. That was my first
programming system, which I started using in 1990 or so.
Brian
Richard
This is as good as anything to teach the basics of recursive functions.
Bill Pursell
Because it is totally inappropriate to use a recursive
function to compute the length of a string. It may be
useful to do it as an exercise for the sake
of playing with recursive functions, but only if it
is strongly emphasized that using recursion is absolutely
the wrong way to solve this problem. However, it is
far better to teach recursion with examples for
which recursion is the correct solution method.
Practical concerns must be applied during the learning
process, or else the learning process is detached
from reality, and the end result is a programmer who
doesn't know when a technique is appropriate.
Lauri Alanko
Bill Pursell <bill.p...@gmail.com> wrote:
> Because it is totally inappropriate to use a recursive
> function to compute the length of a string.
"Totally inappropriate" apparently means here "inefficient on a
typical C implementation". That is certainly true, but not always
crucial. Even the space performance isn't an issue if the lengths of
all argument strings are known to have a reasonable bound.
Efficiency aside, recursion is certainly a natural way of defining the
length of a sequence.
Lauri
Bill Pursell
> In article <1175456107.493063.221...@n76g2000hsh.googlegroups.com>,
>
> Bill Pursell <bill.purs...@gmail.com> wrote:
> > Because it is totally inappropriate to use a recursive
> > function to compute the length of a string.
>
> "Totally inappropriate" apparently means here "inefficient on a
> typical C implementation". That is certainly true, but not always
> crucial. Even the space performance isn't an issue if the lengths of
> all argument strings are known to have a reasonable bound.
>
> Efficiency aside, recursion is certainly a natural way of defining the
> length of a sequence.
It is a natural way of defining the length of a finite sequence
in a mathematical setting. It is not completely unnatural
to define the length of a finite sequence in terms of recursion
on a computer. However, it IS totally inappropriate to compute
the value using recursion. Totally inappropriate does
not mean "inefficient in a typical C implementation". It
is, rather, a euphimism for "completely boneheaded".
Harald van Dijk
I don't agree. Practical concerns should be secondary during the
learning process, or else the learning process only allows the
programmer to familiarise himself with limited techniques. The first
question should always be one of readability. Additionally, recursion
in the form that would be used by array length functions gets replaced
with iteration forms by certain modern compilers, taking away from the
practical concerns.
Bill Pursell
I should probably learn to pause for at least 10 seconds
before posting, if only to catch stupid spelling errors.
To clarify why I think it's wrong to use recursion in
this case: things should be kept as simple as possible,
but no simpler. The standard library provides strlen,
and "return strlen( a );" is simpler than
"return 1 + reclen( a + 1 );". I'm actually not at
all concerned about efficiency of the implementation,
and in fact it wouldn't bother me if strlen were
implemented as a recursive function. Well, maybe not. :)
Keith Thompson
In real-world C code, I agree. <OT>In Lisp-like languages, it might
be perfectly appropriate.</OT>
But homework assignments are not real-world code; consider how easily
we can tell the difference when people post here asking for help. The
canonical first program is "Hello, world". That's not something for
which there's any real-world requirement. The existing "echo" command
on many systems is an easier and more flexible way to print an
arbitrary message. If I had an actual requirement to print the string
"Hello, world", writing a C program wouldn't be my first choice. But
the point of the program is to learn how to create, compile, and
execute a C program. Using a minimal example lets the beginner do
this without other considerations getting in the way.
Similarly, problems that actually require recursion tend to be more
complex than might be appropriate for a beginner, but we *can* teach
the elements of recursion using artificially simple example, like
computing the length of a string. It might be appropriate to mention
in passing that recursion really isn't the best solution (in fact, a
call to the strlen() function is) -- and for all we know, the OP's
instructor might have mentioned that.
Later on, I'd probably use something like Quicksort as an example of
something where recursion *is* appropriate -- and I might assign a
non-recursive Quicksort (using an explicit stack) to demonstrate that
it's possible, and to show that using the function call mechanism lets
the language take care of a lot of the details for you. I'd probably
also assign, or at least discuss, a recursive Fibonacci function to
demonstrate a case where simple recursion is a *really* bad solution.
But that can come later.
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
army...@email.it
> I'd probably
> also assign, or at least discuss, a recursive Fibonacci function to
> demonstrate a case where simple recursion is a *really* bad solution.
> But that can come later.
Using iteration to computate Fibonacci numbers is somewhat tricky, at
least conceptually.
Why is it *really* bad? IMO it is much more pointless to use recursion
to compute factorials (the classical example) or (*sigh*) to find the
minimum in an array (as my textbook did).
CBFalconer
> Bill Pursell wrote:
>> "Harry" <geharipras...@gmail.com> wrote:
>>
>>> 1)I need your help to solve a problem.
>>> I have a function whose prototype is
>>>
>>> int reclen(char *)
>>>
>>> This function has to find the length of the string passed to it.
>>> should be used.I have to use recursive functions.
>>
>> Ask your instructor what the function should do if its argument
>> is not a string. Then ask your instructor why you have been
>> given an idiotic assignment which will not help you learn to
>> program well. Recursive functions have a place, and this is not
>> it. It is unethical and/or incomptetent of your instructor to
>> teach you how to mis-apply a useful technique.
>
> Why should this not be written as a recursive function? If you
> ignore practical concerns which do not necessarily apply during
> the learning process, do you have any reasons at all?
However, assuming that pass-in time has passed, how about:
size_t lghofstr(char * s) {
if (s && *s) return 1 + lghofstr(s + 1);
else return 0;
}
Incidentally, while it may be idiotic as a function, is is not
idiotic as a means of demonstrating recursive manipulation, and the
cost thereof.
--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>
--
Posted via a free Usenet account from http://www.teranews.com
Keith Thompson
Because a recursive Fibonacci function performs O(n**2) computations,
as compared to O(n) for an interative solution.
Bill Pursell
> "Bill Pursell" <bill.purs...@gmail.com> writes:
> > On Apr 1, 9:10 pm, Lauri Alanko <l...@iki.fi> wrote:
> >> In article <1175456107.493063.221...@n76g2000hsh.googlegroups.com>,
> >> Bill Pursell <bill.purs...@gmail.com> wrote:
> >> > Because it is totally inappropriate to use a recursive
> >> > function to compute the length of a string.
>
> >> "Totally inappropriate" apparently means here "inefficient on a
> >> typical C implementation". That is certainly true, but not always
> >> crucial. Even the space performance isn't an issue if the lengths of
> >> all argument strings are known to have a reasonable bound.
>
> >> Efficiency aside, recursion is certainly a natural way of defining the
> >> length of a sequence.
>
> > It is a natural way of defining the length of a finite sequence
> > in a mathematical setting. It is not completely unnatural
> > to define the length of a finite sequence in terms of recursion
> > on a computer. However, it IS totally inappropriate to compute
> > the value using recursion. Totally inappropriate does
> > not mean "inefficient in a typical C implementation". It
> > is, rather, a euphimism for "completely boneheaded".
>
> In real-world C code, I agree. <OT>In Lisp-like languages, it might
> be perfectly appropriate.</OT>
>
> But homework assignments are not real-world code; consider how easily
> we can tell the difference when people post here asking for help.
You make many excellent points, which I'll try to remember
when I start to make up multiplication flash cards in hex
for my kids. :) I've never taught any programming courses,
but I've taken a few, and have always been very frustrated
by the lack of practicality. As a result, I find myself
spending a lot of time getting burned by triviata that
I should have known better about. Perhaps it is true
that certain things can only be learned by being burned,
but the purist in me wants to believe that is not the
case.
As to the Fibonacci example for recursion: why have
I never seen a programming example of the closed
form solution? There's a nice exposition here:
http://mathproofs.blogspot.com/2005/04/nth-term-of-fibonacci-sequence.html
(I only glanced at it, so I won't vouch for accuracy).
Why bother with the iterative solution, when you
can just compute the value?
Keith Thompson
[...]
> As to the Fibonacci example for recursion: why have
> I never seen a programming example of the closed
> form solution? There's a nice exposition here:
> http://mathproofs.blogspot.com/2005/04/nth-term-of-fibonacci-sequence.html
> (I only glanced at it, so I won't vouch for accuracy).
> Why bother with the iterative solution, when you
> can just compute the value?
The closed-form solution involves square roots, which means it's
likely to be relatively expensive (it's O(1) rather than O(N), but
with a bigger constant) and possibly subject to rounding errors.
For small valuess, the iterative solution is likely to be faster. For
larger values, the closed-form solution is likely to be faster, but
you typically want all the lower values anyway. Computing the N'th
Fibonacci number iteratively is O(n), but it has the side effect of
computing all lower Fibonacci numbers, making the marginal cost O(1).
army...@email.it
> In real-world C code, I agree. <OT>In Lisp-like languages, it might
> be perfectly appropriate.</OT>
>
> But homework assignments are not real-world code; consider how easily
> we can tell the difference when people post here asking for help. The
> canonical first program is "Hello, world". That's not something for
> which there's any real-world requirement.
a real-world C program (it is done all time)...
> Similarly, problems that actually require recursion tend to be more
> complex than might be appropriate for a beginner, but we *can* teach
> the elements of recursion using artificially simple example, like
> computing the length of a string. It might be appropriate to mention
> in passing that recursion really isn't the best solution (in fact, a
> call to the strlen() function is) -- and for all we know, the OP's
> instructor might have mentioned that.
...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.
Keith Thompson
> Keith Thompson ha scritto:
>> In real-world C code, I agree. <OT>In Lisp-like languages, it might
>> be perfectly appropriate.</OT>
>>
>> But homework assignments are not real-world code; consider how easily
>> we can tell the difference when people post here asking for help. The
>> canonical first program is "Hello, world". That's not something for
>> which there's any real-world requirement.
> 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.
>> Similarly, problems that actually require recursion tend to be more
>> complex than might be appropriate for a beginner, but we *can* teach
>> the elements of recursion using artificially simple example, like
>> computing the length of a string. It might be appropriate to mention
>> in passing that recursion really isn't the best solution (in fact, a
>> call to the strlen() function is) -- and for all we know, the OP's
>> instructor might have mentioned that.
> ...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
<snip>
> 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?"
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
Army1987
news:lnlkh71...@nuthaus.mib.org...
>>> But homework assignments are not real-world code; consider how easily
>>> we can tell the difference when people post here asking for help. The
>>> canonical first program is "Hello, world". That's not something for
>>> which there's any real-world requirement.
>> 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.
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.)
>>> Similarly, problems that actually require recursion tend to be more
>>> complex than might be appropriate for a beginner, but we *can* teach
>>> the elements of recursion using artificially simple example, like
>>> computing the length of a string. It might be appropriate to mention
>>> in passing that recursion really isn't the best solution (in fact, a
>>> call to the strlen() function is) -- and for all we know, the OP's
>>> instructor might have mentioned that.
>> ...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.
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[i] > 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" <ks...@mib.org> ha scritto nel messaggio
> news:lnlkh71...@nuthaus.mib.org...
>> 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.
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
--
Charlton Wilbur
cwi...@chromatico.net
Army1987
>> 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 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
> > 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?"
Good Elusion, Buddy
--
Jean-Marc
ymun...@gmail.com
> "Keith Thompson" <k...@mib.org> ha scritto nel messaggionews:lnr6qyz...@nuthaus.mib.org...
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
[snip much]
>
>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.
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.
Army1987
"Charlton Wilbur" <cwi...@chromatico.net> ha scritto nel messaggio
news:87k5wp8...@mithril.chromatico.net...
> 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[i]);
putchar('\n');
}
Harald van Dijk
> "Charlton Wilbur" <cwi...@chromatico.net> ha scritto nel messaggio
> news:87k5wp8...@mithril.chromatico.net...
>
> > 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
news:1175940630.4...@w1g2000hsg.googlegroups.com...
> Army1987 wrote:
>> 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?
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.
Harald van Dijk
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?
Chris Torek
shaved off before I got here:]
>> 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.
>"Charlton Wilbur" <cwi...@chromatico.net> ha scritto nel messaggio
>news:87k5wp8...@mithril.chromatico.net...
>> I strongly doubt these percentages. [snip]
In article <ev7n9v$jt8$1...@tdi.cu.mi.it> Army1987 <pleas...@for.it> wrote:
>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).
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.
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
news:1176043314.6...@n76g2000hsh.googlegroups.com...
> On Apr 1, 10:27 am, "Bill Pursell" <bill.purs...@gmail.com> wrote:
>
> size_t lghoftree(node * n) {
> if !(n == null) return 1 + lghoftree(n->left) + lghoftree(n-
>>right);
> 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
<r...@see.sig.invalid> wrote:
> Keith Thompson said:
>
> <snip>
>
> > 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?"
<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 </>
Army1987
"David Thompson" <dave.th...@verizon.net> ha scritto nel messaggio
news:6km32391s1pi3ntu7...@4ax.com...
That's how my teacher implements the function to add an item at the
end of a list (I copied and pasted, translated the identifiers from
Italian to English -- keeping the capitalization style, removed his
comments and added mine):
typedef struct LI {
InfoType Info;
struct LI *Next;
} ListItemType, *ListType;
#include <stdlib.h>
int EmptyList (ListType List)
/* Why don't directly use (List == NULL) ? */
{
if (List == NULL)
return 1;
else
return 0;
}
void InsertAtEnd (ListType *List, InfoType Info)
{
ListType Ptr;
if (EmptyList (*List))
{
Ptr = malloc(sizeof(TipoElemLista));
Ptr->Next = NULL;
/* I've heard that, on 26 December 2006, someone used a
* program with that function on a DS9K on board of a small
* boat somewhere in the Pacific Ocean, and the malloc above
* had failed. */
Ptr->Info = Info;
/* What if InfoType is an array type? */
*List = Ptr;
}
else InsertAtEnd(&((*List)->Next), Info);
/* This could easily be the ugliest looking line of code I've
* ever seen in any language, and is the most effective way of
* convincing one's students that linked lists are evil, and
* to prevent them from ever using linked lists. */
}
Why? Because this is the *only* way our textbook implements such a
function. (Actually, it uses
typedef enum {false, true} boolean;
and declares EmptyList to return such a type.) Even if the teacher
also gave an almost sane iterative version of the function (yes, it
uses a while when a for would do that, and it doesn't check the
result of malloc, but it is much less insane than the one in the
book), the only fact that he copied such a function from that book
and showed it to us caused *all* the students which took the only
exam in which he ever asked to write a function to add an element
at the end of a list, to fail.
Army1987
"Army1987" <pleas...@for.it> ha scritto nel messaggio
news:evt7mc$d5o$1...@tdi.cu.mi.it...
> typedef struct LI {
> InfoType Info;
> struct LI *Next;
> } ListItemType, *ListType;
> #include <stdlib.h>
> int EmptyList (ListType List)
> /* Why don't directly use (List == NULL) ? */
> {
> if (List == NULL)
> return 1;
> else
> return 0;
> }
> void InsertAtEnd (ListType *List, InfoType Info)
> {
> ListType Ptr;
> if (EmptyList (*List))
> {
> Ptr = malloc(sizeof(TipoElemLista));
That is, ListItemType.