Cairo
Recursion

Recursion

Cairo doesn't support familiar loop constructs such as for, while or do while. However one can express loops via recursion which is defined as a function calling itself.

The following example shows how the Fibonacci Sequence can be computed via recursion in Cairo.

Example

func fibonacci(n : felt) -> (result : felt):
    # We're using `alloc_locals` here to avoid reference revocations.
    alloc_locals

    # Every recursion should terminate at some point so we define
    #   if statements here that return regular values rather than a call to
    #   the function itself.
    # Note: Start by writing these termination rules when you turn a loop into
    #   a recursion to make authoring recursions easier.
    if n == 0:
        return (0)
    end
    if n == 1:
        return (1)
    end

    # Here's "the meat" of the recursion as we're calling the function
    #   itself again.
    let (fib_1) = fibonacci(n - 1)
    let (fib_2) = fibonacci(n - 2)

    return (fib_1 + fib_2)
end

func sum(n : felt, running_total : felt) -> (result : felt):
    if n == 0:
        return (running_total)
    end

    # This is a special form of recursion called "Tail Recursion".
    # Tail Recursion occurs when a function ends by calling a second function
    #   immediately.
    # Tail Recursion are more efficient as they can utilize a technique called
    #   ["Tail Call Optimization"](https://en.wikipedia.org/wiki/Tail_call).
    return sum(n - 1, running_total + n)
end

func main():
    let (result) = fibonacci(10)
    assert result = 55

    let (result) = sum(20, 0)
    assert result = 210

    return ()
end