Thread: recursive remove duplicates from a string

//do nothing and return

is only a comment - it does NOT make function return

computer does only what you TELL him to do, not what you want him to do

ye i know its what laser light said
in the base case
"do nothing and return"
so i left empty cols

i assumed thats what she ment

Originally Posted by transgalactic2

ye i know its what laser light said
in the base case
"do nothing and return"
so i left empty cols

i assumed thats what she ment

It means - you need to add return statement to actually force your function to return at this point

ye i know its what laser light said
in the base case
"do nothing and return"

I have been generous to spell out the algorithm that I had in mind and implemented myself. You need to think about what the algorithm does and how it works, and from there implement the code, not blindly implement it. You cannot expect someone to provide you with the algorithm all the time, and my intention was to give you some idea of how it might be accomplished so that you can learn to construct such algorithms yourself.

That said, if you had blindly implemented the algorithm I outlined you would have written:

Code:

if (string[index]=='\0')
{
    return;
}

But why do that when you can negate the condition?

Code:

void remove_duplicates(char string[], int index)
{
    int flag = -1;
    if (string[index] != '\0')
    {
        flag = has_duplicate(string, index, string[index]);
        if (flag == 1)
        {
            overwrite(string, index);
            remove_duplicates(string, index);
        }
        else
        {
            remove_duplicates(string, index + 1);
        }
    }
}

Note that the flag variable is unnecessary since you can check the return value of has_duplicate with:

Code:

if (has_duplicate(string, index, string[index]))

EDIT:
Oh, and I notice a slight but critical mistake in your call of has_duplicate: you need to use has_duplicate to check the part of the string before the current character. You are checking it before and including the current character.

there is no return in a void function

It could not return value.

It still could use return statement to return control to the calling funtion

Your has_duplicate function is incorrect since there is one control path where you do not return a value. The compiler warned you about that, didn't it?

if you exit your input loop on the i < 255 condition -
your assignment
input[i] = '\0';

will be out-of bounds access

on first call to remove_duplicates it will call has_duplicate
with index == 0 and passing string[0] as character.

has_duplicate will check that the char matches itself - and return 1 (I suppose you will return this char - effectivly emptying all your string)

i forgot to implement this last pat
"else you call has_duplicate() for the previous character and return the return value of that recursive call."

on this function:

Code:

int has_duplicate(char string[], int index, char ch)
{
    int check;
	if (index<0)
	{
       return 0;
	}
    if (ch==string[index])
    {
      return 1;
    }
	else
	{
           check=has_duplicate(string,index-1,ch);
           return check;
	}
	
   
}//end func

now dont have any warnings
but i still dont have any output.
??

Code:

#include <stdio.h>
void remove_duplicates(char string[], int index);
void overwrite(char string[], int index);
int has_duplicate(char string[], int index, char ch);


int main()
{
	int i,ch;
	char input[255];
	printf("enter string\n");
 for (i = 0; i < 255 && (ch = getchar()) != '\n' && ch >=0; ++i)
    {
        input[i] = ch;
    }

    input[i] = '\0';
    remove_duplicates(input,0);
	printf("%s",input);

   return 0;
}


void remove_duplicates(char string[], int index)
{
    int flag = -1;
    if (string[index] != '\0')
    {
        flag = has_duplicate(string, index, string[index]);
        if (flag == 1)
        {
            overwrite(string, index);
            remove_duplicates(string, index);
        }
        else
        {
            remove_duplicates(string, index + 1);
        }
    }
}



int has_duplicate(char string[], int index, char ch)
{
       int check;
	if (index<0)
	{
           return 0;
	}
        if (ch==string[index])
        {
            return 1;
        }
	else
	{
           check=has_duplicate(string,index-1,ch);
	   return check;
	}
	
   
}//end func


void overwrite(char string[], int index)
{
     
	if ( string[index]=='\0')
	 {
             return;
	 }
          if( string[index]!='\0')
	 {
		 string[index]=string[index+1];
	        overwrite(string,index+1);
	 }
	 
}

The problem is here:

Code:

flag = has_duplicate(string, index, string[index]);

Read my edit to post #36 and vart's post #40.

Remember, you are trying to determine if there is a match with the current character. The current character is string[index], so passing string[index-1] is wrong. The problem is that you pass index as the second argument. This means that has_duplicate searches the part of the string from the first character to the current character... and so it will always return 1, causing the current character to be removed whether or it is a duplicate. As such, you should pass index - 1.