## DEV Community # Cairo: compute Pedersen hash of an array of felts challenge

## 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 = 1;
assert array = 4;
let (result) = hash_chain{hash_ptr=pedersen_ptr}(array, 2);
assert 1323616023845704258113538348000047149470450086307731200728039607710316625916 = result;

let (local array: felt*) = alloc();
assert array = 2; // YES
assert array = 100;
assert array = 12;
assert array = 2; // YES
assert array = 422; // YES
assert array = 898;
assert array = 10;
assert array = 31;
assert array = 22;
assert array = 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 = 1;
assert array = 2;
assert array = 3;
assert array = 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!