Recursive functions

[Harry]

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.

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?

[Bill Pursell]

On Apr 1, 9:10 pm, Lauri Alanko <[e-mail] te:

In article <1175456107.493 063.221...@n76g 2000hsh.googleg roups.com>,

Bill Pursell <bill.purs...@g mail.comwrote:

Because it is totally inappropriate to use a recursive
function to compute the length of a string.

"Totally inappropriate" apparently means here "inefficien t 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 "inefficien t in a typical C implementation" . It
is, rather, a euphimism for "completely boneheaded".

[=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=]

On Apr 1, 7:35 pm, "Bill Pursell" <bill.purs...@g mail.comwrote:

On Apr 1, 12:46 pm, "Harald van Dijk" <true...@gmail. comwrote:

Bill Pursell wrote:

On Apr 1, 6:37 am, "Harry" <geharipras...@ gmail.comwrote:

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 shouldbe
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?

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.

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]

On Apr 1, 9:24 pm, "Bill Pursell" <bill.purs...@g mail.comwrote:

On Apr 1, 9:10 pm, Lauri Alanko <[e-mail] te:

In article <1175456107.493 063.221...@n76g 2000hsh.googleg roups.com>,

Bill Pursell <bill.purs...@g mail.comwrote:

Because it is totally inappropriate to use a recursive
function to compute the length of a string.

"Totally inappropriate" apparently means here "inefficien t 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 "inefficien t in a typical C implementation" . It
is, rather, a euphimism for "completely boneheaded".

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]

"Bill Pursell" <bi**********@g mail.comwrites:

On Apr 1, 9:10 pm, Lauri Alanko <[e-mail] te:

>In article <1175456107.493 063.221...@n76g 2000hsh.googleg roups.com>,
Bill Pursell <bill.purs...@g mail.comwrote:

Because it is totally inappropriate to use a recursive
function to compute the length of a string.

"Totally inappropriate" apparently means here "inefficien t 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 "inefficien t 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. 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_Keit h) 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"

[army1987]

On 2 Apr, 00:05, Keith Thompson <[e-mail] ote:

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]

Harald van D?k wrote:

Bill Pursell wrote:

>"Harry" <geharipras...@ gmail.comwrote:

>>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.

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]

ar******@email. it writes:

On 2 Apr, 00:05, Keith Thompson <[e-mail] ote:

>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).

Because a recursive Fibonacci function performs O(n**2) computations,
as compared to O(n) for an interative solution.

--
Keith Thompson (The_Other_Keit h) 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"

[Bill Pursell]

On Apr 1, 11:05 pm, Keith Thompson <[e-mail] ote:

"Bill Pursell" <bill.purs...@g mail.comwrites:

On Apr 1, 9:10 pm, Lauri Alanko <[e-mail] te:

In article <1175456107.493 063.221...@n76g 2000hsh.googleg roups.com>,
Bill Pursell <bill.purs...@g mail.comwrote:
Because it is totally inappropriate to use a recursive
function to compute the length of a string.

"Totally inappropriate" apparently means here "inefficien t 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 "inefficien t 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/...-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]

"Bill Pursell" <bi**********@g mail.comwrites:
[...]

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/...-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).

--
Keith Thompson (The_Other_Keit h) 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"

[army1987]

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)...

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.