2

Recursion is something I have always struggled with understanding. I hope I can get some assistance here on how this function works. It works but I want to know how:

fibStep :: (Int,Int) -> (Int,Int)
fibStep    (u,  v)    = (v,  u+v)

fibPair :: Int -> (Int,Int)
fibPair n
    | n==0      = (0,1)
    | otherwise = fibStep (fibPair (n-1))
maclunian
  • 7,893
  • 10
  • 37
  • 45
  • Can you explain what you've figured out so far? – Dhaivat Pandya May 17 '11 at 00:23
  • @Dhaivat Pandya I know what the `fibStep` function does. I just have no idea though about the `fibPair` function and how it relates back to `fibStep`. – maclunian May 17 '11 at 00:26
  • I recently wrote an answer to a similar question, it may help you too: http://stackoverflow.com/questions/5999356/trying-to-get-my-head-around-recursion-in-haskell/5999433#5999433 – sarnold May 17 '11 at 00:40
  • Are you any good at math? If you are, then try getting some basic combinatorics book and look through recursion, it will really clear up a lot. – Dhaivat Pandya May 17 '11 at 01:53

2 Answers2

3

Generally, when ever you're doing recursion, try working backwards and with small values, for example, if we pass fibPair with n=0, it immediately returns (0,1).

Then, if n=1, we get,

fibPair 1 = fibStep (fibPair 0) = fibStep (0, 1) = (1,1)

Then, with n=2 we get,

fibPair 2 = fibStep (fibPair 1) = fibStep (1,1) = (1,2)

So, as we can see, it gives you the nth pair of the fibonacci sequence by bringing it up from (0, 1).

If you still don't really understand it, try to expand out fibPair 2 fully (i.e. expand out fibStep (fibPair 1))

Dhaivat Pandya
  • 6,499
  • 4
  • 29
  • 43
  • doesn't `fibPair 2` have to work back to fibPair 0 before it can give an answer? If not, this doesn't make sense at all! – maclunian May 17 '11 at 00:45
  • Pandya already expanded `fibPair 1`, so they didn't bother expanding it again for `fibPair 2` simply for brevity. – erisco May 17 '11 at 00:57
  • @maclunian Yes it does. Dhaivat omitted that step brevity, as the expansion of `fibPair 1` was already explained. A full expansion would look like this: `fibPair 2` => `fibStep(fibPair 1)` => `fibStep(fibStep(fibPair 0))` => `fibStep(fibStep(0,1))` => `fibStep(1,1)` => `(1,2)`. – Ergwun May 17 '11 at 00:59
  • Thank you expanding it Ergwun, I should have done it myself, but I was sort of afraid of being beaten to getting an answer :) – Dhaivat Pandya May 17 '11 at 01:53
2

Recursion works much like a loop. With a loop you have a stop condition, and the same is true for recursion, except it is called the base case. In this Fibonacci example, the base case is n==0, which returns the tuple (0,1) -- and of course this represents the first Fibonacci number.

After you've established your base case, now you need to figure out the recursive step -- in this example it is fibStep (fibPair (n-1)). This is equivalent to the code block for a loop, or what step is repeated on every iteration until the base case has been reached. Naturally, it is critical that you make sure you always converge to your base case, else the recursion will never end -- and in the example, the recursive step does converge to the base case, because for each consecutive step, the value of n decreases by one, meaning we must eventually reach the case where n==0 (assuming n is initially positive).

Let us look at the evaluation of fibPair 3. Each consecutive line is an expansion of the previous, using the definitions provided in the example.

fibPair 3 **note: n is not 0 so we use the recursive step
fibStep (fibPair (3-1))
fibStep (fibPair 2) **note: n is not 0 use recursive step again
fibStep (fibStep (fibPair (2-1)))
fibStep (fibStep (fibPair 1)) **note: n is not 0 use recursive step again
fibStep (fibStep (fibStep (fibPair (1-1))))
fibStep (fibStep (fibStep (fibPair 0))) **note: n equals 0 so base case is used
                                        ** recursion has now ended
fibStep (fibStep (fibStep (0,1))) **note: now fibStep begins evaluation
fibStep (fibStep (1, 1))
fibStep (1, 2)
(2, 3)

Importantly, you should become comfortable with an English explanation of what is happening. fibStep takes a tuple of (fib number x, fib number x+1) and returns the next tuple in sequence, namely (fib number x+1, fib number x+2). fibPair acts as loop over fibStep, causing fibStep to be called n times on the same tuple, meaning the tuple (fib number x, fib number x+1) will result as (fib number x+n, fib number x+n+1).

Hopefully that helps clarify things a little bit. Recursion is truly just another way to write a loop; it has all of the same elements yet is written a bit differently. For some problems using recursion results in much simpler logic, or code, or both. Once you become more comfortable with recursion it will be a very useful tool to have for your future programming.

erisco
  • 14,154
  • 2
  • 40
  • 45
  • n does not equal 0. this is popular notation in many languages. in Haskell one would use `not n==0`. the hash is just notation to begin a comment; it is not part of the expression. – erisco May 17 '11 at 00:57
  • Or n /= 0. The Haskell notation was derived from the mathematical notation of a stroked out equality sign. – fuz May 17 '11 at 05:33
  • `not n==0` is a compile error by the way. `not (n == 0)` or, as has been noted, `n /= 0` are correct. – Rotsor May 17 '11 at 05:44