使用递归C删除数组中的特定元素（已解决）

Question

我已经实现了数组结构中给定元素的迭代取消，但是我无法创建递归版本，有帮助吗？

struct array *delete_elem (struct array *q, int val){

    for (int i = 0; i < q->size + 1; i++) {
        if (val == q->A[i].integer) {
            q->size--;
            for (int j = i; j < q->size + 1; j++)
                q->A[j] = q->A[j+1];
        }
    }
    return q;

}

Answer 1

有时很难理解递归。我通常不觉得自己需要它，并且我通常更喜欢迭代方法。话虽这么说，您需要将问题分解为您想要做的事情，这是：

• 扫描数组以搜索值。
• 一旦找到它，“删除”，通过
• 将所有剩余值移动一个空格。

这里是一个例子：

struct array {
   int *values;
   int size;
   int maxSize;
};

void shift( struct array *arr, int to, int from ) {
   if( from >= arr->size ) return; // Done.

   arr->values[to] = arr->values[from];
   return shift( arr, to + 1, from + 1);
}

void recursiveSearchAndDelete( struct array *arr, int value, int index ) {
   if( index >= arr->size ) return; // Didn't find it.

   if( arr->values[index] == value ) {
      // Found it, delete it.
      shift( arr, index, index + 1 );
      arr->size--;
      return;
   }
   return recursiveSearchAndDelete( arr, value, index + 1 );
}

int main() {
   struct array myArray;
   myArray.size = myArray.maxSize = 10;
   myArray.values = (int*)malloc( 10 * sizeof(int) );
   for( int i = 0; i < myArray.size; i++ ) myArray.values[i] = i * 10;

   printf( "Original size: %d\n", myArray.size );
   recursiveSearchAndDelete( &myArray, 50, 0 );
   printf( "New size: %d\n", myArray.size );
   for( int i = 0; i < myArray.size; i++ ) 
      printf( "%d\n", myArray.values[i] );

   return 0;
}

我总是尝试在递归调用函数时尽可能地写return。我们实际上并不关心任何返回值，C编译器已经为您完成了此优化，但是某些其他语言需要return进行tail call，这意味着不会为该创建额外的堆栈条目递归的每一步。这意味着您可以遍历十亿个条目，而不必深入十亿个堆栈条目。

显而易见，递归会在很多时候使函数复杂化。我特别讨厌在各处传递参数以在递归期间保持状态。递归使某些算法更易于理解，而其他算法则较难。查看Fibonacci序列，以获取易于实现的递归函数示例。