Julia Iterate, Recursion and Closure

Fibonacci Series as an Example
using Julia's capabilities like Iterate, recursion, and closures
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.
Loops with Julia Simple Loop

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).
Loops with Julia Julia Iterators
Now we’ll define an iterate function that works exclusively for FibStruct
Loops with Julia Julia Iterators

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 of repeated calculations increase. To solve that we can save the values of our calculations so that we won’t need to recalculate them.
Recursion with Julia Simple Recursion

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.
Recursion with Julia Simple Recursion

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.
Closures with Julia Julia Closures

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

Julia Closures Using Loops
Using recursion
Julia Closures Using recursion

Using closures

Julia Closures Using closures

Author: Mohamed Sayed
Editor: Sherif Adel