Arrays or lists are critical to any programming language. In Cairo you can think of arrays as a pointer to the first memory address in a list of contiguous memory addresses, all of which make up the array. We can create an array of felts (

from starkware.cairo.common.alloc import alloc

tempvar felt_array : felt* = new (1, 2, 3);

Both of these will work! The first one is more dynamic as you can continue to add to the array, while the second one is made for a fixed size array but is also much easier to write. In order to use the first example above, be sure the import statement is included at the top of your script.

. This is something to refer to in the docs for more detailed information, but effectively 

 stores the expression itself from the right side of the equal sign to the variable instead of the expression's value. On the other hand, 

 actually evaluates the expression and stores the value in the variable.

 was storing three times which is storing 

then x = 3, y = 27 and then z = 19683 (27^3).

Enough variable talk, the Mummies want to make sure you can analyze the slopes of their pyramid walls, so that is where we will start.

 that allow the assertions to pass. For this lesson use the 

https://www.cairo-lang.org/docs/reference/syntax.html

https://www.cairo-lang.org/docs/how_cairo_works/consts.html

Creating an array

We will take a step by step approach to solve our first recursion problem. For this lesson we will only be creating the function signature for the recursive function we will be calling.

Mummies love their pyramids to be crafted with precision. Consider the Great Pyramid of Giza, all the sides have a perfect 51.5 degree slope. We will be creating a function that verifies that the slope of each side of our pyramid is in the range of [51,52], or else the mummies will not be pleased.

. The reason we are setting up the function like this is because in Cairo we do not know the length of an array without actually keeping track of it in a separate variable. So the first parameter is a reference to the current element in the array and the second parameter represents how many elements there are until we reach the end of the array.

For this lesson simply create the function and return with 

. Note: This is an intermediate lesson to set up a function signature for a function that allows you to iterate through an array.

Writing Function Signatures For Recursing Through Array

If you are familiar with printing output, then you are free to skip this lesson by clicking 'Verify Answer' as we will not be verifying any code here. This is simply an instruction on how to print output for debugging and visibility purposes.

If you want to see what the value of a particular variable is during execution you can use the 

from starkware.cairo.common.serialize import serialize_word

, the import statement, and the funky squiggly braces with the 

 argument in order for this to work. Let's break down each of these parts:

are predefined optimized low-level execution units which are added to the Cairo CPU board to perform predefined computations which are expensive to perform in vanilla Cairo

: They are parts of the code that you would not want to write yourself at the lowest level because it would be hard and you would probably not write the code optimally.

The import statement is just bringing in the function 

Those funky squiggles are known as implicit arguments. We recommend reading the docs about them because they are a bit nuanced. 

: Implicit arguments allow for ease of passing arguments that you know a function in a chain of functions will eventually need. The 

 in this case so this is a common use case of having the implicit argument at the top of the chain of functions (starting at main), so it can propagate down the chain of function calls.

 statement to print some new variable you create and make sure the code compiles.

For official docs on implicits and builtins: 

https://www.cairo-lang.org/docs/how_cairo_works/builtins.html

Printing Output & Implicit Arguments

Now is the time to put your coding skills to the test. If you do not have any experience with recursion, have a look at the references down below.

Here is an example of implementing a factorial in Cairo using recursion:

func factorial(num : felt) -> (res : felt) {

    let (fact_res : felt) = factorial(num-1);

Here is an example of adding up all the values of an array:

    let (arr_sum : felt) = get_arr_sum(arr, 3);

    tempvar arr_1 : felt* = new(2,3,4,5);

    let (arr_sum_1 : felt) = get_arr_sum(arr_1, 4);

func get_arr_sum(arr : felt*, arr_len : felt) -> (res : felt) {

    let (sum_arr : felt) = get_arr_sum(arr+1, arr_len-1);

Refer to these two examples for help implementing your first recursive function. Remember to have a base case. For example, in the factorial we know that we can stop once we decrement the number to 1. In the array sum, we know that we can stop when we have reached the end of the array, ie the 

It is important to note that in this low-level language, there is no way to get the length of a 

 without knowing the length of that array already, so keep track of the length in a separate variable and use that to iterate through each element of the array. 

 to access the first element of the array. Similarly 

 would give you the second element of the array. 

The above syntax deals with accessing values in an array, but how do you move the pointer to a subsequent or previous address? The notation 

 both move the pointer from its current location to point at the next item in memory. The former directly moves the pointer down by one memory address (the size of a felt) and the latter accesses into the 1st index of the current pointer and then the 

 gets the address of that item in memory.

Moving the pointer is analogous to iterating to the next value in the array, so it is a common technique to do this before making a recursive call.

It is time for you to build the recursive function to check whether or not all the sides of a pyramid have slopes 51 or 52 degrees. Complete the lesson so the assertions all pass.

https://en.wikipedia.org/wiki/Recursion_(computer_science)

Implementing Recursive Logic

If you are new to Cairo or are experienced, you may have been frustrated with references being revoking. This is a frequent occurrence due to the fact that we have been using 

 to declare variables which rely on the allocation pointer (ap) - think of heap memory - rather than the frame pointer (fp) - think of stack memory.

You may have also noticed that we have organized our code in interesting ways in previous lessons... This was mainly to avoid revoked references.

Note that if there is a label or a call instruction (call to another function. See Functions) between the definition of a reference that depends on ap and its usage, the reference may be revoked, since the compiler may not be able to compute the change of ap (as one may jump to the label from another place in the program, or call a function that might change ap in an unknown way).

' We recommend reading through the references below to really understand revoked references well because they occur frequently in Cairo when not using 

 in most complex scenarios because the likelihood you will get a variable revoked is somewhat high. In simple functions, especially in functions that do not call other functions, 

Let's look at how to make use of these local variables and how they can make our lives better.

If you run these two script in your own code editor or 

 (make sure it is running on Cairo version 0.10.0 or higher) you will see that the first one succeeds, but the second one gets a revoked reference for 

. This is because the allocation pointer lost context of 

 and set it to a local in two steps or you can use the shortcut 

 ... as seen above. In two lines would look like:

 In Cairo you cannot unpack a function call directly into a local variable like:

Last thing to note is that in any function where you use local variables, you must declare 

 at the top of that function. This will handle advancing the allocation pointer for you so you do not have to manually keep everything in sync.

 on the first array and then the second array and returns 1 if both the pyramids are valid and 0 otherwise.

This is an exploratory lesson. Explore what causes functions to revoke references by changing variable instantiation from 

https://www.cairo-lang.org/docs/how_cairo_works/consts.html?highlight=local%20variable#local-vars

Local Variables

The Mummies also have a good sense of humor and love to see a silly looking pyramid. A silly looking pyramid can either be:

A negative pyramid - any pyramid that has all of its sides with slopes in the range [-89, -1].

A never ending pyramid - any pyramid that has all of its sides with slopes in the range [90, 179].

Our goal will be to check if the slopes of an array create a silly pyramid.

For this we will need to use a function from the Starknet math library 

, which will tell us if a value is less than or equal to another value. Here is an example:

from starkware.cairo.common.math_cmp import is_le

func main{output_ptr : felt*, range_check_ptr}() {

A couple of things to note here. In order to use the 

 (is less than or equal function), we need to add 

 to the list of builtins at the top of the file, each of which is separated by a space. Also, we need to import the function 

. We will be using more and more functions from Starknet libraries.

 will return 1 if the first value is less than or equal to the second value. Note: in Cairo to represent boolean values, use a 

The next thing we will do is return 2 values from our function, each of which is a 

. We could achieve this using one return variable but for the sake of the lesson you will have to solve with multiple return values.

 with values of 1 and 2 respectively in a function with input 

func my_func(x : felt) -> (y : felt, z : felt) {

 so that all the assertions pass. Make sure you use the 

. If you understand what a local variable is, you can use it in your functions, but try to achieve this just using 

Returning multiple values and more recursion

In order to complete this module, you will have to write three functions:

 which is 1 if true or 0 if false. What makes a pyramid valid? If an array of slopes of the sides of a pyramid are all in the range of [51, 52] then the pyramid is valid and up to the mummies' architectural standards. (The great pyramid at Giza has all of its sides exactly at 51.5 degrees).

 method once on the first array and then once on the second array, returning 1 if both the pyramids are valid and 0 otherwise.

, each of which is 1 if true or 0 if false. What makes a negative pyramid? Each of the slopes of the sides of the pyramid must be in the range [-89, -1], this would make a pyramid that closes and is upside down. What makes a never ending pyramid? Each of the slopes of the sides of the pyramid must be in the range [90, 179], as this would make the walls of the pyramid extend to the heavens forever.

Your goal is to make the script compile and run successfully. Good luck! If you understand what a 

 variable is, you can use it in your functions, but try to achieve this just using 

Solve the Module Without Help

Overview: In module two we will get an introduction to the intricacies of arrays. You will deal with recursing through these arrays of felts, known as felt*.

        What you will implement: For this section you will write a function that recurses through an array of numbers, representing the angle of each of the faces of the pyramid with the ground, and ensure the angles are within the safe range prescribed by the Mummies or are to their liking to build a joke pyramid.

        In this section we will cover: arrays (felt*), recursion, builtins, implicit arguments, imports and local variables. You can either skips the step by step lessons and solve the whole chapter or go step by step starting at Lesson 1. See you on the other side.

Module 1 - Meeting Your First Array