我写了一个简单的猜测数字程序,我需要知道它是否涉及任何类型的递归,以及它是什么类型(原始/尾部)(我是新手,所以请耐心等待)

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!"

最佳答案

如果函数调用自身(不一定在每种情况下,但至少在一种情况下),则该函数是递归的。例如:

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

然而,上面的函数不是尾递归的。在第二个方程中,首先计算 xsum xs,最终结果是它们的和。由于最终结果不是对函数的调用,因此它不是尾递归的。要将这个函数转换为尾递归,我们可以使用累加器模式:
sum [] acc = acc
sum (x:xs) acc = sum xs (x + acc)

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

您的函数 checkGuess 可能看起来是尾递归的,但事实并非如此。 do 语法是使用 >>= 运算符的语法糖。
f = do
    x <- g
    h x

转化为
f = g >>= (\x -> h x)

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

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

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

笔记:
  • 如果一组函数相互调用的方式有循环(f 调用g,g 调用h,h 最终调用f),则可以说一组函数是相互递归的。
  • 关于haskell - 我很困惑什么是递归,尾递归,原始递归,什么不是,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/9138760/

    10-11 22:08
    查看更多