CODEWITHSUNDEEP
haskellrecursionfunctional-programmingtail-recursion
n00b
n00b

Reputation: 911

I'm confused about what's recursive, tail recursive, primitive recursive and what's not

I've written a simple guess the number program and I need to know if there is any kind of recursion involved in it, and what kind it is (primitive/tail) (I'm new to this so please bear with me)

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

Upvotes: 3

Views: 2197

Answers (3)

Jedai
Jedai

Reputation: 1477

A function is recursive if it calls itself anywhere in its code. So guessNum isn't (no call to guessNum in guessNum code or in code it calls), and checkGuess is.

Tail recursion is when the recursive call is the last thing the function do... but this is Haskell and tail recursion is a term mainly intended for strict languages where it allows to optimize a recursive function so that it doesn't grow the stack (the current invocation can be straightforwardly replaced by the recursive one since you won't need to do anything after the recursive call returns). So as others have said checkGuess isn't tail recursive or wouldn't be in a strict language... However with lazy semantics, (a >> b) will be evaluated to b in many Monads (IO included) since once a is evaluated (or rather the IO action is done), it can be forgotten and the return of b is the only thing that matter.

In a nutshell, your function checkGuess is recursive, not tail recursive by most formal definitions but those definitions aren't adapted to non-strict languages like Haskell, and checkGuess will most definitely be executed in constant space as if it was tail recursive in a strict language (at least with reasonable implementations of Haskell, such as GHC).

Primitive recursion is a notion defined on N^k -> N functions, I don't think the question makes sense for such a function as checkGuess, not without some doubtful adaptation and looking at a translation of the function in some simpler language (lamda-calculus equivalent) which would means making explicit IO semantics and so on... I would say though that your function doesn't do anything with its Int parameter that wouldn't be possible with a primitive recursive function.

Note that your code repeats itself, maybe the part that should really be abstracted away is :

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

Upvotes: 1

aelguindy
aelguindy

Reputation: 3711

A function is recursive if it calls itself (not necessarily in every case, but at least in one case). For example:

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

The function above is not however tail recursive. In the second equation, x and sum xs are first computed and the final result is their sum. Since the final result is not a call to the function, it is not tail recursive. To convert this function to tail recursive, we can use the accumulator pattern:

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

Notice now in the second equation first calculates xs and x + acc and as a final step it calls itself. Tail recursive functions are important because they can be systematically transformed to loops, eliminating the overhead of function calls. Some languages do this optimization, I think this optimization is not necessary in Haskell (see hammar's comment below too).

Your function checkGuess might seem tail recursive but it is not. The do syntax is syntactic sugar for using the >>= operator.

f = do
    x <- g
    h x

is transformed to

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

therefore, in almost every do notation the last function to be called is >>=.

A function is primitive recursive if it can be constructed using the 5 constructs described here. Addition, multiplication and factorial are examples of primitive recursive functions, while the Ackermann function is not.

This is usually useful in theory of computability but as far as programming goes, one normally does not care (the compiler does not try to do anything about it).

Notes:

  • One can say that a group of functions are mutually recursive if the way they call each other has cycles (f calls g, g calls h and h eventually calls f).

Upvotes: 12

SoWhat
SoWhat

Reputation: 5622

Tail recursion is when you do nothing after the function calls itself This is generally done by returning with the next recursion call.

So yours is a tail recursion in a way, since you do nothing after your checkGuess is called recursively.

Upvotes: 0

Related Questions