What are recursive algorithms? What are their types? How to avoid stack overflow during recursive call?

Closed due to the fact that off-topic participants Xander , AnT , Darth , Kromster , pavel Jul 17 '17 at 9:03 .

  • Most likely, this question does not correspond to the subject of Stack Overflow in Russian, according to the rules described in the certificate .
If the question can be reformulated according to the rules set out in the certificate , edit it .

  • The question is not clear. For example, "What is a braid?". What kind of "recursion"? Recursive algorithms? Language syntactic recursion? These are completely different things. And what kind of overflow is meant? - AnT
  • @AnT in such cases it is necessary to inform the author about the clarification, etc., and not immediately close the question. IMHO - Lex Hobbit
  • @Lex Hobbit: I do not have the privilege to "immediately close the question." Closing the issue here is done through voting, and it is with the message to the author. - AnT
  • Um .. Are these two questions somehow related? - Qwertiy ♦
  • @AnT I did not mean you specifically. I don't understand in this case why people are minus the question. - Lex Hobbit

2 answers 2

In brief, recursion is a call from the function itself.

For example, what is factorial? n! = n* (n-1) *(n-2) * ... * 1 = n * (n-1)!

So you can write a recursive function of calculating factorial (I will outline C):

 int factorial(int n) { if (n == 1) return 1; // Окончание рекурсии return n * factorial(n-1); // Рекурсивный вызов самой себя }

Well, since each function call requires memory in the stack — for arguments, local variables, and so on — so many such calls can take up the whole stack - overflow it. This is an overflow in the context of recursion.

But there may be an overflow in the context of data types - for example, for an integer 4 bytes are allocated, but we are trying to save a number that does not fit there ...

  • 2
    I’ll clarify that the function does not have to call itself directly. for example, funA calls funB, which calls funA is also a recursion. - Ilya Chizhanov
  • @ Ilya Chizhanov Thanks for the addition. - Harry
  • @Harry, please add more ways to avoid overflow. For example, dynamic programming and so on. - Lex Hobbit
  • @LexHobbit Let's do it in your answer. I just somehow do not really imagine that dynamic programming is a way to avoid overflow during recursion ... - Harry

In addition to the answer @Harry.

Types of recursion

Recursive functions can be divided into several types:

  • linear recursion , in which recursive calls on any recursive slice, initiate no more than one subsequent recursive call. (as in the example of @Harry)
  • tail recursion (a special case of linear recursion), in which a recursive function call occurs at the end of its work. (as in the example of @Harry).
  • nonlinear or parallel recursion , in which recursive calls on any recursive slice, initiate more than one subsequent recursive call.

A good example of this type is the calculation of the n-го member of the Fibonacci series:

 int fib(int n) { if (n == 0) { return 0; } // Окончание рекурсии else { if ((n == -1) || (n == 1)) { return 1; } // Окончание рекурсии else { if (n > 0) { return fib(n - 1) + fib(n - 2); }// параллельный рекурсивный вызов самой себя else { return fib(n + 2) - fib(n + 1); } // параллельный рекурсивный вызов самой себя } } }
  • mutual or indirect recursion , in which a recursive call to this function comes from some other function that was itself called from this function.

Example of calculation (artificial):

 int factorial_odd(int x) { if(x == 0) { return 1; } return factorial_even(x – 1); } int factorial_even(int x) { if(x == 0) { return 1; } return factorial_odd(x – 1); } int factorial (int x) { if(x % 2 == 0) { return factorial_even(x); } else { return factorial_odd(x); } }

When should recursion be used?

Use recursion if:

  1. the task is divided into smaller copies of itself, and there is no obvious way to solve it by writing a cycle;
  2. you work with a recursive data structure, such as linked lists

BUT: If the problem can be solved iteratively, then use iteration.

How to avoid overflow during recursion?

  1. The exit from recursion condition must be present.
  2. If rule 1 is satisfied, but overflow occurs anyway, then it is worth refusing to use recursion and implement the algorithm iteratively. (cycles and dynamic programming to help you)

An example of an iterative factorial calculation:

 int factorial(int n) { int sum = 1; if (n <= 1) return sum; while (n > 1) { sum *= n; n--; } return sum; }

Finally, a better understanding of the theory is achieved through its application in practice .