3 ms·

Here's my suggested Python code for a tail-recursive implementation that carries all the state it needs in a single function: def fib_tail_recurse(n, i=1,

Here's my suggested Python code for a tail-recursive implementation that carries all the state it needs in a single function: def fib_tail_recurse(n, i=1, cur_sum=1, prev_sum=0): if i >= n: return cur_sum return fib_tail_recurse(n, i+1, cur_sum+prev_sum, cur_sum)

kerkeslager 9y ago
Yeah, but... ~/$ python3 Python 3.6.3 (default, Oct 4 2017, 06:09:05) [GCC 4.2.1 Compatible Apple LLVM 8.0.0 (clang-800.0.42.1)] on darwin Type "help", "copyright", "credits" or "license" for more information. >>> import fib >>> fib.fib_tail_recurse(1000) Traceback (most recent call last): File "<stdin>", line 1, in <module> File "/Users/kerkeslager/fib.py", line 4, in fib_tail_recurse return fib_tail_recurse(n, i+1, cur_sum+prev_sum, cur_sum) File "/Users/kerkeslager/fib.py", line 4, in fib_tail_recurse return fib_tail_recurse(n, i+1, cur_sum+prev_sum, cur_sum) File "/Users/kerkeslager/fib.py", line 4, in fib_tail_recurse return fib_tail_recurse(n, i+1, cur_sum+prev_sum, cur_sum) [Previous line repeated 994 more times] File "/Users/kerkeslager/fib.py", line 2, in fib_tail_recurse if i >= n: RecursionError: maximum recursion depth exceeded in comparison >>> This is a perfect example of why tail recursion isn't actually very useful.
- discoursism 9y ago
  *in languages without tail call optimization.
  - kerkeslager 9y ago
    In languages which are functionally-focused enough that tail call optimization can be relied upon, higher-order functions are usually available and a better solution. See my post higher up.
    - bitwalker 9y ago
      I prefer to use recursion in a lot of cases in languages with pattern matching in function heads (e.g. Erlang or Elixir), particularly when each "case" deals with the accumulated state differently, which is more often than not. When you are doing simple maps/filters whatever, then yeah, higher order functions all the way.

kerkeslager 9y ago

Yeah, but... ~/$ python3 Python 3.6.3 (default, Oct 4 2017, 06:09:05) [GCC 4.2.1 Compatible Apple LLVM 8.0.0 (clang-800.0.42.1)] on darwin Type "help", "copyright", "credits" or "license" for more information. >>> import fib >>> fib.fib_tail_recurse(1000) Traceback (most recent call last): File "<stdin>", line 1, in <module> File "/Users/kerkeslager/fib.py", line 4, in fib_tail_recurse return fib_tail_recurse(n, i+1, cur_sum+prev_sum, cur_sum) File "/Users/kerkeslager/fib.py", line 4, in fib_tail_recurse return fib_tail_recurse(n, i+1, cur_sum+prev_sum, cur_sum) File "/Users/kerkeslager/fib.py", line 4, in fib_tail_recurse return fib_tail_recurse(n, i+1, cur_sum+prev_sum, cur_sum) [Previous line repeated 994 more times] File "/Users/kerkeslager/fib.py", line 2, in fib_tail_recurse if i >= n: RecursionError: maximum recursion depth exceeded in comparison >>> This is a perfect example of why tail recursion isn't actually very useful.

discoursism 9y ago
*in languages without tail call optimization.
- kerkeslager 9y ago
  In languages which are functionally-focused enough that tail call optimization can be relied upon, higher-order functions are usually available and a better solution. See my post higher up.
  - bitwalker 9y ago
    I prefer to use recursion in a lot of cases in languages with pattern matching in function heads (e.g. Erlang or Elixir), particularly when each "case" deals with the accumulated state differently, which is more often than not. When you are doing simple maps/filters whatever, then yeah, higher order functions all the way.