Рекурсия с массивом; не могу получить правильное значение для возврата

Question

Решение найдено - менее чем за 5 минут, спасибо, ребята!

Уточнение: содержимое моего массива - значения 0-29. Итак, array [0] [0] = 0, а array [29] [0] = 29 --- это просто тестовые значения. Кроме того, у меня есть потенциальное решение, которое было опубликовано несколько раз, и я попробую это.

Рекурсивное решение: не работает! Пояснение: целое число, время, передается в функцию. Затем он используется для окончания оператора FOR (counter<time). Раздел IF (time == 0) предоставляет базовый случай, когда рекурсия должна завершиться, возвращая 0. В разделе ELSE происходит рекурсивный вызов: total - это закрытая переменная, определенная в заголовочном файле, в другом месте. Он инициализируется в 0 в конструкторе, в другом месте. Функция вызывает сама, рекурсивно, добавляя productsAndSales[time-1][0] к итогу, снова и снова, до базового вызова. Затем сумма возвращается и распечатывается позже. Ну, это то, на что я надеялся в любом случае.

То, что я предполагал, состояло бы в том, что я сложу все значения в этом одном столбце массива, и значение будет возвращено и распечатано. Вместо этого, если возвращается 0. Если я устанавливаю секцию IF на «return 1», я заметил, что она возвращает степени 2 для любого значения времени. Например: время = 3, возвращается 2 * 2 + 1. Если время = 5, возвращается 2 * 2 * 2 * 2 + 1.

Я не понимаю, почему он не возвращает ожидаемое мной значение. Одна вещь, о которой я подумал, это то, что я пытаюсь использовать частную переменную total в секции return вместе с рекурсивным вызовом ... может быть, это как-то нет-нет?

int CompanySales::calcTotals( int time )
{
  cout << setw( 4 );
  if ( time == 0 )
   {
    return 0;
   }
  else
   {
    return total += calcTotals( productsAndSales[ time-1 ][ 0 ]);
   }
}

Итеративное решение: работает! Пояснение: целое число, время, передается в функцию. Затем он используется для завершения оператора FOR (counter<time). Оператор FOR циклически перебирает массив, складывая все значения в одном столбце вместе. Затем возвращается значение (и в другом месте программы, распечатывается). Работает отлично.

int CompanySales::calcTotals( int time )
{
 int total = 0;
 cout << setw( 4 );

 for ( int counter = 0; counter < time; counter++ )
 {
  total += productsAndSales[counter][0];
 }
 return total0;
}

Answer 1

Не используйте глобальный total, сделайте его аргументом.

int totals = calcTotals(time-1, 0); // Call it starting at the end, 
                                    // so we don't have to pass along the `time`


int CompanySales::calcTotals( int counter, int total )
{
  if ( counter == 0 ) {
    return total;
  }
  else {
    return calcTotals(counter - 1, total + productsAndSales[counter][ 0 ]);
  }
}

Теперь он тоже хвостовой рекурсив.

Answer 2

Что ж, в вашей рекурсивной функции вы ожидаете время в качестве параметра для вашей функции, но когда вы делаете рекурсивный вызов, он передает значение вашего массива productsAndSales, а не (время - 1), которое я ожидал .

Если предположить, что содержимое вашего массива productAndSales не содержит ноль, проверка завершения времени == 0 никогда не произойдет

Answer 3

Неправильный аргумент, передаваемый вокруг:

total += calcTotals( productsAndSales[ time-1 ][ 0 ]);

Должно быть:

total +=  productsAndSales[ time ][ 0 ]  + calcTotals(time - 1);

Answer 4

Это должно дать тот же результат, что и итерационная функция.

int CompanySales::calcTotals( int time )
{
  cout << setw( 4 );
  if ( time == 0 ){
    return 0;
  }
  else{
    return productsAndSales[time-1][ 0 ] + calcTotals( time - 1 );
  }
}

Answer 5

Должно быть

return total += productsAndSales[time - 1][0] + calcTotals(time - 1);

Answer 6

Не должно ли это быть

int CompanySales::calcTotals( int time )
{
  int total = 0;
  cout << setw( 4 );
  if ( time == 0 )
   {
    return 0;
   }
  else
   {
    return total += productsAndSales[ time ][ 0 ] + calcTotals( time - 1);
   }
}

Answer 7

Нигде в вашем рекурсивном решении вы на самом деле не добавляете значение productsAndSales - вы передаете эти значения в качестве параметра времени вашей функции calcTotals().

Так что, если total начинается с нуля, вы просто вызываете эту функцию несколько раз и никогда не добавляете к ней ничего, кроме нуля.