Why is this recursion much faster than equivalent iteration?

Question

They told me many times that recursion is slow due to function calls, but in this code it seems much faster than an iterative solution. At best, I usually expect the compiler to optimize recursion on iteration (which looks at the assembly seems to have happened).

#include <iostream>

bool isDivisable(int x, int y)
{
    for (int i = y; i != 1; --i)
        if (x % i != 0)
            return false;
    return true;
}
bool isDivisableRec(int x, int y)
{
    if (y == 1)
        return true;
    return x % y == 0 && isDivisableRec(x, y-1);
}

int findSmallest()
{
    int x = 20;
    for (; !isDivisable(x,20); ++x);
    return x;
}

int main()
{
    std::cout << findSmallest() << std::endl;
}

Build here: https://gist.github.com/PatrickAupperle/2b56e16e9e5a6a9b251e

I would like to know what is happening here. I'm sure this is some kind of complicated compiler optimization that I might be surprised to find out about.

Editing: I just realized that I forgot to mention that if I use the recursive version, it will work in about 0.25 seconds, iterative, about 0.6.

Edit 2: I compile with -O3 using

$ g++ --version
g++ (Ubuntu 4.8.4-2ubuntu1~14.04) 4.8.4

, , .

3:
:
: http://gist.github.com/PatrickAupperle/ee8241ac51417437d012
: http://gist.github.com/PatrickAupperle/5870136a5552b83fd0f1
100

4:
, -fno-inline-functions -fno-inline-small-functions . . 15 , . https://gist.github.com/PatrickAupperle/3a87eb53a9f11c1f0bec

Answer 1

, ( ) GCC 4.9.3 Cygwin.

13.411 seconds for iterative
4.29101 seconds for recursive

, -O3,

• isDivisableRec : .

  _Z14isDivisableRecii:
  .LFB1467:
      .seh_endprologue
      movl    %edx, %r8d
  .L15:
      cmpl    $1, %r8d
      je  .L18
      movl    %ecx, %eax          ; First unrolled divisibility check
      cltd
      idivl   %r8d
      testl   %edx, %edx
      je  .L20
  .L19:
      xorl    %eax, %eax
      ret
      .p2align 4,,10
  .L20:
      leal    -1(%r8), %r9d
      cmpl    $1, %r9d
      jne .L21
      .p2align 4,,10
  .L18:
      movl    $1, %eax
      ret
      .p2align 4,,10
  .L21:
      movl    %ecx, %eax          ; Second unrolled divisibility check
      cltd
      idivl   %r9d
      testl   %edx, %edx
      jne .L19
      subl    $2, %r8d
      jmp .L15
      .seh_endproc
  

• isDivisableRec, findSmallestRec. y isDivisableRec 20, 20, 19... 15 "" , findSmallestRec. isDivisableRec y 14 ( ).

  findSmallestRec

      movl    $20, %ebx
      movl    $1717986919, %esi      ; Magic constants
      movl    $1808407283, %edi      ; for divisibility tests
      movl    $954437177, %ebp       ;
      movl    $2021161081, %r12d     ;
      movl    $-2004318071, %r13d    ;
      jmp .L28
      .p2align 4,,10
  .L29:                              ; The main cycle
      addl    $1, %ebx
  .L28:
      movl    %ebx, %eax             ; Divisibility by 20 test
      movl    %ebx, %ecx
      imull   %esi
      sarl    $31, %ecx
      sarl    $3, %edx
      subl    %ecx, %edx
      leal    (%rdx,%rdx,4), %eax
      sall    $2, %eax
      cmpl    %eax, %ebx
      jne .L29
      movl    %ebx, %eax             ; Divisibility by 19 test
      imull   %edi
      sarl    $3, %edx
      subl    %ecx, %edx
      leal    (%rdx,%rdx,8), %eax
      leal    (%rdx,%rax,2), %eax
      cmpl    %eax, %ebx
      jne .L29
      movl    %ebx, %eax             ; Divisibility by 18 test
      imull   %ebp
      sarl    $2, %edx
      subl    %ecx, %edx
      leal    (%rdx,%rdx,8), %eax
      addl    %eax, %eax
      cmpl    %eax, %ebx
      jne .L29
      movl    %ebx, %eax             ; Divisibility by 17 test
      imull   %r12d
      sarl    $3, %edx
      subl    %ecx, %edx
      movl    %edx, %eax
      sall    $4, %eax
      addl    %eax, %edx
      cmpl    %edx, %ebx
      jne .L29
      testb   $15, %bl               ; Divisibility by 16 test
      jne .L29
      movl    %ebx, %eax             ; Divisibility by 15 test
      imull   %r13d
      leal    (%rdx,%rbx), %eax
      sarl    $3, %eax
      subl    %ecx, %eax
      movl    %eax, %edx
      sall    $4, %edx
      subl    %eax, %edx
      cmpl    %edx, %ebx
      jne .L29
      movl    $14, %edx
      movl    %ebx, %ecx
      call    _Z14isDivisableRecii   ; call isDivisableRecii(x, 14)
      ...
  

jne .L29 20, 19... 15, findSmallestRec. -, , , isDivisableRec y. , 16 testb $15, %bl. - x y .

isDivisable findSmallest - . .

, . y, .

isDivisableRec "" 20 ( 20), .

12.9 seconds for iterative
13.26 seconds for recursive