我写了一个简单的猜测数字程序,我需要知道它是否涉及任何类型的递归,以及它是什么类型(原始/尾部)(我是新手,所以请耐心等待)
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
然而,上面的函数不是尾递归的。在第二个方程中,首先计算
x
和 sum xs
,最终结果是它们的和。由于最终结果不是对函数的调用,因此它不是尾递归的。要将这个函数转换为尾递归,我们可以使用累加器模式: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)
因此,在几乎所有的 do 符号中,最后一个被调用的函数都是
>>=
。如果一个函数可以使用 here 中描述的 5 个构造来构造,则该函数是原始递归的。加法、乘法和阶乘是原始递归函数的例子,而阿克曼函数则不是。
这在可计算性理论中通常很有用,但就编程而言,人们通常并不关心(编译器不会尝试对此做任何事情)。
笔记:
关于haskell - 我很困惑什么是递归,尾递归,原始递归,什么不是,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/9138760/