How to compile ahead of time a recursive function

Numba Support: How do I do ...?
1

Hi,

I am trying to compile ahead of time a recursive function, but i am not sure how to do it. Short snippet that reproduces the issue is below.

import numba
from numba.pycc import CC
cc = CC('fib')
cc.verbose = True

@numba.njit
@cc.export('rtnorm', 'i8(i8)')
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

if __name__ == "__main__":
    cc.compile()
2

Just a thought, but if you move the implementation to a regular jitted function does that help? Sometimes cfunc behaves a little different than njitted functions.

3

AOT compilation doesn’t support recursion, but I think this is not documented (or not very well documented) - there is a feature request issue for AOT compilation of recursive functions: Can't compile recursive function ahead of time · Issue #6513 · numba/numba · GitHub

4

Here’s a PR to document this limitation: Document that AOT compilation of recursive functions is unsupported by gmarkall · Pull Request #8577 · numba/numba · GitHub

5

Thanks for adding a note on this limitation to the docs @gmarkall.

There is a workaround for this problem and I’ve added it as an example on the PR above (#8577). The pycc compiler doesn’t support recursion but it can “compile in” calls to standard @njit compiled functions that do support recursion. It’s a little awkward having to have an additional call but the LLVM inliner will likely just remove it anyway.

Hope this helps.