Правильное использование рекурсии

Question

Я новичок в рекурсии в C ++. Задача просит нас найти максимальный элемент массива.

Авторское решение было следующим:

#include<iostream>
using namespace std;

int arr_max(int arr[], int len)

{
    if (len == 1)
        return arr[0];

    int sub_result = arr_max(arr, len - 1);
    return max(sub_result, arr[len - 1]);
}

int main() {
    int arr[] = { 1, 8, 2, 10, 3 };

    cout << arr_max(arr, 5);

    return 0;
}

и мое решение было следующим:

#include<iostream>
using namespace std;

int func(int arr[] ,int s) {
static int max = 0 ;
static int i = 0 ;
if(s == 0)
    return max ;

if(arr[i] > max)
    max = arr[i] ;
i++ ;
func(arr,s-1) ;
}

int main() {
int arr[6] = {11,5,48,100,45,67} ;
cout << func(arr,6) ;

    return 0;
}

Оба кода работают, но мои вопросы:

1. Правильно ли я использую рекурсию и проверяю концепцию рекурсии, или я делаю что-то еще? И
2. Один из приведенных выше кодов лучше другого? Почему?

Answer 1

Когда я компилирую ваш код, я получаю сообщение об ошибке «main. cpp: 14: 1: предупреждение: элемент управления может достигнуть конца непустой функции [-Wreturn-type]».

I думаю, что дизайн предоставленного ответа лучше, потому что он не рискует не вернуть значение, как ваш.

Подумайте, что вам нужно знать, чтобы заставить рекурсивную функцию работать.

1.) Какой базовый случай? На какой самый простой вариант проблемы вы можете сразу ответить? В этом случае это происходит, если у вас есть массив только с одним элементом, который по определению является самым большим в массиве. (Примечание: вам также нужна обработка ошибок для пустых массивов.)

Итак, в простейшем случае вы просто возвращаете единственный элемент в массиве.

Рекурсивный случай требует, чтобы вы подумайте, что произойдет, если вы увеличите размер массива. Предоставленный ответ делает это путем рекурсивного вызова самого себя до тех пор, пока исходный единственный массив длиной len не будет разделен на len массивы длины 1. Затем он возвращается вверх по стеку вызовов, многократно возвращая больший из последнего элемента. в массиве и функция, вызываемая для остальных элементов, за исключением последнего.

Это означает, что вы выполняете len вызовов для arr_max и len сравнений. (Если бы массив был действительно большим, у вас могла бы закончиться память, сделав это таким образом.)

Ваша функция принимает базовый случай, когда длина массива равна 0. Но если в массиве нет элементов, то это не так. Нет величайшего элемента. Вместо этого вы возвращаете 0. Это немного странно. Также немного странно то, как вы увеличиваете i с 0, но рекурсивно вызываете функцию на len-1.

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