Рекурсия и ее проблемы

#рекурсия #алгоритм

                    
К каким проблемам может привести использование рекурсии и как их избежать?    

Ответы

Ответ 1

Оверхед на вызовы. Немного время, а главное -- стек. При большой глубине рекурсии
быстро расходуется. Метод борьбы -- использование хвостовой рекурсии, которую нормальные
компиляторы трансформируют в итерации.
Добавлено. На тему "заменить рекурсию стеком".
Рекурсивная функция вычисления факториала.
fact.c++
int fact0(int k, int n) {
    if (n > 1) return fact0(k*n, n-1); 
    else return k;
}

fact0.s
    .file   "fact0.c++"
    .text
    .p2align 4,,15
.globl _Z5fact0ii
    .type   _Z5fact0ii, @function
_Z5fact0ii:
.LFB0:
    .cfi_startproc
    .cfi_personality 0x0,__gxx_personality_v0
    pushl   %ebp
    .cfi_def_cfa_offset 8
    movl    %esp, %ebp
    .cfi_offset 5, -8
    .cfi_def_cfa_register 5
    movl    12(%ebp), %edx
    movl    8(%ebp), %eax
    cmpl    $1, %edx
    jg  .L5
    jmp .L2
    .p2align 4,,7
    .p2align 3
.L7:
    movl    %ecx, %edx
.L5:
    leal    -1(%edx), %ecx
    imull   %edx, %eax
    cmpl    $1, %ecx
    jne .L7
.L2:
    popl    %ebp
    .p2align 4,,2
    ret
    .cfi_endproc
.LFE0:
    .size   _Z5fact0ii, .-_Z5fact0ii
    .ident  "GCC: (Ubuntu 4.4.3-4ubuntu5) 4.4.3"
    .section    .note.GNU-stack,"",@progbits

Что тут заменять и на что?


Ответ 2

Слишком глубокую рекурсию всегда можно заменить используя стэк.