Рекурсивная функция, возвращающая непонятные ответы

Question

Я пишу небольшую программу для моего класса Computing I, в которой программа принимает целое число целых чисел, определяемое пользователем, и вычисляет точечный продукт. Я смог сделать это успешно, используя итеративный метод, но теперь мы также должны сделать это, используя рекурсию. Моя функция для вычисления точечного продукта возвращает широкий диапазон неправильных чисел. Иногда он просто возвращает значение двойного результата двух последних значений в массивах, когда было еще 4 других набора, которые не были добавлены. В других случаях у меня будет 2 массива из 3 маленьких чисел, а значение возвращается в 80 тысяч. Вот рекурсивная функция:

//A and B are the arrays that will be dotted together, and n is number of 
//elements in each array 
int dotP(int *A, int *B, int n) { 
    if(n==1) return A[0] * B[0] ; 
    return A[n-1] * B[n-1] + dotP(&A[n-1], &B[n-1], n-1); 
} 

Answer 1

Что именно происходит,

A[n-1]*B[n-1] + A[n-1 + n-2]*B[n-1 + n-2]+.... 

Это происходит потому, что для 2-го рекурсивного вызова, вы передаете адрес n-1-го элемента. Когда он вычисляет A[n-2] во втором вызове, он эффективно указывает на n-2-й элемент, начиная с n-1-го элемента, который равен 2*n-3 rd из первого элемента массива.

Значения в массиве после n является мусор (Предполагая, что вы выделили n элементов или может быть выделены более n, но не инициализировать их). Следовательно, вы получали случайные ответы. Вам не нужно передавать адрес текущего элемента массива на каждый рекурсивный вызов. Вы просто передаете адрес первого элемента, который либо A, либо &A[0]. Тогда ваш код работает нормально. Вот как это сделать:

int dotP(int *A, int *B, int n) { 
if(n==1) return A[0] * B[0] ; 
return A[n-1] * B[n-1] + dotP(A, B, n-1) ; 
} 

С A и B указатели уже, вы просто передать их directly.Hope это помогает.

Answer 2

Не

... + dotP(&A[n-1], &B[n-1], n-1); 

но

... + dotP(&A[0], &B[0], n-1); 

поскольку в этом случае вы хотите обработать последний элемент массива, а затем пройти первый (n- 1) к рекурсивному вызову. Помните, что массивы всегда рассматриваются как указатели на их первый элемент, если вы не делаете что-то гораздо более сложное, чем это.

Проблема решена, но, для образовательных целей, попробуйте этот вариант: можно обработать первый элемент и передать остальное, «хвост», который может быть более приятным для поклонников LISP:

return A[0] * B[0] + dotP(&A[1], &B[1], n-1); 

В качестве альтернативы Для этого вы можете передать A + 1 вместо & A [1].

Answer 3

Почему даже не лучше использовать:

int dotP(int *A, int *B, int n) 
{ 
    if (n) return A[0] * B[0] + dotP(A + 1, B + 1, n-1); 
    else return 0; 
} 

или в более компактной форме:

int dotP(int *A, int *B, int n) 
{ 
    if (n) return A[0] * B[0] + dotP(++A, ++B, --n); 
    else return 0; 
}