In this blog, we’ll guide you through different Julia capabilities like Iterate, recursion, and closures. We will show code snippets of how to use these features in Julia using a simple example of the Fibonacci sequence. We’ll start with a simple for loop and then see how we can use Julia’s multiple dispatches with Base. iterate. Also, we’ll show the simple recursive method and an optimized version of recursion. Finally, we’ll talk about closures.
Fibonacci sequence is a sequence of numbers such as each number is a result of summing up the previous two numbers.
1, 1, 2, 3, 5, 8, 13, 21, …, etc
Loops with Julia
Simple Loop
The natural way of approaching Fibonacci sequence is to start with a=0, b=1 and keep adding those variables along the way to the target sequence.
Julia Iterators
One of Julia’s powerful features is the use of multiple-dispatch. This allows any function to have multiple implementations based on the type of passed arguments. So in our case, we’ll need to have a struct that holds the info of the current iteration and to pass it to Base. iterate to generate a new Fibonacci sequence at each iteration.
In our case, the struct will be holding an integer that refers to the current Fibonacci index (in other cases, you can make your own complex structs with many fields and new functions as a constructor).
Now we’ll define an iterate function that works exclusively for FibStruct
Recursion with Julia
Simple Recursion
By applying the top-down approach from given N until reaching the base case 0, we can do the following with Julia but this approach is very slow. We may not even be able to compute higher numbers before the end of the day or crash the memory.
The problem is that when we are trying to calculate the fifth Fibonacci element we’ll calculate the Fibonacci of `2` twice. Every time you calculate a higher number repeated calculations increase. To solve that we can save the values of our calculations so that we won’t need to recalculate them.
Optimized Recursion
Now every time we calculate the Fibonacci of a number, we’ll save the value of that number in a dictionary or array. In this way, we won’t recalculate values as it’s already saved in the dictionary and we will also have to pass this dictionary at each time as a parameter.
Closures with Julia
Julia Closures
The closure is a combination of functions bonded with its surrounding states such as other outer variables or functions. It provides you with an easier and cleaner way to make a function with changing state without needing to create a struct or class.
Now we’ll use closures to build a function `get_next_number` that keeps generating Fibonacci sequence.
Since we need to save the values of `a` & `b` along the way, we’ll be declaring them in the outer function `fib_closure`, Then to calculate nth Fibonacci, we’ll need to loop n times until reaching the nth Fibonacci number.
Conclusions
Julia Closures
In this blog, we’ve explained Julia’s iterate, recursion, and closures via a Fibonacci series example. As a comparison, we can measure the time of each function and the allocated memory using BenchmarkTool.jl while calculating the 90th Fibonacci number.
Note: If you try a higher number than 93, you’ll have an overflow. You may want to use other data types like UInt64, Int128, UInt128, or BigInt.
Using loops has less computation time and no memory was allocated. On the other side, closure is better than the recursion with respect to both the computation time and the allocated memory
Using Loops
Using recursion
Using closures
Author: Mohamed Sayed
Editor: Sherif Adel