haskell - 我很困惑什么是递归，尾递归，原始递归，什么不是

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 中不需要这种优化(也请参阅下面的 hammar 评论)。

您的函数 checkGuess 可能看起来是尾递归的，但事实并非如此。 do语法是使用 >>= 的语法糖运算符(operator)。

f = do
    x <- g
    h x

转化为

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

因此，在几乎所有的 do 符号中，最后一个被调用的函数都是 >>= .

如果一个函数可以使用描述的 5 个构造来构造，则该函数是原始递归的 here .加法、乘法和阶乘是原始递归函数的例子，而阿克曼函数则不是。

这在可计算性理论中通常很有用，但就编程而言，人们通常并不关心(编译器不会尝试对此做任何事情)。

笔记:

如果一组函数相互调用的方式具有循环(f 调用g，g 调用h 并且h 最终调用f)，则可以说一组函数是相互递归的。