Recursive Functions – Haskell

Haskell encourages a different style of thinking compared to imperative languages. One of the most powerful techniques in Haskell is recursion. The term recursive refers to a process or function that repeats itself in a self-similar way. In programming, recursive functions are a fundamental concept that allow you to define solutions by breaking down a problem into smaller instances of itself.

Authors Note ✏️

For some reason the term “recursive” doesn’t stick for me. Perhaps because you rarely use the term outside of programming. Here’s some synonyms for “recursive” that helped me:

• Looping
• Repetitive
• Iterative
• Circular
• Returning back
• Recurring

“Looping functions” would be so much simpler!

In this article, we will explore the basics of recursion in Haskell, how it works, when to use it, and how it fits naturally with Haskell’s functional paradigm.

What is a Recursive Function?

A recursive function is a function that calls itself in order to solve smaller instances of the same problem. The function typically has two mandatory parts:

1. Base case: A simple, non-recursive case where the function can return a value directly without calling itself. Recursive functions always need a base case. The base case is what stops the recursion and prevents infinite loops. Without a base case, the function would continue calling itself indefinitely, causing a stack overflow.
2. Recursive case: A case where the function calls itself with a smaller or simpler input, eventually converging to the base case.

In essence, recursion is about solving a large problem by reducing it into smaller, more manageable problems.

Example of a Recursive Function: Factorial

One of the most famous examples of recursion is the factorial function. The factorial of a number n (written as n!) is the product of all integers from 1 to n.

The factorial of 5, for example, is: 5! = 5 × 4 × 3 × 2 × 1 = 120

Recursive Factorial Function in Haskell:

factorial :: Int -> Int
factorial 0 = 1  -- Base case: 0! is defined as 1
factorial n = n * factorial (n - 1)  -- Recursive case: n! = n * (n-1)!

Here’s how it works:

• Base case: If n is 0, the function returns 1, which is the definition of 0!.
• Recursive case: If n is greater than 0, the function multiplies n by the factorial of n - 1, which keeps reducing the problem until it hits the base case.

Example Usage:

factorial 5  -- Result: 120
factorial 0  -- Result: 1

The function calls itself repeatedly, reducing n by 1 each time, until n reaches 0, at which point it starts returning values back up the chain.

Another Example: Sum of a List

Let’s look at another example where recursion is often used: calculating the sum of all elements in a list.

Recursive Sum Function:

sumList :: [Int] -> Int
sumList [] = 0  -- Base case: The sum of an empty list is 0
sumList (x:xs) = x + sumList xs  -- Recursive case: Sum is head + sum of tail

Here’s how it works:

• Base case: If the list is empty ([]), the sum is 0.
• Recursive case: If the list has at least one element (x:xs), the function adds x (the head of the list) to the result of calling sumList on xs (the tail of the list).

Example Usage:

sumList [1, 2, 3, 4]  -- Result: 10
sumList []            -- Result: 0

The function recursively reduces the list by breaking it into its head (x) and tail (xs), summing up the elements until the list is empty.

Authors Note ✏️

In Haskell, the tail of a list refers to everything but the head. Specifically, the tail function returns a new list containing all the elements of the original list except the first one (the head).

Example:

• If you have the list [1, 2, 3, 4]:
• The tail is [2, 3, 4].
• The head is 1.

When to Use Recursive Functions in Haskell

Recursion is a natural fit for many problems in Haskell, especially when dealing with recursive data structures like lists and trees. Recursion is used when:

• A problem can be broken down into smaller subproblems.
• You can define a base case to stop the recursion.
• Iteration (using loops) is not preferred because Haskell favors immutable data and pure functions.

For example:

• Working with lists: Functions like map, filter, and fold often use recursion under the hood to process lists.
• Tree structures: Recursive functions are commonly used to traverse and manipulate trees.

Pros and Cons of Recursion

Pros:

• Simplicity: Recursive functions can simplify the code for problems that naturally involve breaking down a task into smaller parts.
• Expressiveness: Recursion allows you to write code that closely mirrors the problem’s structure, leading to more readable code.
• Avoids mutable state: Recursion avoids the need for mutable loops or variables, which is aligned with Haskell’s functional programming principles.

Cons:

• Performance: Recursive functions can be less efficient than iterative ones in some cases because each recursive call consumes stack space. This can lead to performance issues or stack overflows for deep recursions.
• Tail call optimization: Haskell supports tail recursion, where recursive calls can be optimized to avoid growing the call stack. However, non-tail-recursive functions (like the naive factorial above) may not benefit from this optimization.

To write efficient recursion, tail recursion is often recommended, as it allows the compiler to optimize and reuse stack frames.

Tail Recursion in Haskell

In tail recursion, the recursive call is the last operation in the function. This allows the compiler to optimize the recursion and avoid building up the call stack.

Example: Tail-Recursive Factorial

A tail-recursive version of the factorial function can be written using an accumulator:

factorialTR :: Int -> Int -> Int
-- Base case: Return the accumulated result
factorialTR 0 acc = acc  
-- Recursive case with accumulator
factorialTR n acc = factorialTR (n - 1) (n * acc) 

-- Wrapper function to start the recursion with an accumulator of 1
factorial :: Int -> Int
factorial n = factorialTR n 1

Here:

• factorialTR carries an additional argument (acc), which accumulates the result as the recursion proceeds. Since the recursive call is the last operation, this function is tail-recursive.

Example Usage:

factorial 5  -- Result: 120

ELI5 (Explain Like I’m 5): What is Recursion?

Imagine you have a stack of boxes, each with a smaller box inside. The largest box at the top contains a smaller box, and that smaller box contains an even smaller one, and so on, down to the last, smallest box, which is empty.

To open the boxes, you do this:

1. Open the top box (the largest one).
2. Take out the next box and repeat the process with that one.
3. Keep going until you reach the smallest box, which is empty.

Once you open the smallest, empty box, you’re done. Now, you work your way back up the stack, having opened all the boxes one by one.

In a recursive function, the function does the same thing: it calls itself to handle smaller pieces of the problem (like opening each smaller box), until it reaches the simplest case (like the smallest, empty box). Once it reaches the simplest case, it works its way back up to solve the whole problem.

Conclusion

Recursive functions are a powerful tool in Haskell that allow you to break down complex problems into simpler, more manageable pieces. They fit naturally into Haskell’s functional paradigm, and they are often used to process lists, trees, and other recursive data structures. By understanding how to define a base case and a recursive case, you can solve many problems in a clear and expressive way.

While recursion may have performance concerns in some situations, particularly with deep recursions, you can often mitigate these with tail recursion. Mastering recursion will significantly enhance your ability to write efficient and idiomatic Haskell code.

💡 Helpful References

Learn You a Haskell - Syntax in Functions
https://learnyouahaskell.github.io/syntax-in-functions.html

Learn You a Haskell - Recursion
https://learnyouahaskell.github.io/recursion.html

Frequently Asked Questions about Recursive Functions in Haskell

1. What is a recursive function?

A recursive function is a function that calls itself in order to solve a problem. In Haskell, recursion is a common technique for breaking down a problem into smaller subproblems until a base case is reached, at which point the recursion stops.

2. Do recursive functions always need a base case?

Yes, recursive functions always need a base case. The base case is what stops the recursion and prevents infinite loops. Without a base case, the function would continue calling itself indefinitely, causing a stack overflow.

3. What happens if a recursive function doesn’t have a base case?

If a recursive function doesn’t have a base case, it will result in infinite recursion, which will eventually lead to a stack overflow or memory exhaustion. The function will keep calling itself without ever terminating.

4. What is tail recursion, and why is it important?

Tail recursion is a special kind of recursion where the recursive call is the last operation in the function. In tail-recursive functions, there are no pending operations after the recursive call, which allows the compiler to optimize the recursion and reuse stack frames, preventing stack overflow.

Example of a tail-recursive factorial:

factorialTR :: Int -> Int -> Int
factorialTR 0 acc = acc  -- Base case
factorialTR n acc = factorialTR (n - 1) (n * acc)  -- Recursive case with accumulator

Here, the recursive call factorialTR (n - 1) (n * acc) is the last operation, making it tail-recursive.

5. How do recursive functions work with lists in Haskell?

Recursive functions are often used to process lists in Haskell. You typically define a base case for an empty list ([]), and a recursive case that breaks down the list into its head (x) and tail (xs), then processes the tail recursively.

Example: Summing a list:

sumList :: [Int] -> Int
sumList [] = 0  -- Base case: the sum of an empty list is 0
sumList (x:xs) = x + sumList xs  -- Recursive case: sum head + sum of the tail

6. What are the advantages of using recursion in Haskell?

• Simplicity: Recursive solutions often mirror the problem’s structure, making the code more intuitive.
• No loops: Haskell doesn’t rely on loops like imperative languages; recursion replaces iterative constructs.
• Immutable data: Recursion works naturally with Haskell’s immutable data structures, especially lists.
• Modularity: Recursive functions break problems into smaller, modular subproblems, allowing for more elegant solutions.

7. Are recursive functions efficient in Haskell?

Recursive functions can be efficient in Haskell, especially when they are tail-recursive. Haskell’s lazy evaluation can optimize recursive functions by only evaluating expressions when needed. However, non-tail-recursive functions that build up a large stack of deferred operations can lead to performance issues or stack overflow.

8. Can recursion cause stack overflow in Haskell?

Yes, recursion can lead to stack overflow if the recursive calls are not optimized, especially when they are not tail-recursive. To avoid this, it’s recommended to use tail recursion or functions like foldl' (a strict version of foldl) to avoid building up large chains of deferred operations.

9. How do I write a tail-recursive function in Haskell?

To write a tail-recursive function, ensure that the recursive call is the last operation in the function and that any accumulated values are passed along as arguments (usually through an accumulator).

Example: Tail-recursive sum of a list:

sumListTR :: [Int] -> Int -> Int
sumListTR [] acc = acc  -- Base case
sumListTR (x:xs) acc = sumListTR xs (acc + x)  -- Tail-recursive call

10. When should I use recursion instead of other approaches?

Use recursion when:

• The problem can be naturally broken down into smaller subproblems.
• You are working with recursive data structures like lists or trees.
• You want to avoid mutable state and iterative loops.

Recursion is idiomatic in Haskell and is often the cleanest, most elegant way to solve many problems, especially when working with immutable data structures.

11. What is mutual recursion?

Mutual recursion occurs when two or more functions call each other in a recursive manner. This technique can be used to solve problems where multiple functions are needed to complete the recursion.

isEven :: Int -> Bool
isEven 0 = True
isEven n = isOdd (n - 1)

isOdd :: Int -> Bool
isOdd 0 = False
isOdd n = isEven (n - 1)

Here, isEven and isOdd are mutually recursive, each calling the other in their recursive case.

12. How do I avoid common pitfalls when writing recursive functions?

To avoid common pitfalls in recursion:

• Always define a base case to prevent infinite recursion.
• Make sure that your recursive case makes progress toward the base case (e.g., reducing a number or shrinking a list).
• Use tail recursion when possible to improve efficiency and avoid stack overflow.
• Test your functions with both small and large inputs to ensure they work correctly and efficiently.