What problems can the use of recursion cause and how to avoid them?

  • one
    The method of struggle - do not stick with the conditions of exit from recursion - Gorets
  • 2
    I agree with the last comment =) - Zowie
  • 2
    @Gorets Why not stick? And where? - alexlz
  • one
    There is an input - to write code so that the end condition of the recursive function always works. (avoid infinity) And if we are talking about a stack overflow, then IMHO code needs to be rewritten so that it does not exist at all, since stack overflow as it indicates that this place would not hurt, to rewrite. - Zowie
  • one
    The best way to avoid the negative effects of recursion is to avoid recursion. Instead, try to use cycles. - skegg

2 answers 2

Overhead to challenges. A little time, and most importantly - the stack. With a large depth of recursion quickly consumed. The counter method is the use of tail recursion, which normal compilers transform into iterations.

Added. On the topic of "replace recursion stack." Recursive factorial function. 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

What is there to replace and what?

    Too deep recursion can always be replaced using a stack.

    • one
      IMHO - it is not possible but necessary - Zowie
    • Maybe so =) - Pavel S. Zaitsau
    • one
      What is meant by stack? - skegg
    • Apparently the data in the stack, the standard technique when working with recursive structures (for example, trees). But saving of memory will be only if the stack frames of the recursive function are significantly more data. Well, another option - stack structures (connected or not) in a heap. - alexlz 2:43 pm