Fibonacci sequence: Difference between revisions
Content added Content deleted
GordonBGood (talk | contribs) (→{{header|Mathematica}} / {{header|Wolfram Language}}: improve recursion; added iterative approach, list generator...) |
GordonBGood (talk | contribs) (→{{header|Python}}: new section on faster recursion not requiring memoization, and its limits...) |
||
| Line 4,757: | Line 4,757: | ||
<pre> |
<pre> |
||
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040</pre> |
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040</pre> |
||
===Better Recursive doesn't need Memoization=== |
|||
The recursive code as written two sections above is incredibly slow and inefficient due to the nested recursion calls. Although the memoization above makes the code run faster, it is at the cost of extra memory use. The below code uses much more efficient recursion that doesn't require memoization: |
|||
<lang python>def fibFastRec(n): |
|||
if n < 2: return n |
|||
else: |
|||
def fib(prvprv, prv, c): |
|||
if c < 1: return (prvprv + prv) |
|||
else: return fib(prv, prvprv + prv, c - 1) |
|||
return fib(0, 1, n - 2)</lang> |
|||
However, although much faster and not requiring memory, the above code can only process to a limited 'n' due to the limit on stack recursion depth by Python; it is better to use the iterative approach above or the generative one below. |
|||
===Generative=== |
===Generative=== |
||