Когда использовать вспомогательные рекурсивные функции / методы для рекурсивных функций / методов

Question

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

    scala> printCounter (List ("the", "rain", "in", "spain"))
[001] the
[002] rain
[003] in
[004] spain

Решение, представленное на листе, выглядит следующим образом:

def printCounterAux [X] (xs:List[X], count:Int) : Unit = {
  xs match {
    case Nil   => ()
    case y::ys => {
      println ("[%03d] %s".format (count, y))
      printCounterAux (ys, count + 1)
    }
  }
}

def printCounter [X] (xs:List[X]) : Unit = {
  printCounterAux (xs, 1)
}

printCounter (List ("the", "rain", "in", "spain"))

Мне не приходило в голову создать вспомогательный метод. Мой вопрос, как человека, который все еще разбирается в рекурсии: как узнать, когда необходимо создать вспомогательный рекурсивный метод? В этом случае будет ли сигнал иметь несколько параметров? Или это просто вопрос большого количества таких методов? Большое спасибо за любой совет, которым вы можете поделиться. Ура.

Answer 1

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

Мы пишем циклы функционально, без изменения переменной al oop, с помощью рекурсивной функции. Здесь мы определяем рекурсивную вспомогательную функцию внутри тела факториальной функции. Такую вспомогательную функцию часто называют go или l oop по соглашению.

def factorial(n: Int): Int = {
    def go(n: Int, acc: Int): Int =
        if (n <= 0) acc
        else go(n - 1, n * acc)
    go(n, 1)
}

Поскольку она локальная, на функцию go можно ссылаться только из тела факториальной функции, так же, как и локальная переменная. Наконец, определение факториала состоит из вызова go с начальными условиями для l oop.

Аргументы go - это состояние для l oop. В данном случае это оставшееся значение n и текущий накопленный факториал a cc. Чтобы перейти к следующей итерации, мы просто рекурсивно вызываем go с новым состоянием l oop (здесь go(n-1, n*acc)), а для выхода из l oop мы возвращаем значение без рекурсивного вызова (здесь, мы возвращаем cc в случае, если n <= 0). Scala обнаруживает такого рода саморекурсию и компилирует его в тот же вид байт-кода, который будет выдаваться на некоторое время l oop (мы можем писать while циклы вручную в Scala, но это редко необходимо и считается плохим тоном, поскольку мешает хорошему композиционному стилю.), пока рекурсивный вызов находится в хвостовой позиции.

Вызов считается в хвосте позиции, если вызывающий не делает ничего, кроме возврата значения рекурсивного вызова. Например, рекурсивный вызов go(n-1,n*acc) находится в хвостовой позиции, поскольку метод возвращает значение этого рекурсивного вызова напрямую и больше ничего с ним не делает. с другой стороны, если бы мы сказали, что 1 + go(n-1,n*acc), go функция больше не будет в хвостовой позиции, так как у метода все равно будет работа, когда go вернет ее s результат (а именно прибавление к нему 1). Если все рекурсивные вызовы, сделанные функцией, находятся в хвостовой позиции, Scala автоматически компилирует рекурсию в итерационные циклы, которые не используют кадры стека вызовов для каждой итерации, и мы можем избежать проблем с StackOverflow. По умолчанию Scala не сообщает нам, было ли устранение хвостового вызова успешным, но если мы ожидаем, что это произойдет для рекурсивной функции, которую мы пишем, мы можем сообщить компилятору Scala об этом предположении, используя tailre c аннотации, поэтому она может выдать нам ошибку компиляции, если не может устранить хвостовые вызовы функции.

def factorial(n: Int): Int = {
    @annotation.tailrec
    def go(n: Int, acc: Int): Int =
        if (n <= 0) acc
        else go(n - 1, n * acc)
    go(n, 1)
}

Это очень распространенный сценарий для написания внутренней функции или локального определения.

Answer 2

printCounterAux имеет API, отличный от printCounter. Не только это, но и изменение API не имеет ничего общего с функциональностью метода, это чисто деталь реализации. (Например, если бы printCounter был реализован с al oop, в этом не было бы необходимости.)

Следовательно, вы хотите скрыть этот API от потребителя.

По порядку чтобы действительно правильно скрыть этот API, printCounterAux должна быть внутренней функцией из printCounter, например:

def printCounter[X](xs: List[X]): Unit = {
  printCounterAux()

  def printCounterAux[X](xs: List[X] = xs, count: Int = 1): Unit = xs match {
    case Nil     => ()
    case y :: ys => {
      println("[%03d] %s".format(count, y))
      printCounterAux(ys, count + 1)
    }
  }
}

printCounter(List("the", "rain", "in", "spain"))

Обратите внимание, что во многих случаях вам нужно носите с собой какое-то «состояние», а в рекурсивной функции на чисто функциональном языке очень удобное место для переноса этого состояния - это аргументы функции. Следовательно, вам часто придется изменять список параметров, чтобы добавить параметр состояния (например, count в этом случае), который не должен быть показан потребителю.