Почему моя переменная меняет значения в рекурсивном вызове в моей программе на C?

Question

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

/*This program will find the largest integer in an array. It was written to practice 
using recursion.*/ 

#include <stdio.h> 
void find_largest(int *a, int n); 
int main() { 
    int a[] = {10, 27, 101, -8, 16, 93}; 
    int n = 6, i = 0; 
    printf("Current array: "); 
    while(i < n) {//print array 
     printf("%d ", a[i]); 
     i++; 
    } 
    find_largest(a, n); 
    return 0; 
}//end main 

//This function will start at the last element, and then step through the array 
//in reverse order using pointers. 
void find_largest(int *a, int n) { //formulate the size-n problem. 
    int largest = 0; 
    if(n == 0) { //find the stopping condition and the corresponding return 
     printf("\nThe largest number is: %d \n", largest); 
    } 
    else { //formulate the size-m problem. 
     n--; //decrement so that the proper number is added to pointer reference 
     if(largest <= *(a + n)) //check if element is larger 
      largest = *(a + n); //if larger, assign to largest 
     find_largest(a, n); //recursive call 
    } 
} 

Программа возвращает нуль как наибольшее целое число. Есть идеи?

Answer 1

largest не является общим для всех ваших рекурсивных вызовов, каждый из которых имеет свою собственную копию. Это означает, что в базовом случае выполнить этот код:

int largest = 0; 
if (n == 0) { 
    printf("\nThe largest number is: %d \n", largest); 
} 

Где largest будет всегда быть 0.

Вы можете сделать largeststatic, и он будет работать, хотя это немного странный способ обойти это. Я бы предпочел, чтобы сделать что-то вроде этого:

int find_largest(int *a, int n) 
{ 
    int subproblem; 

    // base case - single element array, just return that element 
    if (n == 1) 
    { 
     return *a; 
    } 

    // recursion - find the largest number in the rest of the array (increase 
    // array pointer by one, decrease length by one) 
    subproblem = find_largest(a + 1, n - 1); 

    // if the current element is greater than the result of the subproblem, 
    // the current element is the largest we've found so far - return it. 
    if (*a > subproblem) 
     return *a; 

    // otherwise, return the result of the subproblem 
    else 
     return subproblem; 
} 

Answer 2

Каждый раз, когда вы звоните find_largest(), вы создаете локальную переменную INT большой и присваивая ему значение, равное нулю. Поэтому, когда n наконец достигает нуля, на самом деле все равно, что сделали последние 5 рекурсивных вызовов, он просто возвращает нуль, на который вы только что установили наибольший. Либо сделайте крупнейший глобальный, либо передайте его как параметр функции (вероятно, лучше).

Answer 3

largest инициализируется 0 в каждом отдельном вызове функции, вот быстрое решение:

int find_largest(int *a, int n) { //formulate the size-n problem. 
    static int largest = 0; 
    if(!n) { //find the stopping condition and the corresponding return 
     int answer = largest; 
     largest = 0; 
     return answer; 
    } 
    else { //formulate the size-m problem. 
     n--; //decrement so that the proper number is added to pointer reference 
     if(largest <= *(a + n)) //check if element is larger 
      largest = *(a + n); //if larger, assign to largest 
     find_largest(a, n); //recursive call 
    } 
} 

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

В конце функции вы должны сбросить largest на 0, чтобы в следующем вызове он еще не содержал значение предыдущего. Именно поэтому создается временная переменная, поэтому она может вернуть свое значение до того, как оно будет установлено на 0.

Answer 4

сделать int самым большим = 0; в static int наибольшее = 0; это может помочь. При добавлении статического значения наибольшая переменная будет инициализирована только один раз во всей рекурсии.