In a previous blog post, I mentioned a little bit of recursive function in Haskell, and about how they works.
Today we are going deeper into recursive functions, especially in Haskell.
A typical property of problems solvable by recursion is divide-and-conquer -- first divide the problem into its subproblems, then merge the result in a certain way.
To be more specific, we apply three steps at each level of recursion:
Divide the problem into a number of subproblems that are smaller instances of the same problem.
Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner.
Combine the solutions to the subproblems into the solution for the original problem Last time, I gave a example of recursive function in my blog -- Fibonacci function, today I will take it apart analyse it.
fib :: Integer -> Integer
fib x
' x < 1 = error "n should be greater than 0"
' x == 1 = 1
' x == 2 = 2
' otherwise = fib (x - 1) + fib (x - 2)
How do we divide the problem of finding the nth Fibonacci number?
We know that, by definition, a Fibonacci number is the sum of the previous two Fibonacci number. we break the problem into the subproblem, finding its previous two Fibonacci number.
How to conquer the problem?
If the subproblem is simple enough, it is straight forward, we have already know the 1st and 2nd Fibonacci number, just simply plug it in. (Of course, you can put more cases in the code.)
If it is not that simple, well, continue by solving its subproblem, of course.
How do we combine the solution?
This one is straight forward. Once we obtained the previous two Fibonacci number, we just summing them up and return the result.
However, if I tell you that there are some problem in the code above, it might be kind of hard to see.
In our previous Fibonacci number function, Fibonacci number function is called multiple times on a single argument.
For example, if we want to calculate the 5th Fibonacci number -- fib 5, we will calculate fib 4 and fib 3. However, in the calculation of fib 4, we calculated fib 2 and again fib 3. Clearly, fib 3 is been calculated multiple times.
To generalize, the algorithm given above has a cubic order of growth -- with the size of input growing linearly, the time complexity, or the running time of the program, grows as it is a cubic function.
To solve this problem in the algorithm, we can either use memorization or introduce a new helper function. I will discuss it in the next blog post.