c++ - 实现递归函数

Question

我对递归还是很陌生，我想从这个数组int arr[size] = {21, -6, 3, 5, 5, -3, 6, -21}中返回 3，因为它具有与递归实现相同的绝对值。

但是，我得到的值为 0。我无法确定是什么导致该程序没有带来预期的价值。

#include <iostream>

using namespace std;

int additive_inverse_opposite_pairs_count(int* arr, int n) {
  int size = n;

  if (n == 0) {
    if (arr[n] == -1 * arr[size - 1 - n])
      return 1;
    else
      return 0;
  } else {
    int count = additive_inverse_opposite_pairs_count(arr, n - 1) + count;
    if (arr[n] == -1 * arr[size - 1 - n]) {
      count += 1;
    } else
      count = 0;
    return count;
  }
}

int main() {
  int size = 8;
  int arr[size] = {21, -6, 3, 5, 5, -3, 6, -21};
  int value = 0;

  value = additive_inverse_opposite_pairs_count(arr, size);
  cout << "value: " << value << endl;

  return 0;
}

标签： c++recursion

Answer 1

部分问题是您正在访问数组的大小在arr[n]哪里。n数组的有效索引是0..n-1，因此您需要在语句的一部分中更改arr[n]为。arr[n-1]elseif

一个想法是简单地从一个 index 开始，i从该点开始扫描数组的其余部分以查找加法逆，如果找到，则返回该数字，否则进一步递归到数组中。我写了一个辅助函数来完成这项工作。

int helper(int* arr, int i) {
  if (i == 0) {
    return 0;
  }
  for (int j = i - 1; j >= 0; j--) {
    if (arr[i] == -arr[j]) {
      return abs(arr[i]);
    }
  }
  return helper(arr, i - 1);
}

int additive_inverse_opposite_pairs_count(int* arr, int n) {
  return helper(arr, n - 1);
}