我很困惑什么是递归,尾递归,原始递归和什么不是

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被首先计算,并且最后的结果是它们的总和.由于最终结果不是对函数的调用,因此它不是尾递归的.要将此函数转换为tail递归,我们可以使用累加器模式:

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

现在请注意在第二个公式首先计算xs和x + acc并作为最后一步是调用自身.尾递归函数很重要,因为它们可以系统地转换为循环,从而消除了函数调用的开销.有些语言进行了这种优化,我认为在Haskell中这种优化是不必要的(参见下面的hammar评论).

你的函数checkGuess可能看似尾递归,但事实并非如此.该do语法使用语法糖>>=运营商.

f = do
    x <- g
    h x

变成了

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

因此,在几乎所有的符号中,最后一个要调用的函数是>>=.

如果函数可以使用此处描述的5个构造构造,则它是原始递归的.加法,乘法和阶乘是原始递归函数的例子,而阿克曼函数则不是.

这在可计算性理论中通常很有用,但就编程而言,人们通常并不关心(编译器不会尝试对其进行任何操作).

笔记:

• 可以说一组函数是相互递归的,如果它们相互调用的方式有周期(f调用g,g调用h和h最终调用f).