Это работает, но на больших списках(999999 элементов) предсказуемо ломается. Каждый раз при вызове функции нужно сохранить как минимум адрес возврата, а стек не резиновый, следовательно рано или поздно он переполнится.
Вывод gcc-O-S llist.c(оптимизацию в данном случае включил просто чтобы было поменьше кода).
list_sum:
.LFB43:
.cfi_startproc
movl $0, %eax
testq %rdi, %rdi
je .L29
pushq %rbx
.cfi_def_cfa_offset 16
.cfi_offset 3, -16
movq %rdi, %rbx
movq 8(%rdi), %rdi
call list_sum
addl (%rbx), %eax
popq %rbx
.cfi_restore 3
.cfi_def_cfa_offset 8
.L29:
rep ret
.cfi_endproc
.LFE43:
.size list_sum, .-list_sum
С этим все ясно.
Концевая рекурсия
Хвостовая рекурсия — частный случай рекурсии, при котором любой рекурсивный вызов является последней операцией перед возвратом из функции. Подобный вид рекурсии примечателен тем, что может быть легко заменен на итерацию путем формальной и гарантированно корректной перестройки кода функции.
Как я понял, обосновать возможность оптимизации можно тем, что в данном случае мы можем просто перейти к вложенной функции используя ее адрес возврата вместо исходного.
Задания
Рекурсивная реализация list_sum
int list_sum(const struct llist_t* node) { if(node == NULL) return 0; return node->value + list_sum(node->next);}list_sum:.LFB43: .cfi_startproc movl $0, %eax testq %rdi, %rdi je .L29 pushq %rbx .cfi_def_cfa_offset 16 .cfi_offset 3, -16 movq %rdi, %rbx movq 8(%rdi), %rdi call list_sum addl (%rbx), %eax popq %rbx .cfi_restore 3 .cfi_def_cfa_offset 8.L29: rep ret .cfi_endproc.LFE43: .size list_sum, .-list_sumКонцевая рекурсия