Пытаетесь разобраться с рекурсией в Хаскеле?

Question

Сейчас я использовал много рекурсивных функций, но все еще не могу понять, как именно работает эта функция (я знаком со второй строкой (например, | n==0 = 1), но не очень хорошо знаком с последней строкой (т.е. | n>0 = fac (n-1) * n)).

fac :: Int -> Int
fac n
    | n==0 = 1
    | n>0  = fac (n-1) * n

Answer 1

Рекурсивные алгоритмы очень тесно связаны с математической индукцией .Возможно, изучение одного из них поможет вам лучше понять другое.

При использовании рекурсии необходимо помнить два ключевых принципа:

• Базовый случай
• Индуктивный шаг

Индуктивный шаг часто является самым сложным, потому что он предполагает , что все, на что он опирается, уже вычислено правильно.Сделать этот прыжок веры может быть сложно (по крайней мере, мне потребовалось некоторое время, чтобы освоить его), но это только потому, что у нас есть предварительных условий для наших функций;эти предварительные условия (в этом случае n является неотрицательным целым числом) должны быть указаны так, чтобы индуктивный шаг и базовый случай были всегда истинными .

Базовый случай такжеиногда сложно: скажем, вы знаете, что факториал N! равен N * (N-1)!, но как именно вы справляетесь с первым шагом на лестнице?(В данном случае это просто, определите 0! := 1. Это явное определение предоставляет вам способ прекратить рекурсивное применение вашего индуктивного шага.)

Вы можете увидеть свой типСпецификация и шаблоны защиты в этой функции обеспечивают предварительные условия, которые гарантируют, что индуктивный шаг можно будет использовать снова и снова, пока он не достигнет базового случая, n == 0.Если предварительные условия не могут быть выполнены, рекурсивное применение индуктивного шага не сможет достичь базового варианта, и ваши вычисления никогда не прекратятся.(Ну, это было бы, когда у него не хватало памяти.:)

Один сложный фактор, особенно с функциональными языками программирования, это очень сильное желание переписать все «простые» рекурсивные функции, как у вас здесь, с вариантами, которые используют Tail Calls или Tail Recursion.

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

fac 3        3 * fac 2
  fac 2      2 * fac 1
    fac 1    1 * fac 0
      fac 0  1
    fac 1    1
  fac 2      2
fac 3        6

Этот глубокий стек вызовов занимает память;но компилятор, который замечает, что функция не меняет никакого состояния после выполнения рекурсивного вызова, может оптимизировать рекурсивные вызовы.Такие функции обычно передают аргумент аккумулятор .У такого же накопителя есть очень хороший пример: Хвостовая рекурсия в Haskell

factorial 1 c = c
factorial k c = factorial (k-1) (c*k)

Это очень сложное изменение :) означает, что предыдущая цепочка вызовов превращается в следующее:

fac 3 1       fac 2 3
  fac 2 3     fac 1 6
    fac 1 6   6

(Вложенность предназначена только для показа; система времени выполнения фактически не будет хранить сведения о выполнении в стеке.)

Это выполняется в постоянной памяти независимо от значения nи, таким образом, эта оптимизация может преобразовать «невозможные» алгоритмы в «возможные» алгоритмы.Вы увидите, что этот вид техники широко используется в функциональном программировании, так же, как вы часто видели бы char * в программировании на С или yield часто в программировании на Ruby.

Answer 2

Когда вы пишете | condition = expression, вводится сторож .Охрана проверяется по порядку сверху вниз до тех пор, пока не будет найдено истинное условие, и соответствующее выражение является результатом вашей функции.

Это означает, что если n равно нулю, результат равен 1иначе, если n > 0, результат будет fac (n-1) * n.Если n отрицательно, вы получаете ошибку неполного сопоставления с образцом.

Как только вы определили, какое выражение использовать, нужно просто заменить рекурсивные вызовы, чтобы посмотреть, что происходит.

fac 4
(fac 3) * 4
((fac 2) * 3) * 4
(((fac 1) * 2) * 3) * 4
((((fac 0) * 1) * 2) * 3) * 4
(((1 * 1) * 2) * 3) * 4
((1 * 2) * 3) * 4
(2 * 3) * 4
6 * 4
24

Answer 3

Специально для более сложных случаев рекурсии хитрость для сохранения психического здоровья заключается в , а не , чтобы следовать рекурсивным вызовам, а просто предположить, , что они "поступают правильно". Например. в вашем примере вы хотите вычислить fac n. Представьте, что у вас уже есть результат fac (n-1). Тогда вычислять fac n тривиально: просто умножьте его на n. Но магия индукции заключается в том, что этот аргумент на самом деле работает (при условии, что вы предоставите надлежащий базовый вариант для прекращения рекурсии). Так, например для чисел Фибоначчи просто посмотрите, каков базовый случай, и предположите , что вы можете вычислить функцию для всех чисел, меньших n:

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

См? Вы хотите рассчитать fib n. Это легко, если бы вы знали fib (n-1) и fib (n-2). Но вы можете просто предположить , что вы можете рассчитать их, и что "более глубокие уровни" рекурсии делают "правильную вещь". Так что просто используйте их, это будет работать.

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

Кстати: «лучший» способ написать fac будет fac n = product [1..n].

Answer 4

что тебя бросает? может быть, охранники (|) сбивают с толку.

Вы можете свободно рассматривать охранников как цепочку ifs или оператора switch (разница в том, что может работать только один, и он напрямую оценивает результат. Не выполняет ли серию задач, и, конечно, не имеет побочных эффектов?) просто оценивает значение)

Для панорамирования подобного императиву seudo-кода ....

Fac n:
   if n == 0: return 1
   if n > 0: return n * (result of calling fac w/ n decreased by one)

Дерево вызовов другого автора выглядит так, как будто оно может быть полезным. сделайте себе одолжение и действительно пройдитесь по нему