Thread: A Recursive function for Reversing number?

  1. #1
    Registered User
    Join Date
    Nov 2005
    Posts
    1

    A Recursive function for Reversing number?

    Hi. sorry on my bad english, but I'm not an English speaker.
    I'm a computer student, learning for bachelor's degree.
    I have a task, and i've no idea how to deal with it.
    The mission is quite simple and goes like this:

    I need to write down a recursive function that get a number and return this number - but reverse.
    The function should return the number - not print it.

    Example: The program run, and ask a value for x.
    the user entered 58753 into x.
    The function should return x as 35785.

    Now, I've success to build such one, but with golbal variables. I asked the course guide, but he told me that I've mustn't use global variables, either not loops.

    I've running out of ideas...
    Any help?

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >mustn't use global variables, either not loops
    But you can probably use function parameters. If you need a temporary variable that persists between recursive calls, you can pass the initial value to the first call, modify it within the function, then pass it again when you call the function recursively. With that scratch variable, it's trivial to convert a loop based algorithm like this into a recursive one.
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    Apr 2003
    Posts
    2,663
    If you need a temporary variable that persists between recursive calls, you can pass the initial value to the first call
    I'm horrible at recursion, but while trying to solve that problem recursively, I hit on the idea of using a default value for a second parameter. That way you could call the function with just one argument-- the number--and still have a variable to use to send values to the recursive function calls. I wasn't sure whether I would be considered a recursive cheat or not.

    I still couldn't figure it out though.
    Last edited by 7stud; 11-27-2005 at 06:38 PM.

  4. #4
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Quote Originally Posted by Deshe
    I've running out of ideas...
    Any help?
    Here's a bit more explanation about what Prelude wrote.

    Take (for an example) something simple: a function that takes two arguments, N and M, and computes M * N! (that's N factorial). You could create this with a while loop. I'll use a goto statement, just for fun. (It's just an example, not code that I'd want to share with anybody else.)

    Code:
    int factorial_multiply(int M, int N) {
        top_of_function:
            if (N == 0) {
                return M;
            }
    
            M = M * N;
            N = N - 1;
            goto top_of_function;
    }
    The algorithm is simple: it multiplies M by all the numbers from 1 to N. I would divide this algorithm into two logical parts: The first part tests if N is zero, and if that's the case, returns M. The second part updates the variables M and N with new values, and then jumps to the top of the function.

    Here's an alternative (but very similar) version of the algorithm:
    Code:
    int factorial_multiply(int N, int M) {
            if (N == 0) {
                return M;
            }
    
            return factorial_multiply(M * N, N - 1);
    }
    It could be described the same way as before: "The first part tests if N is zero, and if that's the case, returns M. The second part updates the variables M and N with new values, and then jumps to the top of the function."

    Any time you have a recursive call whose return value gets returned immediately, you can think of the recursive call as a "goto with arguments." The line 'return factorial_multiply(M * N, N - 1);' effectively picks new values for N and M, and then jumps back to the top of the function.

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >I wasn't sure whether I would be considered a recursive cheat or not.
    If it works, who cares?

    >I still couldn't figure it out though.
    With or without the second parameter? It's rather difficult to solve the problem without it because you need to switch the order of operations. First you need to add the current least significant digit to the new value, then recurse, otherwise the digits won't be reversed. Without the extra parameter, you can't easily do that. It's easy to copy the argument:
    Code:
    int revnum ( int num )
    {
      if ( num == 0 )
        return 0;
      else
        return 10 * revnum ( num / 10 ) + ( num % 10 );
    }
    Not exactly useful though.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Undefined Reference Compiling Error
    By AlakaAlaki in forum C++ Programming
    Replies: 1
    Last Post: 06-27-2008, 11:45 AM
  2. recursive function
    By technosavvy in forum C Programming
    Replies: 1
    Last Post: 02-29-2008, 05:42 AM
  3. Including lib in a lib
    By bibiteinfo in forum C++ Programming
    Replies: 0
    Last Post: 02-07-2006, 02:28 PM
  4. linked list recursive function spaghetti
    By ... in forum C++ Programming
    Replies: 4
    Last Post: 09-02-2003, 02:53 PM
  5. I need help with passing pointers in function calls
    By vien_mti in forum C Programming
    Replies: 3
    Last Post: 04-24-2002, 10:00 AM