Моя рекурсивная функция дает сбой из-за переполнения стека? Если да, учитывая мое определение функции, это нормально?

Question

Я тестировал рекурсивную функцию на производительность.

В строке 33 я создаю массив с 50000 элементов в нем; каждый элемент в массиве имеет значение Int между 1 и 30.

Тест завершается ошибкой, когда количество элементов в массиве приблизительно> 37500.

Я не совсем уверен, что это за кр sh из-за, но я предполагаю, что это из-за переполнения стека? Это на самом деле из-за потока стека? Учитывая то, что я делаю / этот контекст - нормально ли ожидать здесь переполнение стека?

Для вашего удобства ниже приведен код:

 let arr = (1...50000).map { _ in Int.random(in: 1...30) }

    func getBuildingsWithView(_ buildings: [Int]) -> [Int]? {
        if buildings.isEmpty { return nil }
        let count: Int = buildings.count - 1
        var indices: [Int] = []
        let largest: Int = 0
        var buildings = buildings
        hasView(&buildings, &indices, largest, count)
        return indices
    }

    func hasView(_ buildings: inout [Int], _ indices: inout [Int],  _ largest: Int, _ count: Int) {
        if count > 0 {
            var largest = largest
            if (buildings[count] > largest) {
                largest = buildings[count]
            }
            hasView(&buildings, &indices, largest, count-1)
        }
        if (buildings[count] > largest) {
            indices.append(count)
        }
    }

    func test1() {
        print("-----------------TEST START - RECURSION------------------")
        measure {
            print(getBuildingsWithView(arr)!)
        }
        print("-----------------END------------------")
    }

Answer 1

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

Более подробно в другом посте: BAD_ACCESS во время рекурсивных вызовов в Swift

Обратите внимание, что то, что вы реализовали, похоже, работает максимум в обратном порядке, возвращая индексы, и это может быть реализовано более эффективно без переполнения как это:

func runningMax(_ arr: [Int]) -> [Int] {
    var max = 0
    var out = [Int]()

    for (i, element) in arr.enumerated().reversed() {
        if element > max {
            max = element
            out.append(i)
        }
    }

    return out.reversed()
}

Я сравнил это с вашим алгоритмом, и результаты, кажется, идентичны. Я также проверил с большими значениями до 100 000 000, и это нормально.

Возвращаемый массив не обязательно должен быть необязательным, если входной массив пуст, так и выходной массив.