Recursion is defining a function in terms of itself via self-referential expressions.
Recursion is an important concept in Haskell and in mathematics because it gives us a means of expressing indefinite or incremental computation without forcing us to explicitly repeat ourselves.
One of the classic examples for demonstrating recursion is factorial.
Let's evaluate 3!:
3! = 3 * 2 * 1
6 * 1
6
Here is some broken Haskell code to implement factorial (it's broken because there's no base case):
brokenFactorial :: Integer -> Integer
brokenFactorial x = x * brokenFactorial (x - 1)
This code never stops running because there is no base case.
We can break it by writing a base case:
brokenFactorial :: Integer -> Integer
brokenFactorial 0 = 1
brokenFactorial x = x * brokenFactorial (x - 1)
Having a base case allows the program to stop running.
Bottom is a term used in Haskell to refer to computations that do not successfully result in a value.
GHCi can detect expressions that will never return:
Prelude> let x = x in x
*** Exception: <<loop>>
Another classic demonstration of recursion is a function that calculates the nth number in a Fibonacci sequence.
The Fibonacci sequence is a sequence of numbers in which each number is the sum of the previous two: 1, 1, 2, 3, 5, 8...
fibonacci :: Integral a => a -> a
fibonacci 0 = 0 -- first base case
fibonacci 1 = 1 -- second base case
fibonacci x =
fibonacci (x - 1) + fibonacci (x - 2)
x = 4
fibonacci 4 = fibonacci 3 + fibonacci 2
fibonacci 3 = fibonacci 2 + fibonacci 1
fibonacci 2 = fibonacci 1 + fibonacci 0 -- recursion is broken
fibonacci 0 + 0
fibonacci 1 + 1
fibonacci 2 + (1 + 0) = 1
fibonacci 3 = (1 + 1) = 2
fibonacci 4 = (1 + 2) = 3
CS Dojo Introduction to Recursion - https://www.youtube.com/watch?v=B0NtAFf4bvU
Haskell Book - https://haskellbook.com/