## Introduction

Cairo provides a built-in hash2 function to calculate the Pedersen hash of two felts. In this challenge, we will recursively compute the hash of an array of felts.

## The challenge

`ex_hash_chain.cairo`

```
// Task:
// Develop a function that is going to calculate Pedersen hash of an array of felts.
// Cairo's built in hash2 can calculate Pedersen hash on two field elements.
// To calculate hash of an array use hash chain algorithm where hash of [1, 2, 3, 4] is H(H(H(1, 2), 3), 4).
from starkware.cairo.common.cairo_builtins import HashBuiltin
from starkware.cairo.common.hash import hash2
// Computes the Pedersen hash chain on an array of size `arr_len` starting from `arr_ptr`.
func hash_chain{hash_ptr: HashBuiltin*}(arr_ptr: felt*, arr_len: felt) -> (result: felt) {
return (result=1);
}
```

`test_ex_hash_chain.cairo`

```
%lang starknet
from starkware.cairo.common.alloc import alloc
from starkware.cairo.common.cairo_builtins import HashBuiltin
from exercises.programs.ex_hash_chain import hash_chain
@external
func test_hash_chain{pedersen_ptr: HashBuiltin*}() {
alloc_locals;
let (local array: felt*) = alloc();
assert array[0] = 1;
assert array[1] = 4;
let (result) = hash_chain{hash_ptr=pedersen_ptr}(array, 2);
assert 1323616023845704258113538348000047149470450086307731200728039607710316625916 = result;
let (local array: felt*) = alloc();
assert array[0] = 2; // YES
assert array[1] = 100;
assert array[2] = 12;
assert array[3] = 2; // YES
assert array[4] = 422; // YES
assert array[5] = 898;
assert array[6] = 10;
assert array[7] = 31;
assert array[8] = 22;
assert array[9] = 5;
let (result) = hash_chain{hash_ptr=pedersen_ptr}(array, 10);
assert 2185907157710685805186499755291718313025201005027499629005977263373594646427 = result;
return ();
}
```

## Solution

```
from starkware.cairo.common.cairo_builtins import HashBuiltin
from starkware.cairo.common.hash import hash2
func hash_chain{hash_ptr: HashBuiltin*}(arr_ptr: felt*, arr_len: felt) -> (result: felt) {
if (arr_len == 2) {
return hash2([arr_ptr], [arr_ptr + 1]);
}
let (hash) = hash_chain(arr_ptr, arr_len - 1);
return hash2(hash, [arr_ptr + arr_len - 1]);
}
```

## Explain the solution

For a better explanation, I added another test case

```
let (local array: felt*) = alloc();
assert array[0] = 1;
assert array[1] = 2;
assert array[2] = 3;
assert array[3] = 4;
let (result) = hash_chain{hash_ptr=pedersen_ptr}(array, 4);
assert 2151680050850558576753658069693146429350618838199373217695410689374331200218 = result;
```

As usual, we handle the base case for our recursion function:

```
if (arr_len == 2) {
return hash2([arr_ptr], [arr_ptr + 1]);
}
```

The base case is to calculate the H(1, 2). Next, we handle the recursive case:

```
let (hash) = hash_chain(arr_ptr, arr_len - 1);
return hash2(hash, [arr_ptr + arr_len - 1]);
```

After the `arr_len`

reaches 2, the call stack starts to offload its box starting from the base case:

```
arr_len = 2
result = H(1, 2)
--------------------
arr_len = 3
hash = H(1, 2)
result = H(H(1 , 2), 3)
--------------------
arr_len = 4
hash = H(H(1 , 2), 3)
result = H(H(H(1 , 2), 3), 4)
done!
```

## Conclusion

I don't often use recursion in other languages which have loop standards. However, since there is no loop in Cairo, things usually get done by recursion. I am getting used to it.

I hope you found this guide insightful. If you have any questions, feel free to reach out. Happy coding!

Here is the Github repo for the code in this article

## Top comments (0)