How can i fix this (is_sorted) , recursive function?

Question

How can i fix this (is_sorted) , recursive function? Target: This function takes a string as a input parameter and returns TRUE if characters in the string are in alphabetical ascending order; returns FALSE otherwise. Characters can be lowercase or uppercase.

#include<stdio.h>
#define SIZE 50
typedef enum{FALSE,TRUE} Bool;

Bool is_sorted(const char *str);

int main(){

    char arr1[SIZE]="aSTYoLPNDeSaFAE";  
    char arr2[SIZE]="aGjklOvz";

    if(is_sorted(arr1)==TRUE){
        printf("arr1 (is_sorted) Yes \n");
    }
    else
    {
        printf("arr1 (is_sorted) No \n");
    }

    if(is_sorted(arr2)==TRUE){
        printf("arr2 (is_sorted) Yes \n");
    }
    else
    {
        printf("arr2 (is_sorted) No \n");
    }

    return 0;
}

Bool is_sorted(const char *str){
    if(str[0]=='\0'){
        return FALSE;
    }
    else if(strcmp(&str[0],&str[1])<0)
    {
        return TRUE;
    }
    else
    {
        return FALSE;
    }

    return is_sorted(&str[1]);
}

What is the specific problem you encountered? Did you run through debugger? — Petar Minchev, Apr 18 '15 at 16:02
I'm using gcc in ubuntu. There is a logic error, because arrays encounter the value of FALSE from is_sorted function. Second array need to return TRUE value. — us23, Apr 18 '15 at 16:07
You aren't handling the lowercase and uppercase thing with strcmp. — Petar Minchev, Apr 18 '15 at 16:10
This version do not include library. Please assume that this library above. How can i solve this recursively? — us23, Apr 18 '15 at 16:11
I couldn't think that upper / lower control as a recursive. I have an option with (int) cast ASCII, but it sounds not logic with recursive. I'm not sure. — us23, Apr 18 '15 at 16:15
The problem is not in the recursion. All lowercase letters have greater ascii codes than the uppercase letters, that's why 'a' > 'G'. Try using toupper function to convert both to uppercase before comparing them. — Petar Minchev, Apr 18 '15 at 16:21
I find your is_sorted a mess! You use strcmp to compare "characters" and is_sorted is never called. Think before you write would be a good advice. See solution by Maciej. — Paul Ogilvie, Apr 18 '15 at 16:28

Maciej Nowicki · Answer 1 · 2015-04-18T16:54:53.283

1

The correct is_sorted function in your program should look like this:

#include <ctype.h>
#include <stdio.h>

Bool is_sorted(const char *str){
    if(str[0]=='\0'){
        return TRUE; //the string is empty
    }
    else if(str[1]=='\0'){
        return TRUE; //the string contains only one character or all letters before NULL are in correct order
    }
    else if(tolower(str[0])<tolower(str[1])))
    {
        return is_sorted(&str[1]); //current and next letter are in correct order
    }
    else
    {
        return FALSE; //current and next letter are in wrong order, thus whole string is not sorted
    }
}

edited Apr 18 '15 at 16:54

answered Apr 18 '15 at 16:25

Maciej Nowicki

237
1
13

1

You should also check if `str[1]` is `\0` or it won't work correctly, check: http://ideone.com/FpA4sq – AliciaBytes Apr 18 '15 at 16:50
Yes, you are right - i didn't takie this case into consideration (I have prepared my solution without compiling ;) ). I've edited my post. – Maciej Nowicki Apr 18 '15 at 16:52

score 1 · Accepted Answer · answered Apr 18 '15 at 16:36

I see 3 problems within your code, let me first explain the problems in your code before showing a working solution.

First off:

if(str[0]=='\0'){
    return FALSE;
}

Why would a empty string not be sorted? Which elements are out of order? After all it's empty.

Next you don't handle upper/lower case correctly:

if(strcmp(&str[0],&str[1])<0)

strcmp compares the ascii values. Upper case letters got lower values than lower case letters. That means strcmp("G", "a")<0 would return true. You really want to compare lowercase letters. You're also comparing strings not letters.

Lastly you never get to your recursive call.

if(str[0]=='\0'){
    return FALSE;
}
else if(strcmp(&str[0],&str[1])<0)
{
    return TRUE;
}
else
{
    return FALSE; // return if you didn't return in any other condition
}

return is_sorted(&str[1]); // You never get here.

Now as for my solution:

Bool is_sorted(const char *str){
    if(str[0]=='\0' || str[1] == '\0'){
        return TRUE; // A single character as well as a empty string are
    }                // by definition sorted already.
    else if(tolower(str[0]) < tolower(str[1))
    {
        return is_sorted(str + 1); //First two characters are sorted we got to check
    }                            // if the rest are sorted too.
    else
    {
        return FALSE; // If the first two characters aren't sorted the whole
    }                 // string isn't sorted.
}

Thanks all of your explanations. I want to ask a particular thing about: return is_sorted(str + 1); || return is_sorted(&str[1]); same thing, isn't it? — us23, Apr 18 '15 at 16:56
Yes, it's completely the same. In both cases you move 1 character forward in the string. — AliciaBytes, Apr 18 '15 at 17:02
By the way, Could you advice me a specific pdf, website,channel about thinking recursively and examples? I'm a student, I need to improve myself about recursion. — us23, Apr 18 '15 at 17:42
In my opinion the best exercise for recurion is writing a Determinant of a Matrix calculator or fibonacci sequence calculator - these are 2 algorithms that have perfect mathematical explanation that includes recursion. Good luck! — Maciej Nowicki, Apr 18 '15 at 17:56
@us23 I don't really know a good tutorial of the top of my hat, maybe try http://stackoverflow.com/a/717839 Otherwise fibonacci was mentioned already which is commonly used for explsining recursion. For me personally I really understood it when I implemented multiple sorting algorithms myself, especially merge-sort. It's a bit harder than fibonacci though. — AliciaBytes, Apr 18 '15 at 18:23

How can i fix this (is_sorted) , recursive function?

2 Answers2