Journey Through Cairo VI — Mastering Recursion

Welcome to the sixth article, in our series, “Journey through Cairo”. In our last article which can be found here, we explained Implicit Arguments in Cairo.

Today, we’d be taking a deep dive into Recursions, and how they function generally in Cairo. As always, if you are just joining mid-flight, endeavour to checkout the previous articles, to better understand and flow with this series.

P.S: All code snippets used in this tutorial, makes use of the old Cairo syntaxes from Cairo-lang v0.9.0, since its what was used in our Starklings exercises as at the time of this writing.

Arrays Are Mythical..

One of the shocking things i heard when starting out with Cairo was i couldn’t write loops. No for loops, no while loops etc, just Recursions..

The main reason for this is that the Cairo memory is immutable, i.e once you write the value of a memory cell, this cell cannot change in the future.

This for the most part was quite discouraging, but thankfully, we’d be seeing an update to this in the upcoming Cairo 1.0.

What Is Recursion?

In computer science, recursion is a programming technique using function or algorithm that calls itself one or more times until a specified condition is met at which time the rest of each repetition is processed from the last one called to the first.

In simpler terms, if a function calls itself repeatedly, that function is a recursive function. Note that the function must have a base condition that stops the recursion, or the program might experience stack overflow.

Recursions are quite complex, took me a while to fully understand, so don’t beat yourself if you don’t get it in the first read. To better explain Recursions, we’d go through some Starklings challenges.

recursion01.cairo

In this exercise, we are expected to write a recursive implementation of fibonacci numbers that returns the nth fibonacci number.

To solve this exercise, we’d need to first understand what a fibonacci number is.

The Fibonacci series is a series of numbers in which each number ( Fibonacci number ) is the sum of the two preceding numbers. An example of the first 13 numbers in the series are:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144

From the definition above, we can place that for us to get the nth fibonacci number, we’d need to add the nth — 1 number and the nth — 2 number. (Since each number is the sum of the two preceding numbers). In mathematical form:

nth number = (nth - 1) + (nth - 2)

So let’s assume we want to find the 5th Fibonacci number, we’d have:

Fib(5) = Fib(4) + Fib(3)

From the 13 numbers we already derived earlier, Fib(4) = 2 and Fib(3) = 1. Therefore:

Fib(5) = 2 + 1 = 3

We could easily derive this since we had to do this for a small nth number (5), but imagine we were asked to get the 100th Fibonacci number, we can’t just do this manually, we’d need to write a program to do that.

We could have easily done this using a for loop, if we were on Javascript, Python, Solidity etc, but since Cairo doesn’t support for loop yet, we’d use Recursions with the following steps:

1. First we’d need to note that as we are writing a computer program, our first Fibonacci number would have an index of 0 rather than 1.
2. We’d establish our base cases, to avoid stack overflow. Since we already know the first and second fibonacci numbers are always 0 and 1, we’d want to check our n and automatically return 0 if its a 0, or return 1 if its a 1:

if n == 0:
  return (0)
end

if n == 1:
  return (1)
end

3. Since the nth fibonacci term is the sum of the nth -1 and the nth -2 numbers, we’d need to get these numbers using recursions (which calls the fibonacci function passing unto it the n — 1 and the n — 2 terms as the new n):

let (x) = fibonacci(n - 1)
let (y) = fibonacci(n - 2)

4. Lastly, we’d return their summations:

return (x + y)

Here’s the full code:

func fibonacci(n : felt) -> (result : felt):
  alloc_locals
  if n == 0:
    return (0)
  end
  if n == 1:
    return (1)
  end
  let (local x) = fibonacci(n - 1)
  let (local y) = fibonacci(n - 2)
  return (x + y)
end

You’d notice, we introduced some new stuffs such as alloc_locals, and the local keyword, this is due to revoked references, which we’d be taking a deep dive into in the next episode of this series.

Now lets check if our test passes:

Yes it does!

array01.cairo

Recursions have huge applications in Arrays similar to with loops.

In this exercise, we are expected to loop through the contains function, and return 1 if the haystack contains the needle, or return 0 otherwise.

To solve this exercise, we’d follow our steps from the fibonacci exercise.

1. We’d need to establish our base case.

• To do this, we’d first need to check if the given array length (haystack_len) is 0 and if yes, we’d automatically return 0 since this means that the array is empty:

if haystack_len == 0:
  return (0)
end

. Next we’d check if the first element in our array is the needle, and if yes, we’d automatically return 1 which would save computation costs.

if haystack[0] == needle:
  return (1)
end

2. We’d recursively loop through the contains function

let (contained) = contains(needle, haystack + 1, haystack_len - 1)
return (contained)

What we did here is, using recursion, we loop through the contains function, each time increasing the array index we are checking by 1, and decreasing the array length by 1.

The logic behind this is, each time we recurse through the contains function, we try to make the array inputs smaller and keep it diminishing till we get to the last element in the array. Here’s a scenario to help you understand this better:

If we have an array, x and needle = 3:

x = [0, 1, 2, 3, 4, 5]

We check our base cases:

if array length is 0, we’d return 0, but it is not, so we move over to check if x[0] = needle, but it is not as x[0] = 0, but needle = 3.

Next we’d begin recursion:

we’d call the contains function, this time passing the needle, then we’d push the array index up by 1 to be x + 1 rather than x, and then decrease the array length by 1 also since we just popped the first element out from the array.

so whilst the first contains function call, would have looked like this:

contains(3, [0, 1, 2, 3, 4, 5], 6)

the second function call would look like this:

contains(3, [1, 2, 3, 4, 5], 5)

And it goes on like that till we finally get to an array length of 0.

Our full code solution should look like this:

func contains(needle : felt, haystack : felt*, haystack_len : felt) -> (result : felt):
  if haystack_len == 0:
    return (0)
  end
  if haystack[0] == needle:
    return (1)
  end
  let (contained) = contains(needle, haystack + 1, haystack_len - 1)
  return (contained)
end

Now let’s check if we passed the challenge:

Voila! We did.

Conclusion

We’ve made significant progress since we began this series, a big kudos to you for making it this far.

As you’d notice, in order to shorten this article, we’ve attempted only 2 out of the 7 exercises in the recursion section of Starklings.

I’d encourage you to attempt the remaining 5 exercises as it’d help increase your understanding of Recursions. Do note, that if you run into any challenges, you could check my github repo here for my solutions, or reach out to me via Twitter.

As always, If you got value from this article, do well to share with others.

You could also connect with me on the following socials, especially on Twitter, where i share my little findings on Cairo!

Twitter: https://twitter.com/0xdarlington

LinkedIn: https://www.linkedin.com/in/nnamdarlington

Github: https://github.com/Darlington02