A Beautiful Piece of Code

Without further ado, here it is:

(defun recursive-fibonacci (n first-term second-term)
    (let ((next-sum (+ first-term second-term)))
      (format t "Next sum: ~A ~%" next-sum)
      (unless (> next-sum n)
        (recursive-fibonacci n second-term next-sum))))

What is it?

What you see above is a function that will calculate the Fibonacci sequence up to n, recursively.

I'm relatively new to Lisp so this partial solution to a Project Euler problem (problem #2, to be specific) was the source of a few light bulb moments. Working through the problem helped me understand a lot more of how to work with Lisp.

Light Bulb #1: Recursion

Recursion is a programming technique where a function calls itself. Working through the aforementioned problem helped me reason about how recursion can be useful. I've solved this problem before with C# although I lost the code for it, unfortunately. From what I remember, I used a combination of a basic for loop to iterate up to a given number and add the terms of the Fibonacci sequence to an array. After the array was created, I probably had a second loop to iterate over the array to sum the even numbers from it.

I've learned a lot since my original attempt, and was able to produce this much simpler solution instead. Instead of using an array to manage state (state being the terms of the Fibonacci sequence in this context) we instead take a functional approach to the problem.

To calculate the Fibonacci sequence we only need two terms, which are just the preceding terms in the sequence. The recursive-fibonacci function takes three arguments: n being the number that we want to stop the sequence at when the summed terms is greater than, and then first-term and second-term being the two terms we want to add together.

Within the function, we define a local variable next-sum that is the sum of the first and second terms. After they are added together, we check to see the next sum in the sequence is greater than n and if not continue the recursion.

To continue the recursion, we call recursive-fibonacci from within itself and pass in n, and then second-term and next-sum as the next to terms in the sequence to add together. No need for an array to hold the state since it's all contained within the function itself and we don't need to keep the previous terms around.

Light Bulb #2: Prefix Notation

Prefix Notation is a style of notation where the operator precedes the operands. For example, instead of infix notation x + y where the operator + is in-between x and y, we would write it as + x y where the operator + precedes the operands x and y.

The light bulb here is that all of Lisp uses prefix notation. In a language like C# we have a combination of prefix, infix, and postfix notation. Here in Lisp everything is uniform. Once I realized that, the syntax became a whole lot more readable to me and it was much easier to reason about how to write it. It's almost a bit like Yoda speak.

Light Bulb #3: Functional Programming

This light bulb kind of piggybacks off of #1 as a more general bulb. I didn't need to use a "traditional" loop or create an array to accomplish the solution to this part of the problem. I just needed to pass the state back into the function and continue deeper into the recursion until the desired result was achieved, at which it would stop. In the context of the problem I didn't need to return the sum at the end but it would only require an additional line to make the function do that.

Closing