NEWTON

NEWTON


Popular tags

    How to make recursive function in Cairo Lang?

    Asked

    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

    asked

    3 months ago


    5 answers

    0

    Accepted answer

    My answer:

    ``

    // 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

    answered

    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

    My answer for today's challenge:

    
    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 ();
    }
    

    answered

    3 months ago

    Your answer

    NEWTON

    NEWTON