NEWTON

NEWTON

# How to make recursive function in Cairo Lang?

3 months ago

137

views

0

Hello! This is day 7 of the 17 days of the Cairo Challenge. And I have no idea how to solve the playground exercise “Recursion”. Perhaps you can help me?

``````// The following code prints the sum of the numbers from 1 to 10.
// Modify the function `compute_sum` to print all the intermediate sums:
// 1, 1 + 2, 1 + 2 + 3, ..., 1 + 2 + ... + 10.
// Note: you'll have to add the implicit argument output_ptr to the
// declaration of compute_sum (in order to use the serialize_word function):
//   func compute_sum{output_ptr: felt*}(n: felt) -> (sum: felt)

// Use the output builtin.
%builtins output

from starkware.cairo.common.serialize import serialize_word

func compute_sum(n: felt) -> (sum: felt) {
if (n == 0) {
// When 0 is reached, return 0.
return (sum=0);
}

// Otherwise, call `compute_sum` recursively to compute 1 + 2 + ... + (n-1).
let (sum) = compute_sum(n=n - 1);
// Add the new value `n` to the sum.
let new_sum = sum + n;
return (sum=new_sum);
}

func main{output_ptr: felt*}() {
let (res) = compute_sum(n=10);

// Output the result.
serialize_word(res);
return ();
}
``````

Answers to this question are a part of the ✨ 17 days of Cairo Lang with Playground & Newton. ✨

Vote for your favorite answer - the best answer will win a \$10 award. A new day – a new reward! During the next 17 days, our goal is to attract more developers to the Cairo language and to systematize the knowledge of Cairo lang. Read rules

#17daysOfCairocairo-beginnerscairoplayground

Newton

3 months ago

0

``

``````// The following code prints the sum of the numbers from 1 to 10.
// Modify the function `compute_sum` to print all the intermediate sums:
// 1, 1 + 2, 1 + 2 + 3, ..., 1 + 2 + ... + 10.
// Note: you'll have to add the implicit argument output_ptr to the
// declaration of compute_sum (in order to use the serialize_word function):
//   func compute_sum{output_ptr: felt*}(n: felt) -> (sum: felt)

// Use the output builtin.
%builtins output

from starkware.cairo.common.serialize import serialize_word

func compute_sum{output_ptr: felt*}(n: felt) -> (sum: felt) {
if (n == 0) {
// When 0 is reached, return 0.
return (sum=0);
}

// Otherwise, call `compute_sum` recursively to compute 1 + 2 + ... + (n-1).
let (sum) = compute_sum(n=n - 1);
// Add the new value `n` to the sum.
let new_sum = sum + n;
serialize_word(new_sum);
return (sum=new_sum);
}

func main{output_ptr: felt*}() {
let (res) = compute_sum(n=10);

// Output the result.
//serialize_word(res);
return ();
}
``````

Prashant Banchhor

3 months ago

0

First things first - why recursion?

Because, in the time of writing this answer, loops don't exist in Cairo in the classical sense, so we need to use recursion in order to traverse an array. Read more here.

Solution

1. add `{output_ptr: felt*}` to the `compute_sum` function sgnature. like so:
``````func compute_sum{output_ptr: felt*}(n: felt) -> (sum: felt) {
``````
1. Add this line `serialize_word(new_sum);` to print the intermediary results:
``````let new_sum = sum + n;
serialize_word(new_sum);
return (sum=new_sum);
``````

-1

My answer with comments that may help to understand the execution of recursion

``````%builtins output

from starkware.cairo.common.serialize import serialize_word

func compute_sum{output_ptr: felt*}(n: felt) -> (sum: felt) {
// serialize_word(n) -> print 10, 9, 8, 7, ... 0
if (n == 0) {
// When 0 is reached, return 0.
return (sum=0);
}
let (sum) = compute_sum(n=n - 1);
// serialize_word(n) -> print 1, 2, 3, 4, ... 10
let new_sum = sum + n;
serialize_word(new_sum); // --> print 1, 3, 6, ... 55
return (sum=new_sum);
}

func main{output_ptr: felt*}() {
let (res) = compute_sum(n=10);

// Output the result.
// serialize_word(res);
return ();
}
``````

Repository challenge

-1

# Solution

``````%builtins output

from starkware.cairo.common.serialize import serialize_word

func compute_sum{output_ptr: felt*}(n: felt) -> (sum: felt) {
if (n == 0) {
// When 0 is reached, return 0.
return (sum=0);
}

// Otherwise, call `compute_sum` recursively to compute 1 + 2 + ... + (n-1).
let (sum) = compute_sum(n=n - 1);
// Add the new value `n` to the sum.
let new_sum = sum + n;
//print all the intermediate sums
serialize_word(new_sum);
return (sum=new_sum);
}

func main{output_ptr: felt*}() {
let (res) = compute_sum(n=10);

return ();
}
``````

# Output

``````Program output:
1
3
6
10
15
21
28
36
45
55

Number of steps: 129
Program hash: 0x034b8ec64f54dafcc743d1af9fbfe33a41b62f19d1849abcdfe3f78dc0b51afb
``````

# Explanation

main function calls compute_sum function by passing an argument of number of natural number(n=10). compute_sum function perform recursion by calling itself. It calls itself till n equal to zero. when base condition reached the sum returned to from where it got called. At this point sum equal to zero and n equal to 1 which results 1 and assigned it to new_sum and then print is using serialize_word. This repeats again sum equal to 1 and n equal to 2 which results in 3.It continues til n equal to 10.

0

``````
from starkware.cairo.common.serialize import serialize_word

func compute_sum{output_ptr: felt*}(n: felt) -> (sum: felt) {
if (n == 0) {
// When 0 is reached, return 0.
return (sum=0);
}

// Otherwise, call `compute_sum` recursively to compute 1 + 2 + ... + (n-1).
let (sum) = compute_sum(n=n - 1);
// Add the new value `n` to the sum.
let new_sum = sum + n;
serialize_word(n);
return (sum=new_sum);
}

func main{output_ptr: felt*}() {
let (res) = compute_sum(n=10);

// Output the result.
serialize_word(res);
return ();
}
``````

3 months ago