Is recursion solution O(1)?


  • 0
    L

    I was able to get a working solution using recursion, with one pointer going from the front and one from the back while I recurse thru the list. But I don't think it's O(1), each recursive call allocated a stack variable at least. Am I not understanding something?


  • 0
    B

    As far as I know, a technique called "tail recursion optimization" was designed to deal with such problems.Tail recursion makes it possible to use only O(1) space in a recursive function. See more at https://en.wikipedia.org/wiki/Recursion_(computer_science)

    Tail recursion optimization was widely supported by a lot of programming languages(compilers), including C and C++, I don't know how java handle their recursion, but Python interpreter doesn't support automatic tail recursion optimization.

    So if you use C/C++, the compiler will do tail recursion optimization for you and your solution is an O(1) space solution, but if you use Python, the answer is no.

    If you are still worried about the compiler, you can write a tail recursion version by youself, it seems not very difficult.

    And, in consideration of that actually i am not very good at computer science, maybe there are some problems in this anwser, any comments from professionals will be welcom sincerely.


  • 0
    L

    That is informational. From an excerpt on wikipedia,
    When a function is called, the computer must "remember" the place it was called from, the return address, so that it can return to that location with the result once the call is complete. Typically, this information is saved on the call stack, a simple list of return locations in order of the times that the call locations they describe were reached. For tail calls, there is no need to remember the place we are calling from – instead, we can perform tail call elimination by leaving the stack alone (except possibly for function arguments and local variables[1]), and the newly called function will return its result directly to the original caller. Note that the tail call doesn't have to appear lexically after all other statements in the source code; it is only important that the calling function return immediately after the tail call, returning the tail call's result if any, since the calling function will never get a chance to do anything after the call if the optimization is performed.

    So it seems like you cannot be O(1) in space because there are still the parameter that need to pass on each recursion call (you cannot optimize away the parameter I believe). In fact, it will be O(n). What do you guys think?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.