Хвостовая рекурсия (Tail Call Optimization) в Swift 4 - PullRequest
Новая
       16

Хвостовая рекурсия (Tail Call Optimization) в Swift 4

2 голосов
/ 06 марта 2019

Я попытался выполнить следующую простую функцию в Swift: 

 func sum (n: Int, currentSum: Int = 0) -> Int {
    return n == 0 ? currentSum :
                    sum(n: n-1,
                        currentSum: currentSum + n)
 }

Я ожидал, что компилятор будет использовать оптимизацию хвостовой рекурсии.Но я попадаю в (буквально :-P) проблему переполнения стека.

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

Спасибо!

1 Ответ

2 голосов
/ 06 марта 2019

Как отмечает Мартин, вы не получите TCO в любом случае, если не включите оптимизатор (-O), но даже в этом случае нет способа гарантировать, что вы получите TCO, и поэтому вы действительноне могу на это рассчитывать.Swift не особенно дружелюбен к рекурсивным алгоритмам.Обычно вы пишете это следующим образом: 

func sum(n: Int) -> Int {
    return (1...n).reduce(0, +)    
}

Или для сохранения той же самой вычислительной схемы (т. Е. С обратным отсчетом от n до 1): 

func sum(n: Int) -> Int {
    return (1...n).reversed().reduce(0, +)
}
...