Recursion in Haskell

Haskell supports recursive functions. Here’s a classic example.

module Main where

-- This `fact` function calls itself until it reaches the
-- base case of `fact 0`.
fact :: Int -> Int
fact 0 = 1
fact n = n * fact (n - 1)

main :: IO ()
main = do
    print $ fact 7

    -- In Haskell, we don't need to declare recursive functions
    -- separately. We can define them directly.
    let fib :: Int -> Int
        fib n
            | n < 2 = n
            | otherwise = fib (n - 1) + fib (n - 2)

    print $ fib 7

In this Haskell version:

1. We define the fact function using pattern matching. The base case fact 0 = 1 is explicitly stated, and the recursive case follows.

2. The main function is where we execute our code.

3. In Haskell, we don’t need to explicitly declare recursive functions before defining them, as we do with closures in some other languages. We can define recursive functions directly, as shown with the fib function.

4. The fib function uses guards (|) instead of if-else statements to define its behavior for different input conditions.

To run this program, save it in a file named recursion.hs and use the following commands:

$ ghc recursion.hs
$ ./recursion
5040
13

This will compile the Haskell code and then run the resulting executable, which outputs the factorial of 7 and the 7th Fibonacci number.

Haskell’s strong support for recursion and pattern matching makes it particularly well-suited for implementing recursive algorithms in a clear and concise manner.