Salt: For CentOS minions test.fib runtime increases exponentially or returns recursion depth error

[seanacais]

Description of Issue/Question

For CentOS minions test.fib doesn't return or returns recursion depth error

Setup

(Please provide relevant configs and/or SLS files (Be sure to remove sensitive info).)
No special setup.

Steps to Reproduce Issue

(Include debug logs if possible and relevant.)

$ sudo salt -G 'os:CentOS' test.fib 10
myapps:
    - 55
    - 4.79221343994e-05
ciao:
    - 55
    - 5.91278076172e-05

Works as expected if a little slow.

$ sudo salt -G 'os:CentOS' test.fib 32
myapps:
    - 2178309
    - 4.28802800179
ciao:
    - 2178309
    - 5.14673304558
$ sudo salt -G 'os:CentOS' test.fib 33
myapps:
    - 3524578
    - 7.12137389183
ciao:
    - 3524578
    - 8.18820476532

$ sudo salt -G 'os:CentOS' test.fib 34
myapps:
    - 5702887
    - 11.472121954
ciao:
    - 5702887
    - 13.4241538048
$ sudo salt -G 'os:CentOS' test.fib 35
myapps:
    - 9227465
    - 17.7961521149
ciao:
    - 9227465
    - 21.4182200432
$ sudo salt -G 'os:CentOS' test.fib 36
myapps:
    - 14930352
    - 30.3570690155
ciao:
    - 14930352
    - 35.0243809223

Run times get longer as you go for higher numbers

$ salt -G "os:CentOS" test.fib 100
(By the time you get to 100 not patient enough to wait for completion)

$ salt -G "os:CentOS" test.fib 1000
(returns the following repeated many, many times)

      File "/usr/lib/python2.6/site-packages/salt/modules/test.py", line 338, in _fib
        return _fib(num-1) + _fib(num-2)
    RuntimeError: maximum recursion depth exceeded

Versions Report

(Provided by running salt --versions-report. Please also mention any differences in master/minion versions.)

$ sudo salt '*' test.version
myapps:
    2016.11.1
ciao:
    2016.11.4

[gtmanfred]

This is not a bug. This is the way the Fibonacci sequence works. As the numbers get larger it takes more time to compute the answer, and over 1000, the python recursion depth is reached.

Thanks,
Daniel

[thatch45]

@seanacais if you would like to submit a non-recursive implementation of the Fibonacci sequence so that the recursion depth limit is not reached we would be happy to merge it, but seeing how this is only in Salt because I thought it would be fun to add as a way to test how salt behaves with computationally intensive long running tasks I must say this it is working as expected.

[DmitryKuzmenko]

I've rewrote the fibo to the loop algorithm that has a linear performance and no memory limit. Actually there is a more efficient matrix algorithm but it's less readable and if it's needed math module is the place for it 😄