Multiple Recursive Calls
Explore how to write Haskell functions that use multiple recursive calls, using the Fibonacci sequence as a key example. Understand the inefficiency of naive recursion and learn to optimize it with helper functions. Apply these concepts by writing recursive functions that solve problems like counting distinct bit sequences.
We'll cover the following...
In the previous lesson, we started writing simple recursive functions. So far, all the functions that we looked at followed a simple recursive pattern of exactly one recursive call per equation. In this lesson, we will consider functions that require multiple recursive calls.
Fibonacci numbers
As an example, let’s write a function to compute the Fibonacci sequence.
The Fibonacci numbers are defined using a recursive equation. The first two Fibonacci numbers are 0 and 1. The successive numbers are obtained by adding the two previous numbers. This leads to the sequence
...