How to remove neighbouring duplicate in array using recursion?

Question

I have made the following function that will remove the neighboring duplicate. How to implement it using recursion??

example 1,1,5,4,7,7,9,9,8 will result to 1, 5, 4, 7, 9, 8

void remove() {
  int arr[9]={1,1,5,4,7,7,9,9,8};
  int newarr[9];
  int counter=0;

  for(int i = 0; i < 9; i++) {
    if(arr[i] == arr[i + 1]) {
      newarr[counter] = arr[i];
      i += 1;
      counter++;
    } else {
      newarr[counter] = arr[i];
      counter++;
    }
  }

  for(int z = 0; z < counter; z++){
    printf("%d ", newarr[z]);
  }
}

Hint: Begin with a small example using a pencil and a paper. After understanding how the recursion works, try to implement it. If you fail, we're here to help! — Maroun
– Maroun, Commented Nov 5, 2015 at 9:26

Vlad from Moscow · Accepted Answer · 2015-11-06 09:53:14Z

2

First of all your program has undefined behaviour because it tries to access memory beyond the array in the loop when i is equal to 8.

  for(int i = 0; i < 9; i++) {
    if(arr[i] == arr[i + 1]) {
                     ^^^^^^

The element with index equal to 9 (arr[8 + 1]) does not exist.

Moreover the logic is wrong. You are incrementing i twice when arr[i] is equal to arr[i+1]

  for(int i = 0; i < 9; i++) {
                        ^^^^
    if(arr[i] == arr[i + 1]) {
      newarr[counter] = arr[i];
      i += 1;
      ^^^^^^
      counter++;
    } else {

but the next element with index arr[i+2] also can be equal to arr[i]. So the same value will be written at least twice in the destination array.

Try for example to apply your program to an array like this

int arr[] = { 1, 1, 1, 1, 1, 1 };

So you need to rewrite your program entirely.:)

As for the recursive function then it can look the following way

#include <stdio.h>

int * unique( const int *a, size_t n, int *b )
{
    if ( n == 0 ) return b;

    if ( n == 1 || a[0] != a[1] ) *b++ = *a;        

    return unique( a + 1, n - 1, b );
}

int main( void )
{
    int a[] = { 1, 1, 5, 4, 7, 7, 9, 9, 8 };
    const size_t N = sizeof( a ) / sizeof( *a );

    for ( size_t i = 0; i < N; i++ ) printf( "%d ", a[i] );
    printf( "\n" );

    int b[N];

    int *last = unique( a, N, b );

    for ( int *first = b; first != last; ++first ) printf( "%d ", *first );
    printf( "\n" );
}

Its output is

1 1 5 4 7 7 9 9 8 
1 5 4 7 9 8

If you compiler does not support the C99 STandard then the program can look like

#include <stdio.h>

int * unique( const int *a, size_t n, int *b )
{
    if ( n == 0 ) return b;

    if ( n == 1 || a[0] != a[1] ) *b++ = *a;        

    return unique( a + 1, n - 1, b );
}

#define N 9

int main( void )
{
    int a[N] = { 1, 1, 5, 4, 7, 7, 9, 9, 8 };
    int b[N];
    size_t i;
    int *first, *last;

    for ( i = 0; i < N; i++ ) printf( "%d ", a[i] );
    printf( "\n" );

    last = unique( a, N, b );

    for ( first = b; first != last; ++first ) printf( "%d ", *first );
    printf( "\n" );
}

edited Nov 6, 2015 at 9:53

answered Nov 5, 2015 at 9:51

Vlad from Moscow

313k27 gold badges204 silver badges358 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Vlad from Moscow Over a year ago

@quickbrownfox Show the statement for which the error is issued.

beginner Over a year ago

on line 17 improper use of typedef 'size_t' on line 17 for statement missing ;

Vlad from Moscow Over a year ago

@quickbrownfox It seems you missed a semicolon. Can you simply copy and paste the code?

Vlad from Moscow Over a year ago

@quickbrownfox It seems you have an old C compiler or you did not specify that the compiler should follow the C88 Standard. Remove the definition of N. Instead place directive before main #define N 9 (neither semicolon after the directive), Then declare arrays a and b like int a[N] = { /*..*/}; int b[N];

Vlad from Moscow Over a year ago

@quickbrownfox Then after the array definitions insert definition size_t i; and in the loop write for ( i = 0; i < N; i++ ) /*...*/. Also declaration of pointer first also place in the beginning of the main.

Collectives™ on Stack Overflow

How to remove neighbouring duplicate in array using recursion?

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related