Рекурсия C ++ для выбора между двумя значениями в массиве

Question

Я пытаюсь создать функцию, которая может увеличивать на один или два шага вперед (в зависимости от того, какой индекс содержит меньшее целое число) в массиве, чтобы перейти к последнему значению с помощью рекурсии. Это для задания, и я работал больше дня, чтобы попытаться понять это. Поэтому я не прошу фактический код для этого, но ищу, что не так в коде, который у меня есть. Я собрал функцию, которая работает, но делает это постепенно.

int findLowestSum(int arr[], int low, int high, int arrSize) {
    int minVal = 0;
    while (high < arrSize) {

        if (arr[low] < arr[high]) {
            minVal += arr[low];
            low += 1;
            high = low +1;
        }
        else {
            minVal += arr[high];
            low +=2;
            high = low +1;

        }
    }
    return minVal;
}

Вот что у меня есть для рекурсивной версии. Не пытаясь пошутить над рекурсией, я ходил по этому поводу по кругу около дня. был бы очень признателен.

Answer 1

Попробуйте использовать итераторы вместо индексов массива. Тогда решение становится тривиальным:

#include <iterator>

int findLowestSum(int const* begin, int const* const end) {
  if (begin >= end) return 0; // std::next(begin) would be UB
  auto const next = std::next(begin);
  if (next >= end) return 0;
  if (*begin >= *next) {
    begin = next;
  }
  return *begin + findLowestSum(std::next(begin),end);
}

Это можно вызвать с помощью findLowestSum(std::begin(arr),std::end(arr)).

Вам нужен только заголовок <iterator> для std::next, std::begin и std::end. Вы также можете переписать это, если вам не нужна зависимость <iterator>.