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?

[Martin Ambuhl]

Re: Recursive functions

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

#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]

Re: Recursive functions

On 31 Mar 2007 22:37:59 -0700, "Harry" <gehariprasath@ gmail.com>
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]

Re: Recursive functions

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

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

Re: Recursive functions

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

[osmium]

Re: Recursive functions

"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) 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]

Re: Recursive functions

osmium wrote:

"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]

Re: Recursive functions

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

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

This is as good as anything to teach the basics of recursive functions.

[Bill Pursell]

Re: Recursive functions

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

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]

Re: Recursive functions

In article <1175456107.493 063.221730@n76g 2000hsh.googleg roups.com>,
Bill Pursell <bill.pursell@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.


Lauri

[Bill Pursell]

Re: Recursive functions

On Apr 1, 9:10 pm, Lauri Alanko <l...@iki.fiwro 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?=]

Re: Recursive functions

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]

Re: Recursive functions

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

On Apr 1, 9:10 pm, Lauri Alanko <l...@iki.fiwro 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]

Re: Recursive functions

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

On Apr 1, 9:10 pm, Lauri Alanko <l...@iki.fiwro 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) kst-u@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@email.it]

Re: Recursive functions

On 2 Apr, 00:05, Keith Thompson <k...@mib.orgwr 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).