CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 17
  1. #1
    Join Date
    Jul 2015
    Posts
    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?

  2. #2
    Join Date
    Oct 2008
    Posts
    1,456

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


  3. #3
    Join Date
    Jan 2010
    Posts
    1,133

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

  4. #4
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    4,626

    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.

  5. #5
    Join Date
    Jun 2015
    Posts
    208

    Re: Recursive function: take a non-negative integer and print each digit of that inte

    Quote Originally Posted by OReubens View Post
    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.

  6. #6
    Join Date
    May 2007
    Location
    Scotland
    Posts
    1,164

    Re: Recursive function: take a non-negative integer and print each digit of that inte

    Quote Originally Posted by tiliavirga View Post
    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.

  7. #7
    Join Date
    Jun 2015
    Posts
    208

    Re: Recursive function: take a non-negative integer and print each digit of that inte

    Quote Originally Posted by PredicateNormative View Post
    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.

  8. #8
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: Recursive function: take a non-negative integer and print each digit of that inte

    Quote Originally Posted by tiliavirga View Post
    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.

  9. #9
    Join Date
    Jun 2015
    Posts
    208

    Re: Recursive function: take a non-negative integer and print each digit of that inte

    Quote Originally Posted by monarch_dodra View Post
    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.

  10. #10
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    Re: Recursive function: take a non-negative integer and print each digit of that inte

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

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

    Quote 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.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  11. #11
    Join Date
    Oct 2008
    Posts
    1,456

    Re: Recursive function: take a non-negative integer and print each digit of that inte

    Quote Originally Posted by laserlight View Post
    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 ).

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

  12. #12
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    Re: Recursive function: take a non-negative integer and print each digit of that inte

    Quote 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).
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  13. #13
    Join Date
    Oct 2008
    Posts
    1,456

    Re: Recursive function: take a non-negative integer and print each digit of that inte

    Quote Originally Posted by laserlight View Post
    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 )

  14. #14
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    Re: Recursive function: take a non-negative integer and print each digit of that inte

    Quote 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.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  15. #15
    Join Date
    Oct 2008
    Posts
    1,456

    Re: Recursive function: take a non-negative integer and print each digit of that inte

    Quote Originally Posted by laserlight View Post
    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.

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured