-
July 16th, 2015, 06:45 PM
#1
Recursive function: take a non-negative integer and print each digit of that integer
I'm stuck on my last recursive function assignment:
Write a recursive function that takes a nonnegative integer as an
argument and prints each digit of that integer out (in order from left or
right) on a separate line. The base case is one in which the integer
contains only one digit. Note the following when considering the general
case: 1) a number n divided by 10 is the number with the last digit
removed, and 2) n % 10 is the last digit of n. Write a program to test your
function.
This is quite confusing for me. Help?
-
July 17th, 2015, 01:58 AM
#2
Re: Recursive function: take a non-negative integer and print each digit of that inte
consider the number "123456"
123456 % 10 = 6
123456 / 10 = 12345
12345 % 10 = 5
12345 / 10 = 1234
1234 % 10 = 4
1234 / 10 = 123
...
-
July 17th, 2015, 04:56 AM
#3
Re: Recursive function: take a non-negative integer and print each digit of that inte
Also,
(in order from left or right)
I have a feeling that your assignment says that you should print it from "left to right" - check that (that's sort of where the recursion comes in - instead of just doing it in a loop).
-
July 17th, 2015, 06:40 AM
#4
Re: Recursive function: take a non-negative integer and print each digit of that inte
teachers should try and make recursive tasks about problems that are best solved with recursion rather than conveying the bad notion that recursion is a good (or god forbid, better) substitute for iteration.
-
July 17th, 2015, 12:29 PM
#5
Re: Recursive function: take a non-negative integer and print each digit of that inte
Originally Posted by OReubens
teachers should try and make recursive tasks about problems that are best solved with recursion rather than conveying the bad notion that recursion is a good (or god forbid, better) substitute for iteration.
Recursion and iteration are theoretically equivalent so it is not that one is better for certain problems than the other. It's more a question of personal taste and whether you're more comfortable with the imperative or functional programming paradigm.
https://msdn.microsoft.com/en-us/library/bb669144.aspx
If you're in the imperative tradition then iteration is king and recursion is suspicious and if you're in the functional corner it's the other way around.
Interestingly C++ has a pure functional feature called template metaprogramming. It has no notion of state so there is no iteration only recursion possible. If you are requested to solve a problem by way of template metaprogramming and every fiber of you screams iteration you still have to use recursion. Bad luck if you didn't have a teacher with insight and foresight enougth to prepare you for this situation.
-
July 17th, 2015, 01:08 PM
#6
Re: Recursive function: take a non-negative integer and print each digit of that inte
Originally Posted by tiliavirga
Recursion and iteration are theoretically equivalent so it is not that one is better for certain problems than the other. It's more a question of personal taste and whether you're more comfortable with the imperative or functional programming paradigm.
https://msdn.microsoft.com/en-us/library/bb669144.aspx
If you're in the imperative tradition then iteration is king and recursion is suspicious and if you're in the functional corner it's the other way around.
Interestingly C++ has a pure functional feature called template metaprogramming. It has no notion of state so there is no iteration only recursion possible. If you are requested to solve a problem by way of template metaprogramming and every fiber of you screams iteration you still have to use recursion. Bad luck if you didn't have a teacher with insight and foresight enougth to prepare you for this situation.
You seem to miss the practical point that with recursion you can run out of stack space - for this reason in cases that are not sufficiently bound iteration is the clear winner. With template metaprogramming you can reach the compiler limit for recursion - write an isprime template, give it a large prime number and see what happens.
-
July 17th, 2015, 02:30 PM
#7
Re: Recursive function: take a non-negative integer and print each digit of that inte
Originally Posted by PredicateNormative
You seem to miss the practical point
You can reach the limit anywhere but that's not what my post was about. I argued that teachers should teach both iterative and recursive solutions to any problem because students will be required to handle both.
-
July 17th, 2015, 02:41 PM
#8
Re: Recursive function: take a non-negative integer and print each digit of that inte
Originally Posted by tiliavirga
You can reach the limit anywhere but that's not what my post was about. I argued that teachers should teach both iterative and recursive solutions to any problem because students will be required to handle both.
I think the original argument is that some problems really call for recursive solutions (for example, anything that has to do with a tree), whereas others do not (printing a number). When you want to teach recursion, at the very least, do it with a problem where it is called for.
IMO, binary_search is an OK example of a problem that can be efficiently solved either way, and as such would make for a better example. The issue with binary trees is that by the time you get to it, students should already understand recursion...
Is your question related to IO?
Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.
-
July 17th, 2015, 05:09 PM
#9
Re: Recursive function: take a non-negative integer and print each digit of that inte
Originally Posted by monarch_dodra
I think the original argument is that some problems really call for recursive solutions (for example, anything that has to do with a tree), whereas others do not (printing a number). When you want to teach recursion, at the very least, do it with a problem where it is called for.
As I've said, iteration and recursion are equivalent so no problem objectively "calls" for one or the other. It's you who subjectively prefer one over the other.
With everybody preferring either iteration or recursion and nobody knowing the future, the best a teacher can do is hedging the bets and give both equal importance to students.
Last edited by tiliavirga; July 17th, 2015 at 05:12 PM.
-
July 18th, 2015, 01:30 AM
#10
Re: Recursive function: take a non-negative integer and print each digit of that inte
Originally Posted by OReubens
teachers should try and make recursive tasks about problems that are best solved with recursion rather than conveying the bad notion that recursion is a good (or god forbid, better) substitute for iteration.
If TheGreatCthulhu's guess in post #3 is correct, then the expected recursive solution for the problem that Smitten was tasked with is not tail recursive, and the equivalent iterative solution requires an explicit stack.
Even so, I tend to agree with with what monarch_dodra implied (with a hint of recursion, heh) in post #8: students may reasonably be tasked with simpler problems first, even if these problems could be trivially solved using iteration. Such a pedagogical approach does not mean that recursion is better than iteration, or vice versa.
Originally Posted by tiliavirga
I argued that teachers should teach both iterative and recursive solutions to any problem because students will be required to handle both.
I agree, though "any problem" is a little impractical as eventually the teaching points will be less on iteration or recursion in themselves and more on other techniques. Consequently, once students have a grasp of both, it makes sense to give preference to iteration over recursion if the programming language used does not guarantee tail call elimination, as is the case for C++.
Originally Posted by tiliavirga
As I've said, iteration and recursion are equivalent so no problem objectively "calls" for one or the other. It's you who subjectively prefer one over the other.
I do not think the reasoning follows. That they are equivalent means that any problem that can be solved by one can be solved by the other, but that in itself does not mean that a given problem is definitely not "best solved" by one or the other.
In particular, if a solution is not tail recursive, then the equivalent iterative solution would require the use of an explicit stack. This typically would be more complicated and less elegant (since it explicitly involves an additional construct) than the equivalent recursive solution. In such a case, except for real world considerations like limited stack space and recursion depth, the problem would be "best solved" by recursion, assuming there is no better solution that could use tail recursion instead. Of course, this does not mean that students should not be taught how to use iteration with an explicit stack, otherwise there would be a gaping hole in their knowledge of problem solving with programming.
-
July 18th, 2015, 03:02 AM
#11
Re: Recursive function: take a non-negative integer and print each digit of that inte
Originally Posted by laserlight
If TheGreatCthulhu's guess in post #3 is correct, then the expected recursive solution for the problem that Smitten was tasked with is not tail recursive, and the equivalent iterative solution requires an explicit stack.
granted, an explicit stack is the most straightforward way of transforming a recursive solution to an interative solution, but I don't think it's "required" ( unless you consider any form of state an "explicit stack", but this would imply that all iterative solutions do ). As a trivial example, consider a recursive algo having a "closed form" solution ( like, for a given n, getting 1+2+...+n-1+n ).
Originally Posted by tiliavirga
I argued that teachers should teach both iterative and recursive solutions to any problem because students will be required to handle both.
in a computer science class, yes; for example, recursion is essential in mathematics ( see logic and recusion theory ) where it's much simpler to think in terms of stateless entities ... so, yes it's wise to teach both in a purely theorical context IMO
but, when using real languages with stateful variables one should distinguish between "true" recursion ( compile time or tail optimized ) and "emulated" recursion ( that is, having an implicit stack ). The latter means asking for troubles and hardly gives truly more elegant and efficient solutions. Even better, I'd avoid the use of the word "recursion" altogether ( that has a pointless formal meaning ) and focus on the more important concept of mutability.
-
July 18th, 2015, 03:33 AM
#12
Re: Recursive function: take a non-negative integer and print each digit of that inte
Originally Posted by superbonzo
granted, an explicit stack is the most straightforward way of transforming a recursive solution to an interative solution, but I don't think it's "required" ( unless you consider any form of state an "explicit stack", but this would imply that all iterative solutions do ). As a trivial example, consider a recursive algo having a "closed form" solution ( like, for a given n, getting 1+2+...+n-1+n ).
Um, my statement was pertaining to the problem that Smitten posted about, with reference to TheGreatCthulhu's guess. I even mentioned that directly as a preface. I certainly did not state that an explicit stack is required to transform any recursive solution to an equivalent iterative version.
Furthermore, if there is a closed form solution, then it is not an equivalent iterative solution. It is a different solution, perhaps one that is better (or not).
-
July 18th, 2015, 03:57 AM
#13
Re: Recursive function: take a non-negative integer and print each digit of that inte
Originally Posted by laserlight
Um, my statement was pertaining to the problem that Smitten posted about, with reference to TheGreatCthulhu's guess. I even mentioned that directly as a preface.
yep, and I was pointing out that you have'nt proved that an explicit stack is required in the OP case ( the fact that it's not tail recursive does not imply it , unless I'm missing something of course )
-
July 18th, 2015, 04:04 AM
#14
Re: Recursive function: take a non-negative integer and print each digit of that inte
Originally Posted by superbonzo
yep, and I was pointing out that you have'nt proved that an explicit stack is required in the OP case ( the fact that it's not tail recursive does not imply it , unless I'm missing something of course )
I think that the fact that it is not tail recursive does imply that an explicit stack is required, at least if you want an equivalent iterative solution rather than a different solution altogether.
-
July 18th, 2015, 04:28 AM
#15
Re: Recursive function: take a non-negative integer and print each digit of that inte
Originally Posted by laserlight
I think that the fact that it is not tail recursive does imply that an explicit stack is required, at least if you want an equivalent iterative solution rather than a different solution altogether.
well, then I have to ask you what do you mean exactly by equivalent/different solutions. Note that the issue this thread is about ( well, at least concerning OReubens and tiliavirga debate ) has to do with the relative opportunity of "writing a function" satisfying the OP requirements in either recursive or iterative form, regardless of their solution to be equivalent ( in any arbitrary sense ) or not.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|