Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

C/++/# Indefinite recursion

  1. Jul 7, 2016 #1
    Upto how many levels of recursion can be used in an algorithm to avoid stack overflow error ?
     
  2. jcsd
  3. Jul 7, 2016 #2
    There is no guarantees as it depends upon:
    1. How much stack space is there to begin with?
    2. How much space does each call take?

    While you can measure these for a particular use case, in general you can't rely on this.

    For any of the products I work on, I try to avoid using recursion and use an iterative algorithm. When I do use recursion, it is either for an internal tool that customers won't have to use or has some means of guaranteeing it won't require a deep stack.
     
  4. Jul 7, 2016 #3

    QuantumQuest

    User Avatar
    Gold Member

    This question could not be more abstract. What kind of recursion, which programming environment / language and last but not least which operating system?
     
  5. Jul 7, 2016 #4
    It depends.
    For example, tail recursion is as good as any iteration.
     
  6. Jul 7, 2016 #5

    Mark44

    Staff: Mentor

    I don't think so. In recursion of any kind, the return address and any parameters have to be pushed onto the stack, something that is not done when a loop executes. Eventually the program will run out of available stack storage.
     
  7. Jul 7, 2016 #6
    It depends.
    A compiler (interpreter) may treat tail-recursive calls as jumps not function calls. Then, the space is constant.
     
  8. Jul 7, 2016 #7

    Mark44

    Staff: Mentor

    If the recursive function takes parameters, I don't see how a compiler could rewrite a function call as a jump. The compiler would still have to push the parameters onto the stack.
     
  9. Jul 7, 2016 #8

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Exactly. Many compilers are very good at recognizing tail recursion. It's called "Tail call optimization". Some interpreters are also good at recognizing tail recursion (e.g., many dialects of Lisp), many others are not (python (Guido hates TCO), perl, ruby, ...).
     
  10. Jul 7, 2016 #9

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Tail recursion is a very special kind of recursion. The following C function to compute [itex]n![/itex] is recursive but it is not tail recursive:
    Code (C):
    unsigned factorial (unsigned n) {
        if (n <= 1) {
            return 1;
        } else {
            return n * factorial(n-1);
        }
    It appears to be tail recursive because the last function that is called is the function itself. However, the last operation is to multiply the value returned value by that call with n. One needs to write a helper function to make this tail recursive in C:
    Code (C):
    unsigned factorial_helper (unsigned n, unsigned prod) {
        if (n <= 1) {
            return prod;
        } else {
            return factorial_helper(n-1, n*prod);
        }
    }

    unsigned factorial (unsigned n) {
        return factorial_helper(n, 1);
    }
    Functional languages invite one to write tail recursive functions in lieu of loops. Non-functional languages such as C (and everything derived from C) invite one to write loops in lieu of tail recursive functions.
     
  11. Jul 7, 2016 #10
    Consider GCD - it can be implemented as tail recursion.
    Factorial - cannot.

    There is an article "Tail call" in Wiki on this subject.
     
  12. Jul 7, 2016 #11

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    I just showed one for factorial. It can be implemented as tail recursion.

    Ackermann's function cannot.
     
  13. Jul 7, 2016 #12

    Mark44

    Staff: Mentor

    Good point. My mindset is from learning C 30+ years ago, before there were such sophisticated optimization schemes.
     
  14. Jul 8, 2016 #13
    Perhaps, there is a toggle for each recursion.
    Mathematicians have not proved the opposite so far.
    So, there is hope. And a scope for work.
     
  15. Jul 8, 2016 #14
    Usually if you even come close to a stack overflow, you are using the wrong algorithm. What kind of algorithm are you doing?

    Also, why is everyone talking about compiler optimization? The code has to work while he's debugging it too, without the compiler optimizations.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Indefinite recursion
  1. Recursion in C (Replies: 12)

  2. Recursion function (Replies: 5)

  3. About Recursion (Replies: 8)

Loading...