Я запутался в том, что рекурсивно, хвост рекурсивно, примитивно рекурсивно, а что нет

Question

Я написал простое предположение о числовой программе, и мне нужно знать, есть ли в ней какая-либо рекурсия и какая она (примитивная / хвостовая) (я новичок в этом, поэтому, пожалуйста, имейте в видуя)

module MyProgram where
import System.Random

guessNum :: IO()
guessNum =
do  --gen <- newStdGen
    --let num = randoms gen :: [Int]
    num<-randomRIO(20,100 :: Int)
    putStrLn "Guess the number: "
    input<-getLine
    let guess = (read input :: Int)
    checkGuess guess num


checkGuess:: Int -> Int -> IO()
checkGuess guess num1 |(num1<guess)=
                do  putStr"Too high! Guess again!"
                    input<-getLine
                    let guess = (read input)::Int
                    checkGuess guess num1
                |(num1>guess)=          
                do  putStr"Too low! Guess again!"
                    input<-getLine
                    let guess = (read input)::Int
                    checkGuess guess num1
                |(num1==guess)  =
                do  putStr"Congratulations! You found the number!"

Answer 1

Функция является рекурсивной, если она вызывает себя (не обязательно в каждом случае, но, по крайней мере, в одном случае).Например:

sum [] = 0
sum (x:xs) = x + sum xs

Приведенная выше функция не является хвостовой рекурсивной.Во втором уравнении сначала вычисляются x и sum xs, а конечным результатом является их сумма.Поскольку конечный результат не является вызовом функции, он не является хвостовой рекурсивной.Чтобы преобразовать эту функцию в хвостовую рекурсию, мы можем использовать шаблон аккумулятора:

sum [] acc = acc
sum (x:xs) acc = sum xs (x + acc)

Обратите внимание, что во втором уравнении сначала вычисляются xs и x + acc, а в качестве последний шаг это называет себя.Хвостовые рекурсивные функции важны, потому что их можно систематически преобразовывать в циклы, что исключает накладные расходы на вызовы функций.Некоторые языки делают эту оптимизацию, я думаю, что эта оптимизация не нужна в Haskell (см. Также комментарий Хаммара ниже).

Ваша функция checkGuess может показаться хвостовой рекурсивной, но это не так.Синтаксис do является синтаксическим сахаром для использования оператора * 1016. *

f = do
    x <- g
    h x

преобразуется в

f = g >>= (\x -> h x)

, поэтому почти в каждой записи do последняя функция, которая будет вызванаis >>=.

Функция является примитивно-рекурсивной, если она может быть построена с использованием 5 конструкций, описанных здесь .Сложение, умножение и факториал являются примерами примитивно-рекурсивных функций, в то время как функция Аккермана - нет.

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

Примечания:

• Можно сказать, что группа функций является взаимно рекурсивной, если способ, которым они вызывают друг друга, имеет циклы (f вызывает g,g вызывает h, а h в конце концов вызывает f).

Answer 2

Функция является рекурсивной, если она вызывает себя где-нибудь в своем коде.Так что предположим, что не имеется догадки (в коде guessNum или в коде, который он вызывает), нет никакого предположения о догадке, а checkGuess имеет значение.

Хвостовая рекурсия - это когда рекурсивный вызов - это последнее, что делает функция ... но этоHaskell и tail recursion - это термин, в основном предназначенный для строгих языков, где он позволяет оптимизировать рекурсивную функцию, чтобы она не увеличивала стек (текущий вызов может быть прямо заменен рекурсивным, поскольку вам не нужно ничего делатьпосле рекурсивного вызова возвращается).Так как другие говорили, что checkGuess не является хвостовой рекурсией или не будет на строгом языке ... Однако с ленивой семантикой, (a >> b) будет оцениваться как b во многих монадах (включая IO), так как раз aвычисляется (точнее, выполняется действие ввода-вывода), его можно забыть, и единственное, что имеет значение, - это возврат b.

В двух словах, ваша функция checkGuess является рекурсивной, а не хвостовой рекурсивной по большинству формальных определенийно эти определения не адаптированы для нестрогих языков, таких как Haskell, и checkGuess будет определенно выполняться в постоянном пространстве, как если бы он был хвостовым рекурсивным в строгом языке (по крайней мере, с разумными реализациями Haskell, такими как GHC).

Примитивная рекурсия - это понятие, определенное для N ^ k -> N функций, я не думаю, что вопрос имеет смысл для такой функции, как checkGuess, не без некоторой сомнительной адаптации и рассмотрения перевода функции внекоторый более простой язык (эквивалент лямда-исчисления), который означал бысемантика cit IO и т. д. Я бы сказал, что ваша функция ничего не делает со своим параметром Int, что было бы невозможно с примитивной рекурсивной функцией.

Обратите внимание, что ваш код повторяется,может быть, часть, которая действительно должна быть удалена, это:

input<-getLine
let guess = (read input :: Int)
checkGuess guess num

Answer 3

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

Таким образом, ваша хвостовая рекурсия в некотором роде, так как вы ничего не делаете после своего checkGuessвызывается рекурсивно.