Хвостовая рекурсия в Scala

В этом посте я расскажу об интересной фиче функционального программирования - о хвостовой рекурсии. Но для начала вспомним, что такое вообще рекурсия. Итак, рекурсия - это описание некоего объекта, который является составной частью самого себя. Например, математическое выражение может содержать числовые операнды, арифметические операции и другие математические выражения.

Рекурсия

В работе мы сталкиваемся с рекурсивными функциями. Для нахождения значения такой функции для определенного набора входных параметров требуется найти значение этой функции для другого набора входных параметров. Другими словами, это функция, которая вызывает сама себя. Самыми известными примерами рекурсий являются факториал (именно так утверждают большинство учебников по программированию) и числа Фибоначчи. Забудем о факториале и посмотрим, как выглядит реализации чисел Фибоначчи на Java:

    public static int fib(int n) {
        if (n > 1) return fib(n - 1) + fib(n - 2);
        else return n;
    }

Как видно из примера, перед возвратом значения из функции происходит два вызова этой же функции, но с другими значениями.

Хвостовая рекурсия

Теперь вернемся к хвостовой рекурсии. Рекурсия будет хвостовой, если вызов рекурсивной функции будет последней операцией перед возвратом. Давайте перепишем предыдущий пример с использованием хвостовой рекурсии:

    public static int fibWithTailRec(int n) {
        if (n > 1) return fibIter(1, 1, n - 2);
        else return n;
    }

    private static int fibIter(int prev, int current, int n) {
        if (n == 0) return current;
        else return fibIter(current, prev + current, n - 1);
    }

API нашего класса не изменилось: у нас по-прежнему есть метод, возвращающий значение n-ого числа Фибоначчи. Также у нас появился новый закрытый метод fibIter, который содержит хвостовую рекурсию. Очень часто для её реализации используется вспомогательный метод, который принимает состояние рекурсии перед очередной итерацией. Благодаря этому хвостовая рекурсия может быть представлена как цикл:

    public static int fibWithLoop(int n) {
        if (n <= 1) return n;

        int i = 2;
        int prev = 1;
        int current = 1;
        while (i < n) {
            int next = prev + current;
            prev = current;
            current = next;
            i += 1;
        }
        return current;
    }

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

Давайте проверим наши функции в боевых условиях и посчитаем 10000-й элемент последовательности. К нашему огорчению, оба метода - и fib, и fibWithTailRec - бросят java.lang.StackOverflowError. Это говорит о том, что использовать рекурсии в Java нужно аккуратно. И не забывать о методе с использованием цикла :)

Scala спешит на помощь

А что думают о рекурсии другие JVM языки? Давайте посмотрим, как обстоят дела у Scala с рекурсивным функциями и перепишем оба рекурсивные реализации кода, считающий числа Фибоначчи. Попробуем сделать максимально похожие реализации тех же функций:

  def fib(n: Int): Int =
    if (n > 1) fib(n - 1) + fib(n - 2)
    else n

  def fibWithTailRec(n: Int): Int =
    if (n > 1) fibIter(1, 1, n - 2)
    else n

  // Функция fibIter не сделана внутренней в fibWithTailRec для наглядности.
  private def fibIter(prev: Int, current: Int, n: Int): Int = 
    if (n == 0) current
    else fibIter(current, prev + current, n - 1)

А теперь еще раз посчитаем 10000-ое число Фибоначчи, но уже на Scala. Оказывается, что версия с хвостовой рекурсией успешно справилась с задачей. В чем же разнице между практически “одинаковым” кодом на Java и на Scala. Давайте заглянем в байт-код этих методов (javap -c) и проверим, что же на самом деле предполагают делать компиляторы:

java version:
  public static int fibIter(int, int, int);
    Code:
       0: iload_2
       1: ifne          6	// проверка на конец вычисления
       4: iload_1
       5: ireturn
       6: iload_1			// пишем в стек current
       7: iload_0
       8: iload_1
       9: iadd		    	// пишем в стек prev + current
      10: iload_2
      11: iconst_1
      12: isub				// пишем в стек n - 1
      13: invokestatic  #2  // вызываем метод fibIter:(III)I
      16: ireturn			// возвращаем результат вызова
scala version:
  public int fibIter(int, int, int);
    Code:
       0: iload_3
       1: iconst_0
       2: if_icmpne     7	// проверка на конец вычисления
       5: iload_2
       6: ireturn
       7: iload_2			// пишем в стек current
       8: iload_1
       9: iload_2
      10: iadd				// пишем в стек prev + current
      11: iload_3
      12: iconst_1
      13: isub				// пишем в стек n - 1
      14: istore_3
      15: istore_2
      16: istore_1			// сохраняем всё в локальные переменные
      17: goto          0	// переходим в начало итерации

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

Мир никогда не будет прежним

Итак, мы уже знаем, насколько крута хвостовая рекурсия. Пора применить эти знания. В мире ФП ни одна программа не обходится без списков. Попробуем самостоятельно реализовать свертку (он же fold, он же reduce) - одну из основных операций над списком (Scala предлагает нам две версии - слева и справа):

  def foldLeft[A, B](seq: Seq[A], z: B)(f: (B, A) => B): B =
    seq match {
      case Nil => z
      case x :: xs => foldLeft(xs, f(z, x))(f)
    }

  def foldRight[A, B](seq: Seq[A], z: B)(f: (A, B) => B): B =
    seq match {
      case Nil => z
      case x :: xs => f(x, foldRight(xs, z)(f))
    }

Как видим, обе функции рекурсивные, но, о ужас, foldRight не имеет хвостовой рекурсии, а значит нам грозит переполнением стека. Есть достаточно простое решение, которое, конечно же, требует дополнительных затрат, но при этом не ухудшит сложность вашего алгоритма. Напишем свертку справа через свертку слева:

  def foldRightUsingFoldLeft[A, B](seq: Seq[A], z: B)(f: (A, B) => B): B =
    foldLeft(seq.reverse, z)((b, a) => f(a, b))

В случае, если мы не уверены, будет наша функция оптимизирована или нет, а нам бы очень этого хотелось, можно воспользоваться аннотацией @tailrec. Достаточно распространенным является мнение, что это команда компилятору сделать хвостовую рекурсию в методе. Но это не так (тем более, что такое преобразование не всегда возможно). Она лишь заставляет проверить, содержит ли помеченная ею функция хвостовую рекурсию, и, если это не так, то произойдет ошибка компиляции. Причин для этого немного и их легко проверить:

  • это не финальный метод, а значит он может быть переопределен в подклассах
  • метод не вызывает сам себя, т.е. это не рекурсия
  • это не хвостовая рекурсия.
Связаться