3 ms·

In practice iteration will be faster, even in Python (because there's less overhead). But yes, I should have written "naive recursive solution". There are many

• eru 6y ago
  In Python, yes. If you have a decent language and a good compiler / interpreter, then the recursion with function calls will have no overhead over iteration. (Basically, in Haskell or Scheme your recursion will be compiled into the same machine language sequence of straight-line code plus conditional jump as the iterative loop.) But, agreed with everything else you wrote!
  • ajuc 6y ago
    I can't be sure without measuring, but I strongly suspect the overhead will be mostly in tuple packing/unpacking and GC. And I instinctively distrust Sufficiently Smart Compilers ;)
    • eru 6y ago
      Oh, your compiler doesn't have to be sufficiently smart. It merely has to avoid premature optimization: see this classic paper https://dspace.mit.edu/handle/1721.1/5753 https://dspace.mit.edu/handle/1721.1/5753 by Guy Steele. > I can't be sure without measuring, but I strongly suspect the overhead will be mostly in tuple packing/unpacking and GC. I guess that's the same overhead as in this imperative version: a, b = 0, 1 for _ in range(n): a, b = b, a + b
  • tom_mellior 6y ago
    > If you have a decent language and a good compiler / interpreter, then the recursion with function calls will have no overhead over iteration. The recursive Python version above didn't use tail calls. I don't think that a Haskell or Scheme compiler would compile the equivalent versions into a simple loop.
    • eru 6y ago
      I just tried it out, I didn't manage to get GHC to compile the equivalent of the code I've given into something that runs in constant memory. (I did the calculations modulo some number, to keep the numbers themselves bounded.) GHC is sometimes able to do some of those transformations. > The recursive Python version above didn't use tail calls. Just to be more pedantic: it did use tail calls, but the recursive calls weren't the tail calls.
      • tom_mellior 6y ago
        > Just to be more pedantic: it did use tail calls, but the recursive calls weren't the tail calls. I was talking about this code: def fib(n): if n =< 0: return (0, 1) else: a, b = f(n-1) return (b, a + b) Not sure what you mean by tail calls here. I don't see Python-level tail calls. The interpreter will call C code for tuple packing, but those aren't in tail position with respect to the Python code either.
        • eru 6y ago
          The last call (to a function or operator) is in the tail position. In this case, it is tuple packing. Why wouldn't the tuple packing be in tail position in the Python code?
          • tom_mellior 6y ago
            Because after tuple packing returns (a C return) you still need to perform a Python return. The C tuple packing function cannot return directly from the Python function. Looking at https://github.com/python/cpython/blob/master/Python/ceval.c https://github.com/python/cpython/blob/master/Python/ceval.c, here is the code that needs to be executed after the tuple is constructed: case TARGET(RETURN_VALUE): { retval = POP(); assert(f->f_iblock == 0); assert(EMPTY()); f->f_state = FRAME_RETURNED; f->f_stackdepth = 0; goto exiting; } // ... exiting: if (tstate->use_tracing) { if (tstate->c_tracefunc) { if (call_trace_protected(tstate->c_tracefunc, tstate->c_traceobj, tstate, f, PyTrace_RETURN, retval)) { Py_CLEAR(retval); } } if (tstate->c_profilefunc) { if (call_trace_protected(tstate->c_profilefunc, tstate->c_profileobj, tstate, f, PyTrace_RETURN, retval)) { Py_CLEAR(retval); } } } /* pop frame */ exit_eval_frame: if (PyDTrace_FUNCTION_RETURN_ENABLED()) dtrace_function_return(f); _Py_LeaveRecursiveCall(tstate); tstate->frame = f->f_back; return _Py_CheckFunctionResult(tstate, NULL, retval, __func__); I guess you could duplicate all this code in a special "pack tuple and return from Python function" C function which you could then really tail call.
  • crimsonaluca20 6y ago
    >(Basically, in Haskell or Scheme your recursion will be compiled into the same machine language sequence of straight-line code plus conditional jump as the iterative loop.) This is not true. The recursive code will not compile with zero overhead even in haskell or lisp. fib :: int -> int fib 0 = 1 fib 1 = 1 fib n = fib (n - 1) + fib (n - 2) The code above will add layers to the call stack and has a speed complexity of O(N) and memory complexity of O(N). To optimize in Haskell you need to deliberately restructure your code. fib :: int -> int fib n = let _fib 0 a b = a _fib 1 a b = b _fib n a b = fib (n - 1) b (a + b) in _fib n 0 1 The above code will have O(N) speed complexity and constant memory in Haskell. In order for Haskell or any language with tail recursion optimization to work the recursive call must take up the entire return expression. In short the coder must deliberately make optimizations and write recursion in a way similar to the original iterative syntax in order for such tricks to work.
    • eru 6y ago
      Yes. Though GHC is sometimes able to do some simple transformations on its own. But not in this case. For anyone trying this at home: I suggest calculating your additions modulo some constant, so that the numbers involved stay within a fixed size. (Otherwise, you either hit the limits of Int and weird things can happen, or when calculating with the arbitrary precision type Integer, your numbers themselves will grow linearly in space.)