Are recursive functions allowed?

[anton-trunov]

What happens if I try to use recursion in contract methods, standalone functions or getters? The answer should include mutual recursion too.

[novusnota]

Yes, recursion is allowed. Though, the maximum depth is to be discovered. And, I suppose, there's no tail call optimization, but that also requires a check.

In any case, here's a global static function fib() computing the n-th number of the Fibonacci sequence:

import "@stdlib/deploy";

fun fib(n: Int): Int {
    if (n <= 0) { return 0; }
    if (n == 1) { return 1; }
    return fib(n - 1) + fib(n - 2); 
}

contract Fibonacci with Deployable {
    init() {} // just in case of running this with Tact 1.2.0
    get fun fib(n: Int): Int {
        return fib(n);
    }
}

[anton-trunov]

Pretty neat! We absolutely need to have this in the Tact test suite: https://github.com/tact-lang/tact/issues/303

[novusnota]

Though, the maximum depth is to be discovered.

For the Sandbox, the maximum n for fib(n) seems to be 20 — that's the last n that computes without giving the error code -14.

Because this recursive implementation of fib() function calls itself twice on almost each turn, that gives roughly O(2^n) in computational complexity. Therefore, maximum depth for WASM-based execution in the Sandbox is about 1048576 recursive calls.

[novusnota]

And, I suppose, there's no tail call optimization, but that also requires a check.

So, we can optimize our recursive function using the iterative approach. Not sure if this counts as a tail call optimization, but getter functions are indeed quite powerful:

import "@stdlib/deploy";

fun fibTail(n: Int, a: Int, b: Int): Int {
    if (n <= 0) { return a; }
    if (n == 1) { return b; }
    return fibTail(n - 1, b, a + b);
}

contract FibonaccisTail with Deployable {
    init() {} // just in case of running this with Tact 1.2.0
    get fun fibTail(n: Int): Int {
        return fibTail(n, 0, 1);
    }
}

It's able to compute the 370-th number of the sequence! Any more than that cause error code 4, which is Integer overflow (that a + b addition gets too big even for Int type)

P.S.: For the reference, the 370-th Fibonacci number is 94611056096305838013295371573764256526437182762229865607320618320601813254.

[anton-trunov]

What about mutually recursive functions? Are these allowed?

[Gusarich]

the maximum depth is to be discovered

it is unlimited by default in Mainnet's TVM as I know. and -14 error that you got in result of testing means "out of gas", not stack overflow.