Почему это не хвост рекурсивный - PullRequest
Новая
       41

Почему это не хвост рекурсивный

0 голосов
/ 04 мая 2018

У меня есть (со?) Рекурсивная пара функций, которые обрабатывают список кортежей и складывают их в пакеты на основе некоторых начальных и конечных критериев.

Я не так много делаю, поэтому могу быть глупым.

Я уже исправил простую не хвостовую рекурсивную версию в этом, явно введя параметр "tot", который составляет текущее свернутое состояние, что я считал хвостовым рекурсивным, но я получаю страшное переполнение стека на больших входах .... (как в отладчике, так и (debug) .exe)

Вероятно, есть лучший способ сделать это как явное сгибание ... но это почти не главное, суть в том, почему это, по-видимому, не хвостовая рекурсия? 

    let rec ignoreUntil2 (xs : List<(string * string)>)  tot = //: List<(string * string)> -> List<List<(string * string)>> -> List<List<(string * string)>> = 
        match xs with              
        | [] -> tot
        | ((s1,s2)::tail) -> 
            if s2.StartsWith("Start importing record: Product") then
                takeUntil2 [] ((s1,s2)::tail) tot
            else
                ignoreUntil2 tail tot
and takeUntil2 acc xs tot = // : List<(string * string)> -> List<(string * string)> -> List<List<(string * string)>> -> List<List<(string * string)>> =
        match xs with
        | [] -> acc :: tot
        | ((s1,s2)::tail)   ->
            let newAcc = ((s1,s2)::acc)
            if s2.StartsWith("Finished importing record: Product") then
                ignoreUntil2 tail (newAcc :: tot)
            else
                takeUntil2 newAcc tail tot

1 Ответ

0 голосов
/ 04 мая 2018

Ваш код является хвостовой рекурсивом.

(как в отладчике, так и (debug) .exe)

По умолчанию компилятор F # не устраняет хвостовые вызовы в режиме отладки. Вам нужно либо явно включить параметр --tailcalls, либо скомпилировать в режиме выпуска.

...