These other answers are somewhat misleading. I agree that they state implementation details that can explain this disparity, but they overstate the case. As correctly suggested by jmite, they are implementation-oriented toward broken implementations of function calls/recursion. Many languages implement loops via recursion, so loops are clearly not going to be faster in those languages. Recursion is in no way less efficient than looping (when both are applicable) in theory. Let me quote the abstract to Guy Steele's 1977 paper Debunking the "Expensive Procedure Call" Myth or, Procedure Implementations Considered Harmful or, Lambda: the Ultimate GOTO

Folklore states that GOTO statements are "cheap", while procedure calls are "expensive". This myth is largely a result of poorly designed language implementations. The historical growth of this myth is considered. Both theoretical ideas and an existing implementation are discussed which debunk this myth. It is shown that the unrestricted use of procedure calls permits great stylistic freedom. In particular, any flowchart can be written as a "structured" program without introducing extra variables. The difficulty with the GOTO statement and the procedure call is characterized as a conflict between abstract programming concepts and concrete language constructs.

The "conflict between abstract programming concepts and concrete language constructs" can be seen from the fact that most theoretical models of, for example, the untyped lambda calculus, don't have a stack. Of course, this conflict is not necessary as the above paper illustrates and as is also demonstrated by languages who have no iteration mechanism other than recursion such as Haskell.

Let me demonstrate. For simplicity, I'll use an "applied" lambda calculus with numbers and and booleans, and I'll assume we have a fixed-point combinator, fix, which satisfies fix f x = f (fix f) x. All of this can be reduced to just the untyped lambda calculus without changing my argument. The archetypal way of understanding the evaluation of the lambda calculus is through term rewriting with the central rewrite rule of beta reduction, namely where means "replace all free occurrences of in with " and means "rewrites to". This is just the formalization of substituting the arguments of a function call into the functions body.

Now for an example. Define fact as

fact = fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 1

Here's the evaluation of fact 3, where, for compactness, I'll use g as synonym for fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)), i.e. fact = g 1. This doesn't affect my argument.

fact 3 
~> g 1 3
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 1 3 
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 1 3
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 1 3
~> (λn.if n == 0 then 1 else g (1*n) (n-1)) 3
~> if 3 == 0 then 1 else g (1*3) (3-1)
~> g (1*3) (3-1)
~> g 3 2
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 3 2
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 3 2
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 3 2
~> (λn.if n == 0 then 3 else g (3*n) (n-1)) 2
~> if 2 == 0 then 3 else g (3*2) (2-1)
~> g (3*2) (2-1)
~> g 6 1
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 6 1
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 6 1
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 6 1
~> (λn.if n == 0 then 6 else g (6*n) (n-1)) 1
~> if 1 == 0 then 6 else g (6*1) (1-1)
~> g (6*1) (1-1)
~> g 6 0
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 6 0
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 6 0
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 6 0
~> (λn.if n == 0 then 6 else g (6*n) (n-1)) 0
~> if 0 == 0 then 6 else g (6*0) (0-1)
~> 6

You can see from the shape without even looking at the details that there is no growth and each iteration needs the same amount of space. (Technically, the numeric result grows which is unavoidable and just as true for a while loop.) I defy you to point out the boundlessly growing "stack" here.

It seems the archetypal semantics of the lambda calculus already does what is commonly misnamed "tail call optimization". Of course, no "optimization" is happening here. There are no special rules here for "tail" calls as opposed to "normal" calls. For this reason, it's hard to give an "abstract" characterization of what tail call "optimization" is doing, as in many abstract characterizations of function call semantics, there is nothing for tail call "optimization" to do!

That the analogous definition of fact in many languages "stack overflows", is a failure by those languages to correctly implement function call semantics. (Some languages have an excuse.) The situation is roughly analogous to having a language implementation that implemented arrays with linked lists. Indexing into such "arrays" would then be an O(n) operation which doesn't meet the expectation of arrays. If I made a separate implementation of the language, that used real arrays instead of linked lists, you wouldn't say I've implemented "array access optimization", you would say I fixed a broken implementation of arrays.

So, responding to Veedrac's answer. Stacks are not "fundamental" to recursion. To the extent that "stack-like" behavior occurs during the course of evaluation, this can only happen in cases where loops (without an auxiliary data structure) would not be applicable in the first place! To put it another way, I can implement loops with recursion with exactly the same performance characteristics. Indeed, Scheme and SML both contain looping constructs, but both of them define those in terms of recursion (and, at least in Scheme, do is often implemented as a macro that expands into recursive calls.) Similarly, for Johan's answer, nothing says a compiler must emit the assembly Johan described for recursion. Indeed, nothing says a compiler can't emit exactly the same assembly whether you use loops or recursion. The only time the compiler would be (somewhat) obligated to emit assembly like what Johan describes is when you are doing something that isn't expressible by a loop anyway. As outlined in Steele's paper and demonstrated by the actual practice of languages like Haskell, Scheme, and SML, it is not "exceedingly rare" that tail calls can be "optimized", they can always be "optimized". Whether a particular use of recursion will run in constant space depends on how it is written, but the restrictions you need to apply to make that possible are the restrictions you'd need to fit your problem into the shape of a loop. (Actually, they are less stringent. There are problems, such as encoding state machines, that are more cleanly and efficiently handled via tails calls as opposed to loops which would require auxiliary variables.) Again, the only time recursion requires doing more work is when your code isn't a loop anyway.

My guess is Johan is referring to C compilers which have arbitrary restrictions on when it will perform tail call "optimization". Johan also is presumably referring to languages like C++ and Rust when he talks about "languages with managed types". The RAII idiom from C++ and present in Rust as well makes things which superficially look like tail calls, not tail calls (because the "destructors" still need to be called). There have been proposals to use a different syntax to opt-in to a slightly different semantics that would allow tail recursion (namely call destructors before the final tail call and obviously disallow accessing "destroyed" objects). (Garbage collection has no such issue, and all of Haskell, SML, and Scheme are garbage collected languages.) In a quite different vein, some languages, such as Smalltalk, expose the "stack" as a first-class object, in these cases the "stack" is no longer an implementation detail, though this doesn't preclude having separate types of calls with different semantics. (Java says it can't due to the way it handles some aspects of security, but this is actually false.)

In practice, the prevalence of broken implementations of function calls come from three main factors. First, many languages inherit the broken implementation from their implementation language (usually C). Second, deterministic resource management is nice and does make the issue more complicated, though only a handful of languages offer this. Third, and, in my experience, the reason most people care about, is that they want stack traces when errors occur for debugging purposes. Only the second reason is one that can be potentially theoretically motivated.

is recursion ever faster than a loop?

No, Iteration will always be faster than Recursion. (in a Von Neumann Architecture)

Explanation:

If you build the minimum operations of a generic computer from scratch, "Iteration" comes first as a building block and is less resource intensive than "recursion", ergo is faster.

Building a pseudo-computing-machine from scratch:

Question yourself: What do you need to compute a value, i.e. to follow an algorithm and reach a result?

We will establish a hierarchy of concepts, starting from scratch and defining in first place the basic, core concepts, then build second level concepts with those, and so on.

1. First Concept: Memory cells, storage, State. To do something you need places to store final and intermediate result values. Let’s assume we have an infinite array of "integer" cells, called Memory, M[0..Infinite].

2. Instructions: do something - transform a cell, change its value. alter state. Every interesting instruction performs a transformation. Basic instructions are:

   a) Set & move memory cells

   • store a value into memory, e.g.: store 5 m[4]
   • copy a value to another position: e.g.: store m[4] m[8]

   b) Logic and arithmetic

   • and, or, xor, not
   • add, sub, mul, div. e.g. add m[7] m[8]

3. An Executing Agent: a core in a modern CPU. An "agent" is something that can execute instructions. An Agent can also be a person following the algorithm on paper.

4. Order of steps: a sequence of instructions: i.e.: do this first, do this after, etc. An imperative sequence of instructions. Even one line expressions are "an imperative sequence of instructions". If you have an expression with a specific "order of evaluation" then you have steps. It means than even a single composed expression has implicit “steps” and also has an implicit local variable (let’s call it “result”). e.g.:

   4 + 3 * 2 - 5
   (- (+ (* 3 2) 4 ) 5)
   (sub (add (mul 3 2) 4 ) 5)  
   

   The expression above implies 3 steps with an implicit "result" variable.

   // pseudocode
   
          1. result = (mul 3 2)
          2. result = (add 4 result)
          3. result = (sub result 5)
   

   So even infix expressions, since you have a specific order of evaluation, are an imperative sequence of instructions. The expression implies a sequence of operations to be made in a specific order, and because there are steps, there is also an implicit "result" intermediate variable.

5. Instruction Pointer: If you have a sequence of steps, you have also an implicit "instruction pointer". The instruction pointer marks the next instruction, and advances after the instruction is read but before the instruction is executed.

   In this pseudo-computing-machine, the Instruction Pointer is part of Memory. (Note: Normally the Instruction Pointer will be a “special register” in a CPU core, but here we will simplify the concepts and assume all data (registers included) are part of “Memory”)

6. Jump - Once you have an ordered number of steps and an Instruction Pointer, you can apply the "store" instruction to alter the value of the Instruction Pointer itself. We will call this specific use of the store instruction with a new name: Jump. We use a new name because is easier to think about it as a new concept. By altering the instruction pointer we're instructing the agent to “go to step x“.

7. Infinite Iteration: By jumping back, now you can make the agent "repeat" a certain number of steps. At this point we have infinite Iteration.

                      1. mov 1000 m[30]
                      2. sub m[30] 1
                      3. jmp-to 2  // infinite loop
   

8. Conditional - Conditional execution of instructions. With the "conditional" clause, you can conditionally execute one of several instructions based on the current state (which can be set with a previous instruction).

9. Proper Iteration: Now with the conditional clause, we can escape the infinite loop of the jump back instruction. We have now a conditional loop and then proper Iteration

   1. mov 1000 m[30]
   2. sub m[30] 1
   3. (if not-zero) jump 2  // jump only if the previous 
                           // sub instruction did not result in 0
   
   // this loop will be repeated 1000 times
   // here we have proper ***iteration***, a conditional loop.
   

10. Naming: giving names to a specific memory location holding data or holding a step. This is just a "convenience" to have. We do not add any new instructions by having the capacity to define “names” for memory locations. “Naming” is not a instruction for the agent, it’s just a convenience to us. Naming makes code (at this point) easier to read and easier to change.

       #define counter m[30]   // name a memory location
       mov 1000 counter
    loop:                      // name a instruction pointer location
        sub counter 1
        (if not-zero) jmp-to loop  
    

11. One-level subroutine: Suppose there’s a series of steps you need to execute frequently. You can store the steps in a named position in memory and then jump to that position when you need to execute them (call). At the end of the sequence you'll need to return to the point of calling to continue execution. With this mechanism, you’re creating new instructions (subroutines) by composing core instructions.

    Implementation: (no new concepts required)

    • Store the current Instruction Pointer in a predefined memory position
    • jump to the subroutine
    • at the end of the subroutine, you retrieve the Instruction Pointer from the predefined memory location, effectively jumping back to the following instruction of the original call

    Problem with the one-level implementation: You cannot call another subroutine from a subroutine. If you do, you'll overwrite the returning address (global variable), so you cannot nest calls.

    To have a better Implementation for subroutines: You need a STACK

12. Stack: You define a memory space to work as a "stack", you can “push” values on the stack, and also “pop” the last “pushed” value. To implement a stack you'll need a Stack Pointer (similar to the Instruction Pointer) which points to the actual “head” of the stack. When you “push” a value, the stack pointer decrements and you store the value. When you “pop”, you get the value at the actual Stack Pointer and then the Stack Pointer is incremented.

13. Subroutines Now that we have a stack we can implement proper subroutines allowing nested calls. The implementation is similar, but instead of storing the Instruction Pointer in a predefined memory position, we "push" the value of the IP in the stack. At the end of the subroutine, we just “pop” the value from the stack, effectively jumping back to the instruction after the original call. This implementation, having a “stack” allows calling a subroutine from another subroutine. With this implementation we can create several levels of abstraction when defining new instructions as subroutines, by using core instructions or other subroutines as building blocks.

14. Recursion: What happens when a subroutine calls itself?. This is called "recursion".

    Problem: Overwriting the local intermediate results a subroutine can be storing in memory. Since you are calling/reusing the same steps, if the intermediate result are stored in predefined memory locations (global variables) they will be overwritten on the nested calls.

    Solution: To allow recursion, subroutines should store local intermediate results in the stack, therefore, on each recursive call (direct or indirect) the intermediate results are stored in different memory locations.

...

having reached recursion we stop here.

Conclusion:

In a Von Neumann Architecture, clearly "Iteration" is a simpler/basic concept than “Recursion". We have a form of "Iteration" at level 7, while "Recursion" is at level 14 of the concepts hierarchy.

Iteration will always be faster in machine code because it implies less instructions therefore less CPU cycles.

Which one is "better"?

• You should use "iteration" when you are processing simple, sequential data structures, and everywhere a “simple loop” will do.

• You should use "recursion" when you need to process a recursive data structure (I like to call them “Fractal Data Structures”), or when the recursive solution is clearly more “elegant”.

Advice: use the best tool for the job, but understand the inner workings of each tool in order to choose wisely.

Finally, note that you have plenty of opportunities to use recursion. You have Recursive Data Structures everywhere, you’re looking at one now: parts of the DOM supporting what you are reading are a RDS, a JSON expression is a RDS, the hierarchical file system in your computer is a RDS, i.e: you have a root directory, containing files and directories, every directory containing files and directories, every one of those directories containing files and directories...

Mu.

Seriously now, it doesn't matter. Not for examples this size. They both have the same complexity. If your code is not fast enough for you, this is probably one of the last places you'd look at.

Now, if you really want to know which is faster, measure them. On SBCL, you can call each function in a loop and measure the time. Since you have two simple functions, time is enough. If your program was more complicated, a profiler would be more useful. Hint: if you don't need a profiler for your measurements, you probably don't need to worry about performance.

On my machine (SBCL 64 bit), I ran your functions and got this:

CL-USER> (time (loop repeat 1000 do (factorial_recursion 1000)))
Evaluation took:
  0.540 seconds of real time
  0.536034 seconds of total run time (0.496031 user, 0.040003 system)
  [ Run times consist of 0.096 seconds GC time, and 0.441 seconds non-GC time. ]
  99.26% CPU
  1,006,632,438 processor cycles
  511,315,904 bytes consed

NIL
CL-USER> (time (loop repeat 1000 do (factorial_loop 1000)))
Evaluation took:
  0.485 seconds of real time
  0.488030 seconds of total run time (0.488030 user, 0.000000 system)
  [ Run times consist of 0.072 seconds GC time, and 0.417 seconds non-GC time. ]
  100.62% CPU
  902,043,247 processor cycles
  511,322,400 bytes consed

NIL

After putting your functions in a file with (declaim (optimize speed)) at the top, the recursion time dropped to 504 milliseconds and the loop time dropped to 475 milliseconds.

And if you really want to know what's going on, try dissasemble on your functions and see what's in there.

Again, this looks like a non-issue to me. Personally, I try to use Common Lisp like a scripting language for prototyping, then profile and optimize the parts that are slow. Getting from 500ms to 475ms is nothing. For instance, in some personal code, I got a couple of orders of magnitude speedup by simply adding an element type to an array (thus making the array storage 64 times smaller in my case). Sure, in theory it would have been faster to reuse that array (after making it smaller) and not allocate it over and over. But simply adding :element-type bit to it was enough for my situation - more changes would have required more time for very little extra benefit. Maybe I'm sloppy, but 'fast' and 'slow' don't mean much to me. I prefer 'fast enough' and 'too slow'. Both your functions are 'fast enough' in most cases (or both are 'too slow' in some cases) so there's no real difference between them.

I am not really confortable with python, but I have a different approach to the problem for what it's worth. As far as I saw, all solutions posted are O(NM) where N is the length of the array and M the length of the largest elements array. Because of your specific situation whereN >> M you could say it's O(N), but the longest the inputs the more it will be O(NM) I agree with @zvone that it seems you have more steps in the iterative solution, which sounds like an valid explanation to your different computing speeds. Back to my proposal, implements binary search O(N*logM) with recursion:

import math

def binarySearch(arr, target, origin = 0):
    """ 
    Recursive binary search
    Args:
        arr (list): List of numbers to search in
        target (int): Number to search with
    Returns:
        int: index + 1 from inmmediate lower element to target in arr or -1 if already present or lower than the lowest in arr
    """
    half = math.floor((len(arr) - 1) / 2);
    if target > arr[-1]:
        return origin + len(arr)
    if len(arr) == 1 or target < arr[0]:
        return -1
    if arr[half] < target and arr[half+1] > target:
        return origin + half + 1
    if arr[half] == target or arr[half+1] == target:
        return -1
    if arr[half] < target:
        return binarySearch(arr[half:], target, origin + half)
    if arr[half] > target: 
        return binarySearch(arr[:half + 1], target, origin)
    
def findLargestNumbers(array, limit = 3, result = []):
    """ 
    Recursive linear search of the largest values in an array
    Args:
        array (list): Array of numbers to search in
        limit (int): Length of array returned. Default: 3
    Returns:
        list: Array of max values with length as limit
    """    
    if len(result) == 0:
        result = [float('-inf')] * limit
    if len(array) < 1:
        return result
    val = array[-1]
    foundIndex = binarySearch(result, val)
    if foundIndex != -1:
        result.insert(foundIndex, val)
        return findLargestNumbers(array[:-1],limit, result[1:])
    return findLargestNumbers(array[:-1], limit,result)

It is quite flexible and might be inspiration for a more elaborated answer.

If you're measuring the number of function calls (or additions -- it turns out the same), the correct recurrence relations are:

T(0) = 0
T(n) = T(0) + T(1) + T(2) + ... + T(n-1) + n

You can compute the first few values:

 T(0) = 0
 T(1) = 1
 T(2) = 3
 T(3) = 7
 T(4) = 15

You can guess from this that T(n) = 2^n - 1, and that's easy to check by a proof by induction.

In some sense you are right that T(n) = O(n!) since n! > 2^n for n>3, but T(n) = O(2^n) is a tighter bound.