Recursive function in C to determine if digits of an integer are sorted ascending, descending or neither

Question

I need to write a recursive function that returns 1 if digits of a whole number are ascending (left to right), return -1 if descending or return 0 if neither.

My solution attempt returns 0 every time and I know why but I don't know how to get around it.

Here's my code:

#include <stdio.h>

int check_order(int n)
{
    if (n % 10 > n / 10 % 10)
    {
        return check_order(n / 10);
        if (n == 0)
        {           
            return 1;
        }
    }
    else if (n % 10 < n / 10 % 10)
    {
        return check_order(n / 10);
        if (n == 0)
        {
            return -1;
        }
    }
    else
    {
        return 0;
    }
}

int main()
{
    int n;
    printf("enter a whole number (n > 9):");
    scanf_s("%d", &n);
    printf("function returned: %d\n", check_order(n));
}

Answer 1

Here's a simple recursion:

int f(int n){
  if (n < 10)
    return 0;

  int dr = n % 10; // rightmost digit
  n = n / 10;
  int dl = n % 10; // second digit from the right 
  int curr = dl < dr ? 1 : -1; // current comparison 
  if (dl == dr) curr = 0; // keep strict order

  if (n < 10)
    return curr;

  return curr == f(n) ? curr : 0; // are the comparisons consistent?
}

Answer 2

Code after a return statement like this is unreachable:

return check_order(n / 10);
if (n == 0)
{
    return -1;
}

Beyond this, you're on the right track of checking the current digit against the next digit, but I don't see a clear base case (when n < 10, that is, a single digit).

Trying to check ascending and descending in one recursive function is difficult to manage. In particular, communicating state between stack frames and determining which cases are still valid at a given call suggests that the return value is overworked.

To save having to return a struct or use an enum or magic numbers as flags, I'd write two general helper functions, ascending_digits and descending_digits.

#include <stdbool.h>
#include <stdio.h>

bool ascending_digits(int n) {
    if (n < 10) return true;
    if (n % 10 < n / 10 % 10) return false;
    return ascending_digits(n / 10);
}

bool descending_digits(int n) {
    if (n < 10) return true;
    if (n % 10 > n / 10 % 10) return false;
    return descending_digits(n / 10);
}

int check_order(int n) {
    if (ascending_digits(n)) return 1;
    if (descending_digits(n)) return -1;
    return 0;
}

int main() {
    printf("12345: %d\n", check_order(12345));
    printf("54321: %d\n", check_order(54321));
    printf("54323: %d\n", check_order(54323));
    printf("454321: %d\n", check_order(454321));
    printf("1: %d\n", check_order(1));
    printf("12: %d\n", check_order(12));
    printf("21: %d\n", check_order(21));
    return 0;
}

Output:

12345: 1
54321: -1
54323: 0
454321: 0
1: 1
12: 1
21: -1

Not only are these functions easier to understand and maintain individually, they're also more reusable than if they were inseparably tied together.

This doesn't handle negative numbers--you could apply abs and go from there if you want. Same goes for handling equal values; this implementation accepts numbers such as 1223 but you could use <= to enforce strict ordering.

Answer 3

A version that works for any length since it takes the string as parameter. And feeding the recursive function with previous status (ascending or descending) allows for some shorter code and less functions.

int check_order(char *str, int index, int previous) {
     char current = str[index];       // char at index
     char next = str[index+1];        // char at index+1
     if (current == 0 || next == 0) {
          return previous;            // End of string
     }
     // Ascending or descending?
     int status = next > current ? 1 : (next < current ? -1 : 0); 
     if (status == 0 || index > 0 && status != previous) {
          // If neither -1/1 nor status == previous (while not initial call)
          return 0;
     }
     return check_order(str, index+1, status); // Check from next index
}

The main function must ensure the string is at least 2 chars

int main(int argc, char **argv) {
     char *str = *++argv;
     // Some optional checks on str here... (like this is a number)
     int status = 0; // Default value if string length < 2
     if (strlen(str) >= 2) {
        status = check_order(str, 0, 0);
     }
     printf("Check order for %s is %d\n", str, status);
     return 0;
}

Answer 4

I think you were started on the right track but need to flesh out your code more. My solution borrows on that of @ChuckCottrill as I like his enum but I don't like that he doesn't play the ball as it lays (i.e. converts to a string instead of dealing with the int.) I also borrow the nice test examples of @ggorlen but I don't like that solution either as it can take multiple passes through the number to figure out the answer when only one pass should be needed:

#include <stdio.h>

typedef enum { descending=-1, other=0, ascending=1 } order_t; // a la @ChuckCottrill

order_t check_order(int n)
{
    if (n > 9) {
        int right = n % 10;
        int left = n / 10 % 10;

        if (right > left) {
            n /= 10;

            if (n > 9) {
                return (ascending == check_order(n)) ? ascending : other;
            }

            return ascending;
        }

        if (right < left) {
            n /= 10;

            if (n > 9) {
                return (descending == check_order(n)) ? descending : other;
            }

            return descending;
        }
    }

    return other;
}

int main() { // a la @ggorlen
    printf("12345: %d\n", check_order(12345));
    printf("54321: %d\n", check_order(54321));
    printf("54323: %d\n", check_order(54323));
    printf("454321: %d\n", check_order(454321));
    printf("1: %d\n", check_order(1));
    printf("12: %d\n", check_order(12));
    printf("21: %d\n", check_order(21));
}

OUTPUT

> ./a.out
12345: 1
54321: -1
54323: 0
454321: 0
1: 0
12: 1
21: -1
> 

Answer 5

Explain your algorithm?

Suppose you use the following:

• You are given a number.
• You need to turn that number into a sequence of digits.
  • If you are given a number, you can convert that number to a sequence of digits.
  • If you are given a sequence of digits, use that.
• Compare each pair of digits -> ascending, descending, or neither.
• Combine the results from each pair, sequentially/recursively.

We can use a string to make the digit comparisons easier, and accept very long sequences of digits.

We can use an enum(erated) type to represent the ordering.

How do you combine the results? Define a function that combines the order of two adjacent, overlapping pairs, then you can combine results.

#include <stdio.h>
#include <string.h>

typedef enum { descending=-1, other=0, ascending=1 } order_t;

order_t pair_order(int a, int b) {
    if( a < b ) return ascending;
    if( a > b ) return descending;
    return other;
}

//strict (increasing/decreasing)
order_t strict_order( order_t x, order_t y ) {
    if( x == y ) return x;
    return other;
}

//monotone (increasing/decreasing)
order_t monotone_order( order_t x, order_t y ) {
    if( x == y ) return x;
    if( other == x ) return y;
    if( other == y ) return x;
    return other;
}

order_t check_order( char* p, int remain ) {
    //printf("p:%s\n",p); //uncomment to watch progress
    if( remain<2 ) return other;
    if( remain==2 ) return pair_order(p[0], p[1]);
    return strict_order( pair_order(p[0], p[1]), check_order(p+1, remain-1) );
    //return monotone_order( pair_order(p[0], p[1]), check_order(p+1, remain-1) );
}

char* order_name[] = {
    "descending",
    "other",
    "ascending"
    ""
};

int main()
{
    char line[666] = "none";
    while ( strlen(line) > 0 ) {
    printf("enter a number (at least 2 digits):");
    fgets(stdin,line,sizeof(line)-1);
    if( strlen(line) > 0 && line[strlen(line)-1] == '\n' )
        line[strlen(line)-1] = '\0';
    order_t order = check_order(line);
    printf("function returned: (%d)%s\n", order, order_name[order+1]);
    }
}