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]

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]

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.

 

[Guest]

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]

"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

 

[Richard]

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.

 

[Default User]

"Harry" wrties:


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

 

[Bill Pursell]

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]

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]

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

 

[Guest]

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]

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

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]

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

 

[army1987]

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]

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.

 

[Keith Thompson]

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.

 

[Bill Pursell]

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

 

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