Help: C++ and recursive functions
Author |
Message |
Sudipta Banerje #1 / 24
|
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 ? Thanks in advance. Sud Banerjee
--
|
Tue, 26 Mar 2002 03:00:00 GMT |
|
|
Salter #2 / 24
|
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 |
|
|
IST/C #3 / 24
|
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 |
|
|
Gene Wirchen #4 / 24
|
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: >Thanks in advance.
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 |
|
|
Francis Glassboro #5 / 24
|
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[1] (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 |
|
|
John Pott #6 / 24
|
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 |
|
|
John Pott #7 / 24
|
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 |
|
|
Gene Wirchen #8 / 24
|
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". 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. >>Thanks in advance. > 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 |
|
|
Peter Burk #9 / 24
|
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 |
|
|
Hans-Bernhard Broek #10 / 24
|
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 |
|
|
Ben Pfaf #11 / 24
|
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 |
|
|
Gene Wirchen #12 / 24
|
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. 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 additional function calls. 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 improperly, it adds alot of overhead. 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 |
|
|
Gene Wirchen #13 / 24
|
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 |
|
|
Mitc #14 / 24
|
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 |
|
|
Jerry Coff #15 / 24
|
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:
[1]
[2] |
|