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

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

fac :: Int -> Int
fac n
    | n==0 = 1
    | n>0  = fac (n-1) * n
Источник

4 ответа

Решение

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

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

  • Базовый вариант
  • Индуктивный Шаг

Индуктивный шаг часто является наиболее трудной частью, потому что он предполагает, что все, на что он опирается, уже вычислено правильно. Сделать этот прыжок веры может быть сложно (по крайней мере, мне потребовалось некоторое время, чтобы освоить его), но это только потому, что у нас есть предварительные условия для наших функций; эти предварительные условия (в этом случае, что 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

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

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.

Источник

Когда ты пишешь | 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
Источник

Специально для более сложных случаев рекурсии уловка, направленная на сохранение психического здоровья, заключается не в том, чтобы следовать рекурсивным вызовам, а просто предполагать, что они "поступают правильно". Например, в вашем примере с fac вы хотите вычислить 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],

Источник

Что тебя бросает? может быть, охранники (|) запутанные вещи.

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

Для панорамирования императивный, как seudo-код....

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

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

Источник
Другие вопросы по тегам