Kotlin под капотом: как избавиться от рекурсии

[GospodinKolhoznik]

Добавление tailrec к функции без хвостовой рекурсии скомпилируется, но не даст вам никакой оптимизации.

Тогда зачем вообще нужно это волшебное слово tailrec? Если компилятор может оптимизировать рекурсию, так пусть оптимизирует, ну а если не может, так не может. Зачем принуждают писать tailrec?

[aamonster]

Стало интересно, нагуглил две причины:

1. В Kotlin и Java не заложена хвостовая рекурсия по умолчанию, т.к. она ломает стек фреймы (удобство отладки? Стоит ли того?)

2. Якобы tailrec – в первую очередь для программиста, чтобы он был уверен, что тут цикл (тогда непонятно, почему не tail call – это warning, а не error)

3. Кстати, ещё наткнулся на интересный вопрос – почему это модификатор функции, а не атрибут для вызова. Аннотация на уровне вызова подошла бы для вещей типа первой оптимизации наивной реализации qiucksort (когда для меньшей части массива мы делаем рекурсивный вызов, а для большей – итеративный), а также для случая взаимной рекурсии.

[MaxSidorov]

Я и сам задаюсь этим вопросом. Посмотрим что ответят в JetBrains

[vba]

От части с вами согласен, но разработчику жизненно важно знать имела ли оптимизация место или нет. В данном случае компилятор должен работать как, например, в Scala:

Добавление tailrec к функции без хвостовой рекурсии скомпилируется, Если оптимизация не возможна или жирное предупреждение, или ошибка компиляции.

[Anarchist]

Ошибка компиляции в Scala :) Любое нецклевое использование: если нет рекурсии вообще или есть нехвостовая.

[KonovalovIly]

Потому что есть recursion , а есть corecursion. Tailrec поддерживается только для corecursion. А не каждая recursion corecursion. Если хотите разобраться есть книга "the joy kotlin" Saumont, там этому раздел посвящен. Ну а если хочется прям в базу копнуть то есть SICP но там в lisp-е придется поковыряться

[konsoletyper]

Вот никогда не понимал этого. Я ещё понимаю, во всяких OCaml, где никаких циклов не заложено by design, там хвостовая рекурсия - это единственный способ писать оптимальный код. Но Kotlin - нормальный императивный язык, нет вообще ни одной причины тот код, который легко и читабельно представим циклами, переписывать в хвостовую рекурсию. Но вот взяли и потратили силы на то, чтобы это реализовать. Чтобы что? Поставить галочку напротив "ещё одна фича из функциональных языков"? Ради читабельности? Не думаю, что большинству разработчиков удобнее спарсить глазами того же Фибоначчи в "декларативном" стиле, чем через старый добрый цикл. Кроме того, часто такие элегантные математические определения из учебника не ложатся в хвостовую рекурсию и нужно их переписать, так что они уже не будут выглядеть такими же элегантными.

[aamonster]

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

А в функциональщине, кстати, любят вместо хвостовой рекурсии в явном виде использовать fold и тому подобное.

[Beholder]

От варианта с генератором sequence можно было бы ожидать более низкой производительности, так как там действительно работают suspend функции, но не настолько же. Всё как-то подозрительно.

Вы опубликовали бы исходники бенчмарка.

[MaxSidorov]

Я создаю следующую иерархию вью

root
  view
  viewGroup
  view    |
          view
          viewGrpoup
          view     |
                  view
                  viewGroup
                  view

и так на заданный уровень глубины (1000, 3000, 5000)

Затем я выполняю тест, который находит все view, чей id делится нацело на 10 (то есть примерно 10% всех вьюшек). Идишники вьюшек генерируются автоинкрементом

И вот код самого теста, но он тривиальный

    val rootView = createHierarchy(10000)
    
    @Benchmark
    fun yieldBenchmark(): List<View> {
        return rootView.findViewYield { it.id % 10 == 0  }.toList()
    }

    fun ViewGroup.findViewYield(predicate: (View) -> Boolean): Sequence<View> {
        return sequenceOf(this)
            .plus(this.descendants)
            .filter { predicate(it) }
    }    

Аналогичные тесты и для всех остальных функций

[MaxSidorov]

На выходных оформлю код в github, его надо еще причесать) и отправлю issue в JetBrains и возможно в Google и тогда скину ссылку на github в статью. Просто я статью написал за два дня и еще не успел все оформить как следует.

[MaxSidorov]

Я опубликовал исходники тестов и всех функций: https://github.com/maxssoft/yield_recursion
И обновил статью. Перепроверил все результаты. Yield работает в сотни раз медленнее всех остальных подходов.

[Spinoza0]

Любопытно было прочитать, спасибо

[auddu_k]

Классная статья, спасибо ? Всегда интересны новые подходы к стандартным задачам.

Есть вопрос -) Правильно ж я вижу, что в итераторе при обходе не учитывает root, мы сразу перескаетваем к деткам?

[MaxSidorov]

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

[Kajfolom]

...с мягким знаком) простите...