C reverse a number recursivly

Question

I have an assigment to create a function that recieves a number, and return the reversed number.

E.G :

Input : 12343 
Output : 34321

No loops allowed, and the input is only the number .

This is what I've tried :

long GetReverse(unsigned long n)
{
    if (n < 10)
        return n % 10;
    else
        return  10 * GetReverse(n / 10) + n % 10;
}

Though This is retuning me the same input and not reversing the number ( I know what is the problem here, I just can't think of a way to do it)

Any thoughts?

EDIT: This is the solution I came up with :

int numOfMulti(unsigned long num) {
    if (num < 10)
        return 1;
    return 10 * numOfMulti(num / 10); 
}

long GetReverse(unsigned long n)
{
    if (n < 10)
        return n % 10; 
    else
        return  n % 10 * numOfMulti(n) + GetReverse(n / 10) ; 
}

Wasn't able to find a solution without a secondary function or static variables.

Answer 1

It's easy. Please try my solution. NO LOOPS, ONE PARAMETER.

long GetReverse(unsigned long n)
{
    static unsigned long m = 0;
    static int recursive_level = 0;
    recursive_level++;
    if (n < 10) {
        recursive_level--;
        m = m * 10 + n;
        int temp = m;
        if (recursive_level == 0) {
            m = 0;
        }
        return temp;
    }
    m = m * 10 + (n % 10);
    GetReverse(n / 10);
    recursive_level--;
    int temp = m;
    if (recursive_level == 0) {
        m = 0;
    }
    return temp;   
 }

Answer 2

You will need to pass 2 elements to the GetReverse function, because the last digit will have to be shifted on the left:

long GetReverse(unsigned long n, unsigned long m)
{
    if (n < 10)
        return 10 * m + n;
    else
        return  GetReverse(n / 10, 10 * m + n % 10);
}

You can then call GetReverse(12343, 0) and get as expected 34321

Answer 3

This is silly and should not be used in real life, but complies with the requirements:

unsigned long GetReverse(unsigned long n)
{
    if (n < 10)
        return n;
    else
        return n % 10 * lround(pow(10,floor(log10(n)))) + GetReverse(n / 10);
}

Answer 4

Here's a solution that only takes one parameter, although you can only use the least significant 32 bits for your input:

uint64_t rev(uint64_t n)
{
    uint32_t _n = n;
    uint32_t _m = n >> 32;
    return _n < 10 
        ? 10 * _m + _n
        : rev(_n / 10 + (uint64_t)(10 * _m + _n % 10) * 65536 * 65536)
    ;
}

int main(){
    uint32_t n = 12345;
    n = rev(n);
}

Essentially the coefficient is stored in the higher order bits of n. In many ways this is a terrible contrivance since all I'm doing is using a single parameter where there should be two parameters, and I'm relying on a (well-defined) narrowing unsigned conversion at the call site! But it does show the elegance of using the fixed width unsigned types.

Answer 5

How about this?

#include <stdio.h>
#include <math.h>

long GetReverse(unsigned long n){
    if (n < 10){
        return n;

    } else {
        unsigned long r = GetReverse(n / 10);          
        int p = snprintf(NULL, 0, "%lu", r);    
        return lround(pow(10, p)) * (n % 10) + r; 
    }
}

int main(void){
    unsigned long n = 112233445566778899;   
    printf("%lu", GetReverse(n));   
    return 0;
}

Answer 6

To place the last digit first you need to multiply it by 10 once for each digit in the number:

#include <math.h>

long GetReverse(unsigned long n)
{
    if (n < 10)
        return n;  // Removed the % 10 as it is not needed when n is < 10
    else {
        long digit = n%10;
        long factor = (long) pow(10, (int)log(n));
        return  digit * factor + GetReverse(n / 10);
    }
}

log and pow is used instead of loops to calculate the number of digits in n. Note that this may fail unless the implementation of pow is good enough. I did a test using gcc (GCC) 4.8.5 20150623 (Red Hat 4.8.5-16) and that combination produced correct results for integer powers of 10 for results that fit in a long.

Answer 7

No loops, no variables, no additional parameters!

---

#include <stdio.h>
unsigned long reverse(unsigned long num)
{
if (num < 10) return num;
if (num < 100) return 10 * (num %10) + reverse(num/10);
if (num < 1000) return 100 * (num %10) + reverse(num/10);
if (num < 10000) return 1000 * (num %10) + reverse(num/10);
if (num < 100000) return 10000 * (num %10) + reverse(num/10);
if (num < 1000000) return 100000 * (num %10) + reverse(num/10);
if (num < 10000000) return 1000000 * (num %10) + reverse(num/10);
if (num < 100000000) return 10000000 * (num %10) + reverse(num/10);
return 100000000 * (num %10) + reverse(num/10);
}

int main(int argc, char **argv)
{
unsigned long num, rev;

if (argc < 2) return 1;
sscanf(argv[1], "%lu", &num);

rev = reverse(num);
printf("%lu -->> %lu\n", num, rev );

return 0;
}

---

Or, using a helper function (not a variable)

[note: this has quadratic complexity(on the number of digits)]

---

unsigned long tencount(unsigned long num)
{
if (num < 10) return 1;
return 10 * tencount( num/10);
}

unsigned long reverse2(unsigned long num)
{
if (num < 10) return num;
return tencount(num) * (num %10) + reverse2(num/10);
}

Answer 8

Assuming a 32bit long you could do it without loops or recursion;

long GetReverse(unsigned long n)
{
    unsigned long x = ((n/1000000000) +
                      ((n/100000000)%10)*10 +
                      ((n/10000000)%10)*100 +
                      ((n/1000000)%10)*1000 +
                      ((n/100000)%10)*10000 +
                      ((n/10000)%10)*100000 +
                      ((n/1000)%10)*1000000 +
                      ((n/100)%10)*10000000 +
                      ((n/10)%10)*100000000 +
                      ((n)%10)*1000000000);

    return (x/(9*(x%10==0)+1)/
            (9*(x%100==0)+1)/
            (9*(x%1000==0)+1)/
            (9*(x%10000==0)+1)/
            (9*(x%100000==0)+1)/
            (9*(x%1000000==0)+1)/
            (9*(x%10000000==0)+1)/
            (9*(x%100000000==0)+1)/
            (9*(x%1000000000==0)+1));
}

Answer 9

This is a solution:

int reverse(int i) {
    static int p = 0;
    if (i==0) { int r = p; p = 0; return r; }
    p = 10*p+i%10;
    return reverse(i/10);
}

Idea is to use a second argument, but as it is used only to store the partial result a static variable can be used. To be able to reuse the function you just need to reset the static at the end of the recursion.

Becareful as such a function is not an involution means that reverse(reverse(x)) not equals to x, think about x=1000. If you want involution then you need to define it over a C-string that represent the value.

Answer 10

C reverse a number recursively

I have an assignment to create a function that receives a number and return the reversed number.
No loops allowed, and the input is only the number .

Add a helper recursive function. @Art
No static variable, no floating point math needed.

The below meets the goals:
1) Recursion used.
2) Function receives a number and return the reversed number
3) No loops allowed, and the input is only the number

#include <stdio.h>
#include <stdlib.h>

static unsigned reverse_helper(unsigned x, unsigned *pow10) {
  if (x < 10) {
    *pow10 = 10;
    return x;
  }
  unsigned y = reverse_helper(x / 10, pow10);
  y += *pow10 * (x%10);
  *pow10 *= 10;
  return y;
}

unsigned reverse(unsigned x) {
  unsigned pow10 = 1;
  unsigned y = reverse_helper(x, &pow10);
  printf("%10u %10u\n", x, y);
  return y;
}

int main(void) {
  reverse(0);
  reverse(9);
  reverse(10);
  reverse(99);
  reverse(100);
  reverse(1234);
  reverse(123456789);
}

Output

         0          0
         1          1
         9          9
        10          1
        99         99
       100          1
      1234       4321
 123456789  987654321

Answer 11

A solution like OP's yet uses 2 recursive functions.

Recurse function with 1 parameter, no floating-point, no static variables.

// return the great power-of-10 less than n
unsigned long p10(unsigned long n) {
  if (n < 10) {
    return 1;
  }
  return p10(n/10) * 10;
}

unsigned long GetReverse(unsigned long n) {
  if (n < 10) {
    return n;
  }
  // OPs code
  //return  10 * GetReverse(n / 10) + n % 10;

  //     v----------------v------------------- scale by 1
  //     |                |   v-----------v--- scale by a power of 10 <= n
  return GetReverse(n / 10) + p10(n)*(n%10);
}

Answer 12

What about calling a function like char* getReverse(int n) So you could use mod and concatenation to obtain the reverse. Then in the caller method int getReverse(int n) you parse the string to int. You could use recursion and then the single line to make the parsing. No loops needed and one parameter.

Answer 13

Here's my completely reentrant version, with no extra variable. It works by using ldiv( num / 10 ) to get quotient and remainder, then returns the remainder multiplied by 10^(num digits in quotient) added to the reverse of the quotient (code is formatted to remove the scroll bar - normally I'd have blank lines and more braces):

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
/* unsigned long power function */
unsigned long lpow( unsigned long base, unsigned long exp )
{
    unsigned long result = 1UL;
    while ( exp )
    {
        if ( exp & 1 )
            result *= base;
        exp >>= 1;
        base *= base;
    }
    return( result );
}

/* count the number of decimal digits */    
unsigned long numdigits( unsigned long num )
{
    return( floor( log10( num ) ) + 1 );
}

unsigned long reverse( unsigned long in )
{
    ldiv_t tmp = ldiv( in, 10UL );
    if ( tmp.quot == 0 )
        return( tmp.rem );
    return( reverse( tmp.quot ) + tmp.rem * lpow( 10, numdigits( tmp.quot ) ) );
}

unsigned long lpow() function from https://stackoverflow.com/a/101613/4756299

unsigned long numdigits() function from https://stackoverflow.com/a/1068870/4756299

Called like this:

int main( int argc, char **argv )
{
    for ( int ii = 1; ii < argc; ii++ )
    {
        unsigned long num = strtoul( argv[ ii ], NULL, 10 );

        printf( "Reverse of %lu is %lu\n", num, reverse( num ) );
    }

    return( 0 );
}

Answer 14

For starters it is unclear why the return type is declared like long while the parameter has the type unsigned long.

long GetReverse(unsigned long n);
^^^^            ^^^^^^^^^^^^^

To have a more large of integers it is better to declare the parameter and the return type like unsigned long long int.

The function can be defined by using a local static variable that will keep the calculated reversed value.

Here it is.

unsigned long long int GetReverse(unsigned long long int n)
{
    const unsigned long long int Base = 10;
    static unsigned long long int reversed;

    unsigned long long int tmp;

    reversed = Base * reversed + n % Base;

    return (n /= Base ) == 0 ? tmp = reversed, reversed = n, n = tmp, n
                             : GetReverse(n);
}

In the demonstrative program below there is shown how the function works.

#include <stdio.h>

unsigned long long int GetReverse(unsigned long long int n)
{
    const unsigned long long int Base = 10;
    static unsigned long long int reversed;

    unsigned long long int tmp;

    reversed = Base * reversed + n % Base;

    return (n /= Base ) == 0 ? tmp = reversed, reversed = n, n = tmp, n
                             : GetReverse(n);
}

int main(void) 
{
    const unsigned long long int Base = 10;

    for ( unsigned long long int i = 1, n = 0; i < Base; i++ )
    {
        n = Base * n + i;

        printf( "%llu\n", n );
        printf( "%llu\n", GetReverse( n ) );
        putchar( '\n' );
    }

    return 0;
}

The program output is

1
1

12
21

123
321

1234
4321

12345
54321

123456
654321

1234567
7654321

12345678
87654321

123456789
987654321