Проверял GCC на предмет того, как он умеет рекурсию оптимизировать.
Вот такая штука

unsigned int plus(unsigned int a, unsigned int b)
{
  if (b == 0) return a;
  return plus (a+1, b-1);
}

Относительно успешно сворачивается сложение. Получается такая шняга:

movl %edi, %eax
addl %esi, %eax
ret

Хотя в идеале можно было бы обойтись

leal (%rsi,%rdi), %eax
ret

Что касается умножения, там ситуация более печальная

inline unsigned long int product_0(const unsigned int a, const unsigned int b, const unsigned long int tmp)
{
  if (b == 0) return tmp;
  return product_0(a, b-1, tmp+a);
}

unsigned long int product(const unsigned int a, const unsigned int b)
{
  return product_0(a, b, 0);
}

В ассемблере получается такая фигня

product:
.LFB34:
.cfi_startproc
    xorl %eax, %eax
    testl %esi, %esi
    je .L7
    leal -1(%rsi), %eax
    mov %edi, %edi
    addq $1, %rax
    imulq %rdi, %rax
.L7:
    rep
    ret
.cfi_endproc

Тут оно зачем-то зануляет значение регистра, в котором хранится возврашемое из функции значение и сравнивает с нулем значение регистра, в котором в функцию передается число. Если ноль то прыгаем в конец функции, возвращая 0. Тогда внезапно появляется смысл в этом rep ret http://repzret.org/p/repzret/

Why? Because “The processor is unable to apply a branch prediction to the single-byte near-return form (opcode C3h) of the ret instruction.” Thus, “Use of a two-byte near-return can improve performance”, because it is not affected by this shortcoming.

Ну а дальше через leal из регистра rsi число копируется в eax, уменьшаясь при этом на 1 (нахрена?) и потом из регистра edi двигается в edi (НАХРЕНА??), увеличиваем rax на 1 через addq (ну тут понятно зачем, перед этим ведь оно было непонятно зачем уменьшено на 1, но нахрена уменьшать и потом увеличивать? И вообще, для увеличения на 1 лучше incq использовать) ну и в итоге компилятор таки вставляет инструкцию imulq. Распознать умножение в этой рекурсивной хрени компилятор смог, но при этом как-то через жопу все, нагенерировал кучу говна всякого. Можно было намного проще сделать

movl %esi, %eax
imull %edi, %eax

gcc version 4.5.1 если что