Help: C++ and recursive functions
Author Message Help: C++ and recursive functions

I am taking a C/C++ class and have an assignment which requires that I
develop a C/C++ program which does the following:

(1) accept an integer value as an input (e.g., 3517)
(2) reverse the digits in the integer and display them to standard
output (e.g., 3517 becomes 7153)

The assignment requires that I implement the solution using "iteration"
(I've done this already -- VERY EASY TO DO) and "recursion" -- somewhat
MORE DIFFICULT.

How do I solve this problem using recursion ?

Some of my  initial thoughts:

I am trying to use the modulus (%) and division (/) operators
repetitively to isolate the digits and change their order:

e.g.,     3517  % 10 = 7 and 3517 / 10 =351
351 % 10 = 1 and 351 / 10 =35
35 % 10 = 5 and 35 / 10 =3
3 % 10 =3
In this manner, I'd like to isolate the digits 7, 1, 5, 3 and
use them to turn 3517 into  7*1000 + 1*100 + 5*10 + 3*1 = 7153

Am I on the right track ? Any suggestions ?

Sud Banerjee

--

Tue, 26 Mar 2002 03:00:00 GMT  Help: C++ and recursive functions

Quote:

> I am taking a C/C++ class and have an assignment which requires that I
> develop a C/C++ program which does the following:
>     (1) accept an integer value as an input (e.g., 3517)
>     (2) reverse the digits in the integer and display them to standard
> output (e.g., 3517 becomes 7153)
> The assignment requires that I implement the solution using "iteration"
> (I've done this already -- VERY EASY TO DO) and "recursion" -- somewhat
> MORE DIFFICULT.
> How do I solve this problem using recursion ?

Can you solve the problem for one digit?
Can you solve the problem for n digits, given
a function that works on n-1 digits?

Then you can solve it for all number of digits:
The trick is that the second function does not
require an already existing function: if it takes
an argument n, it can call itself with argument n-1.

The basic recursion is fac(n):

int fac(int n)
{
if (n==1) return 1      /* Special case */
else return n*fac(n-1);

Quote:
}

Now, the only thing you need to do it to provide
a special case for n<10, and a general solution for
n <- n/10    (since eventually, n/(10*10*10*...*10)
will be smaller then 10)

Note that this is not C specific.

Quote:
> Some of my  initial thoughts:

> I am trying to use the modulus (%) and division (/) operators
> repetitively to isolate the digits and change their order:

> e.g.,     3517  % 10 = 7 and 3517 / 10 =351
>             351 % 10 = 1 and 351 / 10 =35
>             35 % 10 = 5 and 35 / 10 =3
>             3 % 10 =3

This seems like the special case

Quote:
>         In this manner, I'd like to isolate the digits 7, 1, 5, 3 and
> use them to turn 3517 into  7*1000 + 1*100 + 5*10 + 3*1 = 7153
> Am I on the right track ? Any suggestions ?

Look at any recursion example, identify the recursion step
and the special terminating case. Look at your problem, find
a recursion step, and a terminating case. Replace these
steps in the recurion example.

Quote:
> Thanks in advance.
> Sud Banerjee

Success with your homework.

Michiel Salters
--

Tue, 26 Mar 2002 03:00:00 GMT  Help: C++ and recursive functions

Quote:

>     (1) accept an integer value as an input (e.g., 3517)
>     (2) reverse the digits in the integer and display them to standard
> output (e.g., 3517 becomes 7153)
> ... and "recursion" -- somewhat MORE DIFFICULT.
> How do I solve this problem using recursion ?

If you understand what recursion *means*, it is easy.
Since this is a class assignment, it is inappropriate to
ask others to solve the problem for you.
--

Tue, 26 Mar 2002 03:00:00 GMT  Help: C++ and recursive functions

Quote:

>I am taking a C/C++ class and have an assignment which requires that I
>develop a C/C++ program which does the following:

>    (1) accept an integer value as an input (e.g., 3517)
>    (2) reverse the digits in the integer and display them to standard
>output (e.g., 3517 becomes 7153)

>The assignment requires that I implement the solution using "iteration"
>(I've done this already -- VERY EASY TO DO) and "recursion" -- somewhat
>MORE DIFFICULT.

Not so much more difficult as stupider, WAY stupider.  You look
to have some sense.

Quote:
>How do I solve this problem using recursion ?

Speaking as a professional programmer/analyst, the use of
recursion is overrated.  For something as simple as what you have been
assigned to do, recursion is a bad way to do it.

Let me put it this way.  If I had given you the assignment and
not specified any particular way to solve it, I would probably mark
your submission lower for gratuitous use of recursion.

I can think of no sensible way of doing it that wouldn't be
better done by recursion.

Quote:
>Some of my  initial thoughts:

>I am trying to use the modulus (%) and division (/) operators
>repetitively to isolate the digits and change their order:

>e.g.,     3517  % 10 = 7 and 3517 / 10 =351
>            351 % 10 = 1 and 351 / 10 =35
>            35 % 10 = 5 and 35 / 10 =3
>            3 % 10 =3
>        In this manner, I'd like to isolate the digits 7, 1, 5, 3 and
>use them to turn 3517 into  7*1000 + 1*100 + 5*10 + 3*1 = 7153

>Am I on the right track ? Any suggestions ?

Yes.  Carry on.  You don't need recursion to do this though any
more than you need to use square roots.

Feel free to pass my comments on to your instructor.  You may use
my name.  This abuse of recursion is ridiculous.

Recursion can be a very useful technique indeed.  However, in my
years of applications programming, I have only used it seriously on
two occasions.

One of these introduced a bug into the program.  The use of
recursion was the bug more than anything.

The other was trivial and could have been easily avoided with
flags.

Quote:

You're welcome.

Sincerely,

Gene Wirchenko

Computerese Irregular Verb Conjugation:
I have preferences.
You have biases.
He/She has prejudices.
--

Tue, 26 Mar 2002 03:00:00 GMT  Help: C++ and recursive functions

Quote:

>I am trying to use the modulus (%) and division (/) operators
>repetitively to isolate the digits and change their order:

>e.g.,     3517  % 10 = 7 and 3517 / 10 =351
>            351 % 10 = 1 and 351 / 10 =35
>            35 % 10 = 5 and 35 / 10 =3
>            3 % 10 =3
>        In this manner, I'd like to isolate the digits 7, 1, 5, 3 and
>use them to turn 3517 into  7*1000 + 1*100 + 5*10 + 3*1 = 7153

>Am I on the right track ? Any suggestions ?

It is very difficult to respond without actually doing the work.
Personally I would not work on these as ints but convert the int to a
string and then handle the array of char (it is much easier to reverse
arrays.

For recursion think of a function that checks if the string has length
1, if so it outputs the character, else it calls itself passing the
array rep (i.e. all but the first character).  On return it outputs
the first character of its copy of the array.

Francis Glassborow      Journal Editor, Association of C & C++ Users
64 Southfield Rd
Oxford OX4 1PA          +44(0)1865 246490
All opinions are mine and do not represent those of any organisation
--

Tue, 26 Mar 2002 03:00:00 GMT  Help: C++ and recursive functions

: I am taking a C/C++ class and have an assignment which requires that I
: develop a C/C++ program which does the following:
:
:     (1) accept an integer value as an input (e.g., 3517)
:     (2) reverse the digits in the integer and display them to standard
: output (e.g., 3517 becomes 7153)

Ok, your instructor assigned problem #3.31 from D&D (C++).  They at
least had the good sense to not request a recursive solution.  Your
instructor should be hung by the thumbs unless they gave more
details on solving problems (needlessly) using recursion than you
will find in the text.

: The assignment requires that I implement the solution using "iteration"
: (I've done this already -- VERY EASY TO DO) and "recursion" -- somewhat
: MORE DIFFICULT.

Noting that your description does not quite match the textbook which
only asks for a function which reverses the digits, I wonder if that
is the requirement.  The requirement could be to print the digits
reversed using a recursive function.  That would be an easy exercise.
You might try it.

: How do I solve this problem using recursion ?

Since you have stated that you have an iterative solution and have
asked for assistance with a recursive version, here are some thoughts.

Let's assume that your function is

int reverse (int n) {
int r = 0;
while (n > 0) {
r = 10 * r + n % 10;
n /= 10;
}
return r;
}

The problem is that the solution uses a second variable and that both
ints are modified each time through the loop.  The recursion is the
loop and needs two variables.  Extract that to a second function with
two parameters and you should be able to solve it.

int reverse (int n) {
return reverse2 (n, 0);
}

Now ask your instructor what they were trying to do with this example.
Teach lisp?

John
--

Fri, 29 Mar 2002 03:00:00 GMT  Help: C++ and recursive functions

[snip good comments about the pedagogical sanity of the instructor]

Agree.

:      Recursion can be a very useful technique indeed.  However, in my
: years of applications programming, I have only used it seriously on
: two occasions.

Never used qsort? :)

John
--

Fri, 29 Mar 2002 03:00:00 GMT  Help: C++ and recursive functions

Quote:

>>I am taking a C/C++ class and have an assignment which requires that I
>>develop a C/C++ program which does the following:

>>    (1) accept an integer value as an input (e.g., 3517)
>>    (2) reverse the digits in the integer and display them to standard
>>output (e.g., 3517 becomes 7153)

>>The assignment requires that I implement the solution using "iteration"
>>(I've done this already -- VERY EASY TO DO) and "recursion" -- somewhat
>>MORE DIFFICULT.

>     Not so much more difficult as stupider, WAY stupider.  You look
>to have some sense.

>>How do I solve this problem using recursion ?

>     Speaking as a professional programmer/analyst, the use of
>recursion is overrated.  For something as simple as what you have been
>assigned to do, recursion is a bad way to do it.

>     Let me put it this way.  If I had given you the assignment and
>not specified any particular way to solve it, I would probably mark
>your submission lower for gratuitous use of recursion.

>     I can think of no sensible way of doing it that wouldn't be
>better done by recursion.

^^^^^^^^^
This should be "iteration".

- Show quoted text -

Quote:
>>Some of my  initial thoughts:

>>I am trying to use the modulus (%) and division (/) operators
>>repetitively to isolate the digits and change their order:

>>e.g.,     3517  % 10 = 7 and 3517 / 10 =351
>>            351 % 10 = 1 and 351 / 10 =35
>>            35 % 10 = 5 and 35 / 10 =3
>>            3 % 10 =3
>>        In this manner, I'd like to isolate the digits 7, 1, 5, 3 and
>>use them to turn 3517 into  7*1000 + 1*100 + 5*10 + 3*1 = 7153

>>Am I on the right track ? Any suggestions ?

>     Yes.  Carry on.  You don't need recursion to do this though any
>more than you need to use square roots.

>     Feel free to pass my comments on to your instructor.  You may use
>my name.  This abuse of recursion is ridiculous.

>     Recursion can be a very useful technique indeed.  However, in my
>years of applications programming, I have only used it seriously on
>two occasions.

>     One of these introduced a bug into the program.  The use of
>recursion was the bug more than anything.

>     The other was trivial and could have been easily avoided with
>flags.

>     You're welcome.

Sincerely,

Gene Wirchenko

Computerese Irregular Verb Conjugation:
I have preferences.
You have biases.
He/She has prejudices.
--

Fri, 29 Mar 2002 03:00:00 GMT  Help: C++ and recursive functions

Quote:

<snip>

>      Speaking as a professional programmer/analyst, the use of
> recursion is overrated.  For something as simple as what you have been
> assigned to do, recursion is a bad way to do it.

>      Let me put it this way.  If I had given you the assignment and
> not specified any particular way to solve it, I would probably mark
> your submission lower for gratuitous use of recursion.

>      I can think of no sensible way of doing it that wouldn't be
> better done by recursion.

Speaking as a professional programmer, I think that this is a bit of
a narrow minded attitude.  Although C does not encourage recursion,
it's a virtual necessity in many other languages (e.g. Lisp, Prolog).
Having a good understanding of how recursion is used is essential to
being able to use these languages, and to the understanding of many
critical algorithms (e.g. Quicksort).

Quote:
>      Feel free to pass my comments on to your instructor.  You may use
> my name.  This abuse of recursion is ridiculous.

The only way for a student to understand this often confusing concept
is to start with simple examples just like this one.  Recursion is
obviously not the best way to solve this problem in C, but being able
to code the recursive solution is extremely important.

Quote:
>      Recursion can be a very useful technique indeed.  However, in my
> years of applications programming, I have only used it seriously on
> two occasions.

Wow!  I've used recursion countless times.  It's the easiest way to do
a multitude of tasks, suck as sorting, parsing and searching.  Sometimes
I'll even code the recursive solution first, and then convert it to an
iterative solution if testing shows that it's important -- the recursive
solution is invariably smaller and usually simpler to understand than the
iterative one.

Unfortunately this isn't a great example of recursion.  Coding a function
which prints the digits in the _correct_ order is actually much more
intersting.

/peter
--

Fri, 29 Mar 2002 03:00:00 GMT  Help: C++ and recursive functions

Quote:

> [snip good comments about the pedagogical sanity of the instructor]
> Agree.
> :      Recursion can be a very useful technique indeed.  However, in my
> : years of applications programming, I have only used it seriously on
> : two occasions.
> Never used qsort? :)

To pick a minor nut, using qsort() has absolutely nothing to do with
recursion. That's because nowhere in the ANSI C Standard is there a
request that 'qsort' be QuickSort. Or any other recursive sorting
algorithm, for that matter.

I, for one, would probably use Heapsort as the implementation of the
qsort() Standard C Library function.
--

Even if all the snow were burnt, ashes would remain.
--

Sat, 30 Mar 2002 03:00:00 GMT  Help: C++ and recursive functions

Quote:

> :      Recursion can be a very useful technique indeed.  However, in my
> : years of applications programming, I have only used it seriously on
> : two occasions.

> Never used qsort? :)

Are you confusing qsort() with quicksort?  qsort() is not necessarily
an implementation of quicksort.
--

Sat, 30 Mar 2002 03:00:00 GMT  Help: C++ and recursive functions

Quote:

><snip>

>>      Speaking as a professional programmer/analyst, the use of
>> recursion is overrated.  For something as simple as what you have been
>> assigned to do, recursion is a bad way to do it.

>>      Let me put it this way.  If I had given you the assignment and
>> not specified any particular way to solve it, I would probably mark
>> your submission lower for gratuitous use of recursion.

>>      I can think of no sensible way of doing it that wouldn't be
>> better done by recursion.

>Speaking as a professional programmer, I think that this is a bit of
>a narrow minded attitude.  Although C does not encourage recursion,
>it's a virtual necessity in many other languages (e.g. Lisp, Prolog).
>Having a good understanding of how recursion is used is essential to
>being able to use these languages, and to the understanding of many
>critical algorithms (e.g. Quicksort).

Whoa!  See your point later which is my point.

- Show quoted text -

Quote:
>>      Feel free to pass my comments on to your instructor.  You may use
>> my name.  This abuse of recursion is ridiculous.

>The only way for a student to understand this often confusing concept
>is to start with simple examples just like this one.  Recursion is
>obviously not the best way to solve this problem in C, but being able
>to code the recursive solution is extremely important.

>>      Recursion can be a very useful technique indeed.  However, in my
>> years of applications programming, I have only used it seriously on
>> two occasions.

>Wow!  I've used recursion countless times.  It's the easiest way to do
>a multitude of tasks, suck as sorting, parsing and searching.  Sometimes
>I'll even code the recursive solution first, and then convert it to an
>iterative solution if testing shows that it's important -- the recursive
>solution is invariably smaller and usually simpler to understand than the
>iterative one.

No, not invariably.  I can code a digital sum algorithm that uses
recursion.  I can code the same general approach using iteration.
Both solutions are about the same size and the iterative solution is
going to be marginally faster because it doesn't have the overhead of

Not that this really matters in this case because there is a much
faster solution that doesn't use iteration either.  Pick a good
algorithm!

Quote:
>Unfortunately this isn't a great example of recursion.  Coding a function
>which prints the digits in the _correct_ order is actually much more
>intersting.

This is *my* point.

Give an assignment where recursion isn't a very good solution and
actually makes things more complicated.  Given that experience with
recursion, why would the student think it of much use at all?  Indeed,
you may convince him of the opposite.

Recursion is a powerful tool *when used properly*.  Used

Sincerely,

Gene Wirchenko

Computerese Irregular Verb Conjugation:
I have preferences.
You have biases.
He/She has prejudices.
--

Sat, 30 Mar 2002 03:00:00 GMT  Help: C++ and recursive functions

Quote:

>[snip good comments about the pedagogical sanity of the instructor]

>Agree.

>:      Recursion can be a very useful technique indeed.  However, in my
>: years of applications programming, I have only used it seriously on
>: two occasions.

>Never used qsort? :)

I meant that I hadn't coded it.  What someone did is what *they*
did.  My applications don't need me looking at mechanics of sorting.
It's in my language (Visual FoxPro).

Recursion can be very useful, but...

1) That doesn't mean that everyone needs it or needs it very often.

2) ALL recursion can be recoded using iteration so it is always
possible to avoid it.  (Whether one wishes to or not because of the
complexity then entered into the code is a matter for judgement.)

I think I'd be interested in a qsort() that is not recursive.

As I understand it, there are only a few values that one needs to
keep track off.  Stuff these in a structure and malloc() as needed.
Maybe start off with enough space for twenty (some reasonable amount)
levels and if more space is needed then malloc().  Be sure to reuse
the memory.

Don't release any malloc()ed memory until terminating.  This
would get past much of the overhead of subordinate qsort() calls where
memory would be being allocated and deallocated frequently.

Granted that the code might be hairier, but the performance might
be worth it.  The reason that recursion appears to be such a deal is
that function calls handle much of the mechanics for you.  This does
come at a price though.

Sincerely,

Gene Wirchenko

Computerese Irregular Verb Conjugation:
I have preferences.
You have biases.
He/She has prejudices.
--

Sat, 30 Mar 2002 03:00:00 GMT  Help: C++ and recursive functions
A good implementation of qsort will not be recursive. Period.
The best form of quicksort is Sedgewick's Median of three, stack iterative
(with max. stack logN) linear sorting of small subsets. I won't bore you
with lengthy benchmarks; see a good text of the subject.

PS. a good text, not some college bunk advocating Bubble-Sort as an OK
kinda sort!!!

Regards,
Mitch

Quote:

> [snip good comments about the pedagogical sanity of the instructor]

> Agree.

> :      Recursion can be a very useful technique indeed.  However, in my
> : years of applications programming, I have only used it seriously on
> : two occasions.

> Never used qsort? :)

> John
> --

--

Sat, 30 Mar 2002 03:00:00 GMT  Help: C++ and recursive functions

says...

Quote:
> A good implementation of qsort will not be recursive. Period.
> The best form of quicksort is Sedgewick's Median of three, stack iterative
> (with max. stack logN) linear sorting of small subsets. I won't bore you
> with lengthy benchmarks; see a good text of the subject.

Nonsense.  At one time it was profitable to eliminate recursion almost
anytime you could without getting into REALLY ugly code.  With modern
architectures, however, the cost of recursion is often immeasurably
small.  In fact, on some architectures recursion tends to be the
preferable solution -- just for example, the SPARC makes function
calls extremely cheap with its register file architecture.
Eliminating recursion will also eliminate use of the majority of its
registers, in many cases forcing the code to refer to memory instead,
at a dramatic cost in speed.

At one time, recursion was expensive because you had to refer to
memory to create a stack frame, and you ended up with calls and
returns.  Current hardware uses caching quite heavily, and the top
part of the stack is nearly _always_ going to be in the cache because
it's so heavily used.  Nearly every current processor does branch
prediction, typically reducing the cost of the call to nearly
nonexistent.  Many also include a return address stack in the CPU
proper, typically reducing the cost of the return to nil as well.
Finally, since the code for the recursive solution is typically
smaller and simpler, the instruction cache will be better utilized as
well.  In short, if you run benchmarks on current machines, you'll
find little advantage in either direction, and depending on the exact
compiler, architecture, etc. involved, a recursive version is about as
likely to be more efficient version as the more complex non-recursive
version.

To summarize: in 1980 your statement would have been absolutely
correct.  In 1990 it would have been somewhat suspect -- right a bit
more often than wrong, but wrong on some fairly well-known and
important architectures.  Right now in 1999, it's basically just flat-
out wrong.  In another 10 years, I suspect the recursive version will
nearly always be more efficient.

--
Later,
Jerry.

The universe is a figment of its own imagination.
--

Sun, 31 Mar 2002 03:00:00 GMT

 Page 1 of 2 [ 24 post ] Go to page:  

Relevant Pages