Recursion function to determine the right condition out of 4

Question

Write a recursive function that gets an int n and another number f that is between 0 and 3, the function returns 0 or 1 depending on the following conditions:

1. If f=0, the function will return 1 if the sequence (from right to left) is an ascending series Otherwise it will return 0.

2. If f=1, the function will return 1 if the sequence (from right to left) is a descending series Otherwise it will return 0.

3. If f=2, the function will return 1 if the sequence (from right to left) is an ascending series up to a certain number and then it's descending (up to the end of the number) Otherwise it will return 0.

4. If f=3, the function will return 1 if the sequence (from right to left) is a descending series up to a certain number and then it's ascending (up to the end of the number) Otherwise it will return 0.

5. If the number n has two consecutive same numbers, for every f value the function will return 0. For example, for the number 1223 for any f value, the function will return 0.

For example:

For 1234,0 the function returns 0

For 4321,0 the function returns 1

For 1234,1 the function returns 1

For 4321,1 the function returns 0

For 12341,2 the function returns 1

For 412341,2 the function returns 0

For 96589,2 the function returns 0.

For 12341,3 the function returns 0

For 96589,3 the function returns 1

For the number 1223 for any f value, the function will return 0.

I wrote this code but the case for f=2 always returns 1.

    #include <stdio.h>

    int func(int n, int f)
    {

    int zero = 0;
    int* one = &zero;

    if (n < 10)
        return n;

    if((func(n / 10, f) == n % 10)
        return 0;

    switch (f)
    {
    case(0):
        if (func(n / 10, f) > n % 10)     
            return (n % 10);
        else
                return 0;

     case(1):
            if (func(n / 10, f) < n % 10)
                return (n % 10);
            else
                return 0;

    
    case(2):
            if (func(n / 10, f) > n % 10)
                return (n % 10);
            else
                return 0;
                
            if (*one == 0)
                if (func(n / 10, f) < n % 10) 
                {
                    *one++;
                    return (n % 10);
                }
            
    case(3):
        if (func(n / 10, f) < n % 10)
            return (n % 10);
        else
            return 0;
        
        if (*one == 0)
            if (func(n / 10, f) > n % 10) 
            {
                *one++;
                return (n % 10);
            }
     }
    }
    
    int main(void)
    {
        
        //int n=1234, f=0; //should return 0
        //int n=4321, f=0; //should return 1
        //int n=1234, f=1; //should return 1
        //int n=4321, f=1; //should return 0
        //int n=12341, f=2; //should return 1
        //int n=412341, f=2; //should return 0
        //int n=96589, f=2;//should return 0
        //int n=96589, f=3; //should return 1
        //int n=12341, f=3; //should return 0
    
        if (func(n , f) != 0)
            printf("1\n");
        else
            printf("0\n");
        return 0;
    }

Answer 1

There are several issues with your code:

• The function is supposed to return either 0 (false) or 1 (true), but you seem to use return value of the truth case for the actual digit at that recursion step. That could be okay if all digits were positive, because any value except for 0 is considered as "true", but I think 210 should return true for case 0.

• In the cases 2 and 3, you have an additional condition:

      if (func(n / 10, f) > n % 10)
          return (n % 10);
      else
          return 0;
  
      if (*one == 0) ...  // dead code!
  

  The if on that condition won't be reached, because you have already returned 0 or n % 10 earlier. (You also don't catch all possible paths if these coditions, as Bob told you.)

• Your pointer one will not buy you anything, because it is always bound to the same local variable, zero. All occurrences of one are dereferences (*one) and you could replace all of them with just zero. That means that if your condition (*one == 0) were actually reachable, it would always be true.

  I guess your intention was to have a flag that is visible in other recusion steps, but it doesn't work that way. For that to work, you should pass a pointer to some value, so that you can access the same data through it in all recursion steps.)

Okay, let's rewrite this function so that it always returns 0 or 1. First, set up some local variables for the current and next digits and catch the base cases:

int func(int n, int f)
{
    int p = n % 10;
    int q = (n / 10) % 10;

    if (n < 10) return (f < 2);
    if (p == q) return 0;

    // ...
    
    return 0;
}

Now let's consider the first two cases: if the two digits are out of order, you can return 0 immediately. Otherwise, recurse with the rest of the number. You can write this concisely with a single return statement, because the shot-circuiting && ensures that you never recurse when p < q or p > q are false:

    switch (f) {
    case 0:     return (p < q && func(n / 10, f));
    case 1:     return (p > q && func(n / 10, f));
    // ...
    }

Now the other two cases with a peak. Test your conditions as above. When they fail, you have reached the peak and the rest of the digits must be decreasing. Fortunately, you already have a function to check that, nemale cases 0 and 1. So test and recurse while the initial condition holds, otherwise call the appropriate function on the remaining number:

    switch (f) {
    case 0:     return (p < q && func(n / 10, f));
    case 1:     return (p > q && func(n / 10, f));
    case 2:     return (p < q && func(n / 10, f)) || func(n, 1);
    case 3:     return (p > q && func(n / 10, f)) || func(n, 0);
    }

This implementation will treat strictly monotonic numbers which satisfy eiter case 0 or 1 as special cases of cases 2 and 3, where the peak or valley is at the end.

Note that since none of the tests in the switch allow equality, the if (p == q) return 0; is redundant.

Answer 2

There was several issues in your codes : your if (*one == 0) statement was never called. Moreover *one++; didn't do what you think it did, I replaced it by a global variable (it could be replaced by a static variable but I did like this to reset the variable from main).

// Retain inverted status across recursive calls
int inverted = 0;

int func(int n, int f)
{
    if (n < 10) return n;
    int p = func(n / 10, f);  //Recursive call
    
    if (p == n % 10) return 0;
    switch (f)
    {
        case(0):
            if (p > n % 10) return (n % 10);
            else return 0;
        case(1):
            if (p && p < n % 10) return (n % 10);
            else return 0;
        case(2):
            // First clause not called if in inverted segment or if p == 0
            if (inverted == 0 && p && p < n % 10) return (n % 10);
            else {
                if (inverted == 0) inverted = 1;
                // Second segment only called if inverted is true 
                if (inverted && p > n % 10) { return (n % 10);  }
                else return 0;
            }
        case(3):
            // First clause not called if in inverted segment
            if (inverted == 0 && p > n % 10) return (n % 10);
            else {
                if (inverted == 0) inverted = 1;
                // Second segment only called if inverted is true and if p != 0 
                if (inverted && p && p < n % 10) return (n % 10);
                else return 0;
            }
     }
}
int main(void)
{
    int cases[9][2] = {
        {1234, 0}, 
        {4321, 0}, 
        {1234, 1}, 
        {4321, 1}, 
        {12341, 2}, 
        {412341, 2}, 
        {96589, 2}, 
        {96589, 3}, 
        {12341, 3} };
    for (char i=0; i<9; i++) {
        inverted = 0;
        printf("%d ", func(cases[i][0] , cases[i][1]) != 0);
    }
    printf("\n");
    return 0;
}

Output :

0 1 1 0 1 0 0 1 0 

Note that the order of operations is not exactly as you imagine : because of the recursion, the process goes forward instead of backward (the deepest calls occur first).

Answer 3

Few comments:

1. I think it is better to structure the code a bit so that it's more manageable, e.g. separate the program's main control from the functions to detect ascending, descending, ascending_then_descending, etc.
2. It seems to be easier in my opinion to check ascending, descending, etc using string/char *, rather than using math operation (by leveraging the '0' - '9' character as ASCII).

Below sample will only provide the functionality of checking ascending, descending, etc. Please note that the definition in the following code is using left-to-right as sequence (as it normally will). Therefore for your case of right-to-left rule, the string will be reversed before being processed. The good thing about using string is that it is also possible to switch the logic of ascending or descending just by reversing the string. Not sure if you have strict rule allowing only to use integer for processing.

Sample output:

N: 1234, F: 0, Return value: 0, Expected: 0
N: 4321, F: 0, Return value: 1, Expected: 1
N: 1234, F: 1, Return value: 1, Expected: 1
N: 4321, F: 1, Return value: 0, Expected: 0
N: 12341, F: 2, Return value: 1, Expected: 1
N: 412341, F: 2, Return value: 0, Expected: 0
N: 96589, F: 2, Return value: 0, Expected: 0
N: 96589, F: 3, Return value: 1, Expected: 1
N: 12341, F: 3, Return value: 0, Expected: 0

Code:

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

int is_ascending(char *str, int currentIdx, int prevChar);
int is_descending(char *str, int currentIdx, int prevChar);
int is_ascending_then_descending(char *str, int currentIdx, int prevChar, char whichMode);
int is_descending_then_ascending(char *str, int currentIdx, int prevChar, char whichMode);

//===================== Helper Function ======================
void inplace_reverse(char *str);
char* my_itoa(int val, int base);

int main() {
    int RetVal=-1, Expected = -1;
    int N=0, F=0;

    //Ascending
    N = 1234, F=0, Expected = 0;
    char *input1 = my_itoa(N, 10);
    inplace_reverse(input1);
    RetVal = is_ascending(input1, 0, 0);
    printf("N: %d, F: %d, Return value: %d, Expected: %d\n", N, F, RetVal, Expected);

    N = 4321, F=0, Expected = 1;
    char *input2 = my_itoa(N, 10);
    inplace_reverse(input2);
    RetVal = is_ascending(input2, 0, 0);
    printf("N: %d, F: %d, Return value: %d, Expected: %d\n", N, F, RetVal, Expected);

    //Descending
    N = 1234, F=1, Expected = 1;
    char *input3 = my_itoa(N, 10);
    inplace_reverse(input3);
    RetVal = is_descending(input3, 0, 0);
    printf("N: %d, F: %d, Return value: %d, Expected: %d\n", N, F, RetVal, Expected);

    N = 4321, F=1, Expected = 0;
    char *input4 = my_itoa(N, 10);
    inplace_reverse(input4);
    RetVal = is_descending(input4, 0, 0);
    printf("N: %d, F: %d, Return value: %d, Expected: %d\n", N, F, RetVal, Expected);

    //Ascending & then Descending
    N = 12341, F=2, Expected = 1;
    char *input5 = my_itoa(N, 10);
    inplace_reverse(input5);
    RetVal = is_ascending_then_descending(input5, 0, 0, 'a');
    printf("N: %d, F: %d, Return value: %d, Expected: %d\n", N, F, RetVal, Expected);

    N = 412341, F=2, Expected = 0;
    char *input6 = my_itoa(N, 10);
    inplace_reverse(input6);
    RetVal = is_ascending_then_descending(input6, 0, 0, 'a');
    printf("N: %d, F: %d, Return value: %d, Expected: %d\n", N, F, RetVal, Expected);

    N = 96589, F=2, Expected = 0;
    char *input7 = my_itoa(N, 10);
    inplace_reverse(input7);
    RetVal = is_ascending_then_descending(input7, 0, 0, 'a');
    printf("N: %d, F: %d, Return value: %d, Expected: %d\n", N, F, RetVal, Expected);

    //Descending & then Ascending
    N = 96589, F=3, Expected = 1;
    char *input8 = my_itoa(N, 10);
    inplace_reverse(input8);
    RetVal = is_descending_then_ascending(input8, 0, 999, 'd');
    printf("N: %d, F: %d, Return value: %d, Expected: %d\n", N, F, RetVal, Expected);

    N = 12341, F=3, Expected = 0;
    char *input9 = my_itoa(N, 10);
    inplace_reverse(input9);
    RetVal = is_descending_then_ascending(input9, 0, 999, 'd');
    printf("N: %d, F: %d, Return value: %d, Expected: %d\n", N, F, RetVal, Expected);

    return 0;
}

// ========================= Main Functionality ==========================
//Return 1 if str is Ascending from left to right; otherwise return 0
int is_ascending(char *str, int currentIdx, int prevChar) {
    char current = str[currentIdx];
    if (current == '\0') {
        return 1;
    } else {
        if (current > prevChar) {
            return is_ascending(str, currentIdx+1, current);
        } else {
            return 0;
        } //end else
    } //
}

//Return 1 if str is Descending from left to right; otherwise return 0.
//Re-use the 'is_asscending' function by reversing the string first
int is_descending(char *str, int currentIdx, int prevChar) {
    inplace_reverse(str);
    return is_ascending(str, currentIdx, prevChar);
}

//Return 1 if str is Ascending and then Descending (from left to right); otherwise return 0.
int is_ascending_then_descending(char *str, int currentIdx, int prevChar, char whichMode) {
    char current = str[currentIdx];
    if (current == '\0') {
        return 1;
    } else {
        if (current > prevChar) {
            if (whichMode == 'a') {
                return is_ascending_then_descending(str, currentIdx+1, current, whichMode);
            } else { //mode is already in Descending, but current > prevChar
                return 0;
            } //end else
        } else { //current <= prevChar
            if (whichMode == 'a') {
                return is_ascending_then_descending(str, currentIdx+1, current, 'd'); //switch to descending mode
            } else { //mode is already in Descending, current <= prevChar
                if (current < prevChar) {
                    return is_ascending_then_descending(str, currentIdx+1, current, 'd');
                } else { //current == prevChar
                    return 0;
                }
            } //end else
        } //end else
    } //
}

//Return 1 if str is Descending and then Ascending (from left to right); otherwise return 0.
int is_descending_then_ascending(char *str, int currentIdx, int prevChar, char whichMode) {
    char current = str[currentIdx];
    if (current == '\0') {
        return 1;
    } else {
        if (current < prevChar) {
            if (whichMode == 'd') {
                return is_descending_then_ascending(str, currentIdx+1, current, whichMode);
            } else { //mode is already in Ascending, but current < prevChar
                return 0;
            } //end else
        } else { //current >= prevChar
            if (whichMode == 'd') {
                return is_descending_then_ascending(str, currentIdx+1, current, 'a'); //switch to ascending mode
            } else { //mode is already in Ascending, current <= prevChar
                if (current > prevChar) {
                    return is_descending_then_ascending(str, currentIdx+1, current, 'a');
                } else { //current == prevChar
                    return 0;
                }
            } //end else
        } //end else
    } //
}

//============================= Helper Function ==============================
//reverse the given null-terminated string in place
//From: https://stackoverflow.com/questions/784417/reversing-a-string-in-c
void inplace_reverse(char *str) {
  if (str) {
    char *end = str + strlen(str) - 1;

    // swap the values in the two given variables
    // XXX: fails when a and b refer to same memory location
#   define XOR_SWAP(a,b) do\
    {\
      a ^= b;\
      b ^= a;\
      a ^= b;\
    } while (0)

    // walk inwards from both ends of the string,
    // swapping until we get to the middle
    while (str < end)
    {
      XOR_SWAP(*str, *end);
      str++;
      end--;
    }
#   undef XOR_SWAP
  }
}

char* my_itoa(int val, int base) {
    static char buf[32] = {0};
    int i = 30;
    for(; val && i ; --i, val /= base)
        buf[i] = "0123456789abcdef"[val % base];

    return &buf[i+1];
}