recursive itoa

This is a discussion on recursive itoa within the C Programming forums, part of the General Programming Boards category; Ok, so i was writing a recursive version of itoa. Im interested if there's a way to avoid using static ...

  1. #1
    Registered User
    Join Date
    Jul 2009
    Location
    Croatia
    Posts
    272

    recursive itoa

    Ok, so i was writing a recursive version of itoa. Im interested if there's a way to avoid using static variable: this is what i came up with.

    "Write a recursive version of itoa".

    Code:
    void itoa(int n, char s[])
    {
         static int i = 0;
         
         if(n < 0) {
              s[i++] = '-';
         }
         
         if(n / 10 != 0)
             itoa(n/10, s);
         else if(n < 0)
             i = 1;
         else
             i = 0;
             
         s[i++] = abs(n % 10) + '0';
         s[i] = '\0';
    
    }

  2. #2
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,246
    You should be able to avoid the recursion if you just incremented 's' instead of indexing it.
    bit∙hub [bit-huhb] n. A source and destination for information.

  3. #3
    Registered User
    Join Date
    Jul 2009
    Location
    Croatia
    Posts
    272
    Yes. But thats an exercise in K&R that explicitly says to write it recursively.

    So, is there a way to write a recursive version without the static?

  4. #4
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    Sure, if you use helper functions. Here's an example. I'm afraid it's not very nicely coded.
    Code:
    #include <stdio.h>
    
    int my_itoa_r(int n, char *s, int digit) {
        int d, max;
        
        if(n == 0) {
            s[digit] = 0;
            return digit;
        }
        
        d = n % 10;
        max = my_itoa_r(n / 10, s, digit + 1);
        s[max - digit - 1] = d + '0';
        
        return max;
    }
    
    void my_itoa(int n, char *s) {
        my_itoa_r(n, s, 0);
    }
    
    int main() {
        char buffer[BUFSIZ];
        int number = 123456;
        
        my_itoa(number, buffer);
        printf("itoa(%d) = \"%s\"\n", number, buffer);
        
        return 0;
    }
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    int myitoa( char *s )
    {
        if( s && *s && isdigit(*s) )
        {
            int n = *s - '0', l = 1, r = myitoa( s + 1 );
            while( r / l ) l *= 10;
            return n * l + r;
        }
        return 0;
    }
    You can add support for sign checking, but there's the general idea.


    Quzah.
    Hope is the first step on the road to disappointment.

  6. #6
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    Slightly nicer version. Maybe not as nice as quzah's, but at least this is O(n).
    Code:
    #include <stdio.h>
    
    void my_itoa_r(int n, char **s) {
        if(n == 0) return;
        
        my_itoa_r(n / 10, s);
        **s = n % 10 + '0';
        (*s) ++;
    }
    
    void my_itoa(int n, char *s) {
        my_itoa_r(n, &s);
        *s = 0;
    }
    
    int main() {
        char buffer[BUFSIZ];
        int number = 123456;
        
        my_itoa(number, buffer);
        printf("itoa(%d) = \"%s\"\n", number, buffer);
        
        return 0;
    }
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  7. #7
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,246
    Quote Originally Posted by Tool View Post
    Yes. But thats an exercise in K&R that explicitly says to write it recursively.

    So, is there a way to write a recursive version without the static?
    Oops, I meant to say "static" instead of "recursion". Oh well, there are plenty of examples from others.
    bit∙hub [bit-huhb] n. A source and destination for information.

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    I got mine backwards. Mine is atoi. Sorry, was on the phone.

    Quzah.
    Hope is the first step on the road to disappointment.

  9. #9
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Communicating back through a double-pointer is kind of cheating IMHO, because it's not possible in most functional languages where you would actually write recursive routines like this.

    Code:
    char *itoa( int n, char *s )
    {
    	if( n == 0 ) return s;
    	*( s = itoa( n / 10, s ) ) = n % 10 + '0';
    	return s + 1;
    }
    
    void itoa_wrapper( int n, char *s )
    {
    	if( n == 0 ) strcpy( s, "0" );
            else if( n < 0 ) { *s = '-'; itoa_wrapper( -n, s + 1 ); }
    	else *itoa( n, s ) = 0;
    }
    edited to handle negatives
    Last edited by brewbuck; 12-30-2009 at 05:22 PM.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  10. #10
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    @quzah: Strangely, I too started writing an atoi() before I realized my mistake.

    quzah's idea can, of course, be used to write an itoa() as well. It's just really inefficient. (Of course, since we're writing this recursively, we're probably not too concerned about efficiency . . . .)

    I like brewbuck's solution best. Reading it made me realize that you need a helper function, though, because otherwise you can't know to turn 0 into "0" and not "", as far as I can tell.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. recursive function
    By technosavvy in forum C Programming
    Replies: 1
    Last Post: 02-29-2008, 04:42 AM
  2. difference between recursive and iterative
    By Micko in forum C Programming
    Replies: 33
    Last Post: 07-06-2004, 09:34 PM
  3. Algorithm help (Changing from Recursive to Non Recursive)
    By Thantos in forum C++ Programming
    Replies: 1
    Last Post: 04-25-2004, 07:27 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. How to change recursive loop to non recursive loop
    By ooosawaddee3 in forum C Programming
    Replies: 1
    Last Post: 06-24-2002, 08:15 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21