How do you optimize recursive functions in Haskell? Explain with an example.?

In Haskell, you can optimize recursive functions using a technique called memoization. Memoization involves storing the results of expensive function calls and returning the cached result when the same inputs occur again. This can be useful for recursive algorithms that repeatedly call the same function with the same arguments, like in dynamic programming problems.

In Haskell, we often use a data structure called a lazy list to memoize function results. Lazy lists are infinite lists where elements are computed on-demand, and once the value is computed, it is stored in the list for future reference.

Let’s take an example of the classic Fibonacci sequence problem, which can be naively defined as a recursive function like this:

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

The naive implementation has an exponential running time (O(2n̂)) due to the repeated computation of the same Fibonacci numbers. We can optimize this recursive function by using memoization through lazy lists.

First, let’s create the infinite Fibonacci list using the ‘zipWith‘ function, which combines two lists element-wise using a given function:

fibList :: [Integer]
fibList = 0 : 1 : zipWith (+) fibList (tail fibList)

Here, ‘fibList‘ is defined as a lazy list with the first two Fibonacci numbers (0 and 1) and then the rest of the Fibonacci numbers calculated by adding the element-wise sum from ‘fibList‘ and its tail.

Now, we can create a memoized ‘fib‘ function that just accesses elements from our ‘fibList‘:

memoizedFib :: Integer -> Integer
memoizedFib n = fibList `genericIndex` n

By using memoization, we have optimized the recursive Fibonacci function from exponential runtime to linear complexity (O(n)).

Let’s visualize the difference between the running times of the naive and memoized implementations:

In this example chart, we can see that the memoized implementation (blue) has a significantly lower computation time compared to the naive implementation (red) as n increases. This optimization is a result of avoiding the redundant computations through memoization.