<p>Recursion is an abstract concept. Talking about whether or not it has in-place semantics is nonsense. (Unless of course the language specifies recursion semantics.) This idea is related to how it is nonsense to talk about the speed of a language.</p>

<p>How recursion is implemented is another question. For example, a compiler might perform tail call optimization where recursion can be converted to a loop under the hood among other things. In this case, recursion maintains constant stack space (assuming your architechure uses stacks :D)</p>

<p><strong>EDIT:</strong> What does this all mean? It means that there exist recursive algorithms that are in-place when implemented in certain fashions. Thus the statement "All recursive algorithms are inherently not in-place" is false.</p>

CC BY-SA 3.0
2012-01-01T02:36:55.203Z
There's nothing nonsensical about considering space usage for abstract recursive algorithms. Recursion has definite semantics regarding space complexity: if the base case uses O(1) space, each recursive step uses O(1) space beyond that used by the next lower level, and the recursion is k levels deep, then the space complexity is O(k). For Quicksort, k = log(n), so Quicksort uses O(log n) space. This is an inherent property of the algorithm and is entirely independent of language.
Ted Hopp
CC BY-SA 3.0
2012-01-01T02:50:18.550Z
What about Chicken scheme for instance? No function in that implementation ever returns as everything is implemented as continuations that delve further into the "callstack".
Thomas Eding
CC BY-SA 3.0
2012-01-01T05:02:55.023Z
What about it? It tends to use _more_ memory than a straightforward recursive algorithm analysis would suggest. (Thus the need to GC the C call stack when it overflows.) If you're suggesting that it doesn't implement recursion because nothing ever returns, then I don't understand how that relates to my previous comment.
Ted Hopp
CC BY-SA 3.0
2012-01-02T23:08:03.240Z
@TedHopp: I think that what trinithis is saying is that something like whether “each recursive step uses O(1) space beyond that used by the next lower level” or not is determined only after giving the precise semantics of recursion such as whether tail call optimization is performed or not.  I agree with trinithis that this level of semantics is often considered outside of a description of an algorithm, and therefore it is often meaningless to discuss whether the space complexity of a recursive algorithm is O(1) or not.  (more)
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-02T23:08:21.323Z
@TedHopp: (cond’d) For example, “What is the space complexity of the factorial implemented by a recursion?” is not answerable because the description is not precise enough to talk about its space complexity.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-03T22:36:22.570Z
@TsuyoshiIto, the jump from what this answer says and your interpretation of what it means seems like magic to me. I agree with two points made here. One by you: To talk about the space usage of recursive algorithms, you need to have a computational model that clarifies what is the space usage of function calls. One by trinithis: It really is about how function calls work, not necessarily recursive ones; to see this, thing about continuation-passing style programs. But statements like "talking about whether recursion has in-place semantics is nonsense" do not seem to address the question.
Radu GRIGore
CC BY-SA 3.0
2012-01-04T03:04:29.953Z
@Radu: I do not see any jump or magic here.  What I wrote in the comments is the only possible interpretation of trinithis’s answer for me.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-04T05:01:45.913Z
I think Tsuyoshi filled in the blanks I may have hinted at, i.e. how function calls are implemented affect space usage by nature of the word "implementation".
Thomas Eding
CC BY-SA 3.0
2012-01-06T15:35:23.423Z
@TsuyoshiIto: I think it's fair to say that the space complexity of a recursive algorithm is at least linear in the maximum recursion depth, unless all recursive calls are tail calls, in which case the space complexity depends on the precise semantics of the language or the implementation.
Antonio Valerio Miceli-Barone
CC BY-SA 3.0
2012-01-06T15:47:03.280Z
@trinithis: Chicken Scheme performs a global transformation to put the program in Continuation Passing Style. In this form, a recursive but not originally tail-recursive algorithm keeps the same space complexity of the original form: instead of a growing call stack you get a growing continuation object.
Antonio Valerio Miceli-Barone
CC BY-SA 3.0
2012-01-01T01:56:45.293Z
2012-01-04T05:04:13.810Z
2012-01-04T05:04:13.810Z
Thomas Eding
<p>Although not for sorting, note that there are algorithms that may naturally be described using recursion but that do not require storage of a call stack. For instance, quickselect can be described as a modified version of quicksort that makes only one of the two recursive calls of quicksort; however, using <a href="http://en.wikipedia.org/wiki/Tail_call">tail recursion</a> for this call avoids the need for a call stack.</p>

<p>Similarly, reverse search procedures (e.g. for listing the vertices of a convex polytope or for various other combinatorial enumeration procedures) are really just performing a recursive traversal of some implicitly-defined tree, but don't need to store more than a constant number of tree nodes at a time — in this case there is more than one recursive call from each call, but the call stack does not need to be stored because it can instead be calculated from the structure of the tree that is being traversed.</p>

CC BY-SA 3.0
2012-01-03T22:26:28.167Z
The second part reminds me of a cute puzzle I saw recently: Do an in-order traversal of a binary tree using $O(1)$ extra memory.
Radu GRIGore
CC BY-SA 3.0
2014-02-26T00:13:38.423Z
It took me several days, but I wrote a quick-sort variation that uses O(1) stack memory, though my peers at StackOverflow immediately called into question if it is still a quick-sort.
Mooing Duck
CC BY-SA 3.0
2012-01-03T22:17:40.600Z
2012-01-03T22:17:40.600Z
David Eppstein
<p>Who says that Quicksort is an in-place sort? There is a <a href="http://en.wikipedia.org/wiki/Quicksort#In-place_version" rel="nofollow">compact version of Quicksort</a> that uses an in-place partition algorithm, but the overall space usage is, as you say, O(log n).</p>

CC BY-SA 3.0
2012-01-01T01:46:09.390Z
Yeah, I'm talking about the inplace version of Quicksort, but again in this inplace version there is inherent usage of O(log(n)) memory in the form of stack? so how is this inplace now? Am I missing somethig?! I believe inplace means you can't use more than a fixed amount of memory in your algorithm!
Alan Turing
CC BY-SA 3.0
2012-01-01T01:38:33.150Z
2012-01-01T01:38:33.150Z
Ted Hopp
<p>In-place sorting algorithms are called so because only a constant number of elements are out of the input (probably an array) at any given time during the sorting process.
Recursion is only a technique that can be used to solve problems. It is defined as "calling itself directly or indirectly with an input of smaller size than the original problem size". 
They are completely two different ideas.
So, there can be in place sorting algorithms which uses recursion. </p>

CC BY-SA 3.0
2012-01-10T00:18:53.977Z
2012-01-10T00:18:53.977Z
Tharindu Rusira
<p>All sorting algorithms on random-access arrays require O(lg(n)) space. Consider the size of the array indices. It requires <code>ceil(lg(n)/lg(2))</code> bits to represent an array index variable that can hold n distinct values. If your data is in a random-access array, you will need at least one such variable. Therefore, there is a minimum bound of <code>O(lg(n))</code> on your space complexity, regardless of what algorithm you use.</p>

<p>Note that mergesort cannot avoid this either. You can either have mergesort run in-place, in which case all merge phases (of which there are <code>O(lg(n))</code>) run in parallel for <code>O(lg(n))</code> space complexity, or you do a non-in-place sort with <code>O(n)</code> space complexity, or you overwrite your input array, in which case you need that index variable again.</p>

<p>Because this bound is rather fundamental (and typically not a problem), usually one does not bother mentioning it.</p>

CC BY-SA 3.0
2012-01-01T03:12:09.623Z
Index size is a different issue (and often assumed to be O(1) in algorithmics), if you are counting it then quicksort and mergesort require O(log^2 n) memory, while insertionsort is O(log n). And in this setting, it is important to mention that time complexity of many sorting algorithms stops being O(n log n), since array access is then O(log n) not O(1).
sdcvvc
CC BY-SA 3.0
2012-01-01T07:57:19.637Z
@bdonlan What you are saying is certainly a good point, but isn't the issue with the size of index more of an architectural issue rather than algorithmic. I mean, in analyzing algorithms we just don't care about practical limit in variables? But in the question I am asking its bit different, here number of such variables used is dependent on size of input and is independent of architecture...
Alan Turing
CC BY-SA 3.0
2012-01-01T21:56:17.993Z
I'm not referring to the number of variables, just the sheer number of bits needed to store an index of a given size. No matter what architecture you use, you'll need O(lg(n)) storage to store an index that counts up to n.
bdonlan
CC BY-SA 3.0
2012-01-02T16:58:19.747Z
Index size is usually not considered because we're usually talking about a finite machine where the index size is a constant: log(address_space_size). (We usually use an `int` to index into an `int[10]` and the same `int` to index into an `int[500000]`.) Despite the fact that all problems are thus theoretically O(1) (since we have a finite space), we're interested in how much heap (or other auxiliary) storage will be needed as the problem grows. The size of index variables usually doesn't grow with problem size.
Ted Hopp
CC BY-SA 3.0
2012-01-03T14:01:15.470Z
The standard integer RAM model assumes that each memory address  holds a w-bit integer, for some integer w ≥ lg n.  Standard operations on those integers—like comparisons, arithmetic, and indirection—require O(1) time.  The standard definition of an in-place algorithm is one that uses O(1) additional *words* of memory.
Jeffε
CC BY-SA 3.0
2012-01-03T21:33:18.190Z
@TedHopp: If the index size is deemed constant, wouldn't a stack declared as `int stack[log(address_space_size)]` (which would work perfectly as a stack for quicksort) be constant size, too? Your reasoning leads to fundamental inconsistencies (as you already said, all problems are `O(1)` in your model) and all this discussions this is just babbling about one of them.
jpalecek
CC BY-SA 3.0
2012-01-04T21:04:12.730Z
@jpalecek: No, that's a stack of O(w) words, not a stack of O(1) words.  The word size w is NOT considered constant.  Operations on w-bit integers are assumed to take constant time because of low-level parallelism in the hardware.
Jeffε
CC BY-SA 3.0
2012-01-01T01:36:08.853Z
2012-01-01T01:36:08.853Z
bdonlan
<p>Afaik, any programming language with good execution time optimizes tail recursion.</p>

<p>There are even algorithms for which it's easiest to code their "most in-place" variant in pure functional languages like Haskell because said algorithm requires considerable small modifications to a large data structure (see <a href="https://stackoverflow.com/questions/7651058/are-there-versions-of-the-c-stls-associative-data-structures-optimized-for-nu">this question pertaining to an example</a>).  </p>

<p>I'll grant that functional languages aren't nearly as explicit with identfying their in-place data.</p>

CC BY-SA 3.0
2012-01-12T20:49:27.900Z
Hmm, but tail-recursion optimization isn't possible in all the cases! So, my question is actually for any generic recursive algorithm, its just that I gave some example :)
Alan Turing
CC BY-SA 3.0
2012-01-10T01:25:25.523Z
2012-01-10T01:25:25.523Z
2017-05-23T12:40:09.333Z
Jeff Burdges
<p>As recursive algorithms depend on the stack whose size is in almost all the cases depend on input, why don't we consider all the recursive algorithms as NOT-inplace algorithms?</p>

<p>Consider for example, Quicksort, we say it as inplace sort, but in reality, (average case) it uses O(log(n)) memory in stack? So, how can it be called inplace sort?!</p>

CC BY-SA 3.0
2012-01-02T14:33:43.687Z
By "in-place version of Quicksort," some people mean that the partition step uses a (true) in-place algorithm. I think the imprecision is rather benign. (As a side note, other people refuse to say "quicksort" when the partitioning is not in-place.)
Radu GRIGore
CC BY-SA 3.0
2012-01-03T21:58:55.927Z
@AlanTuring: Could you please consider choosing a less questionable user name?
Jukka Suomela
CC BY-SA 3.0
2012-01-03T23:03:25.540Z
I think the intuition about in-place sorting might be not about the auxiliary memory, it is about using only $O(1)$ extra data cells to store the members of the array being sorted. Maybe you should fist define (or ask) what is an in-place sorting algorithm?
Kaveh
CC BY-SA 3.0
2012-01-03T23:05:33.017Z
Might be more fair to call quicksort "relatively in-place". It is in-place compared to, say, mergesort which requires $O(n)$ auxiliarly memory. It is not in-place compared to bubble-sort which requires $O(1)$ auxiliary memory.
David Harris
CC BY-SA 3.0
2012-01-03T23:06:26.323Z
Also, note that there is a variant of quicksort which uses tail-recursion for the large half of the input data, which requires $O(\log n)$ stack pointers in the worst case.
David Harris
CC BY-SA 3.0
2012-01-04T01:37:07.147Z
@Jukka Suomela, Why Alan Turing is questionable?! I admire him like many here!
Alan Turing
CC BY-SA 3.0
2012-01-04T21:01:37.927Z
I think by "questionable", @JukkaSuomela means "presumptuous".
Jeffε
CC BY-SA 3.0
2012-01-05T00:58:59.403Z
the common practice here is to use our real names. also, unless you think anything you will post here will be worthy of being signed by Alan Turing, I would change the name
Sasho Nikolov
CC BY-SA 3.0
2012-01-10T01:10:48.807Z
Are there any modern languages that don't optimize out tail recursion?
Jeff Burdges
CC BY-SA 3.0
2012-01-12T15:15:18.717Z
−1 for using the name of the great researcher.  Jukka did not say Alan Turing (the famous one, not you) is a questionable person, but he said that using Alan Turing’s name is a questionable behavior.
Tsuyoshi Ito
<ds.algorithms><terminology>
All recursive algorithms are inherently NOT-inplace, isn't it?
Alan Turing
# All recursive algorithms are inherently NOT-inplace, isn't it?

(Asked by: username_0 on 2012-01-01)

As recursive algorithms depend on the stack whose size is in almost all the cases depend on input, why don't we consider all the recursive algorithms as NOT-inplace algorithms?

Consider for example, Quicksort, we say it as inplace sort, but in reality, (average case) it uses O(log(n)) memory in stack? So, how can it be called inplace sort?!

**Tags:** ds.algorithms, terminology

> **Comments:**
> **username_1**: By "in-place version of Quicksort," some people mean that the partition step uses a (true) in-place algorithm. I think the imprecision is rather benign. (As a side note, other people refuse to say "quicksort" when the partitioning is not in-place.)  
> **username_2**: @AlanTuring: Could you please consider choosing a less questionable user name?  
> **username_3**: I think the intuition about in-place sorting might be not about the auxiliary memory, it is about using only $O(1)$ extra data cells to store the members of the array being sorted. Maybe you should fist define (or ask) what is an in-place sorting algorithm?  
> **username_4**: Might be more fair to call quicksort "relatively in-place". It is in-place compared to, say, mergesort which requires $O(n)$ auxiliarly memory. It is not in-place compared to bubble-sort which requires $O(1)$ auxiliary memory.  
> **username_4**: Also, note that there is a variant of quicksort which uses tail-recursion for the large half of the input data, which requires $O(\log n)$ stack pointers in the worst case.  
> **username_0**: @username_2, Why username_0 is questionable?! I admire him like many here!  
> **username_5**: I think by "questionable", @JukkaSuomela means "presumptuous".  
> **username_6**: the common practice here is to use our real names. also, unless you think anything you will post here will be worthy of being signed by username_0, I would change the name  
> **username_7**: Are there any modern languages that don't optimize out tail recursion?  
> **username_8**: −1 for using the name of the great researcher.  Jukka did not say username_0 (the famous one, not you) is a questionable person, but he said that using username_0’s name is a questionable behavior.  

---

## 6 answers

### Answer by username_9 on 2012-01-01. Score: 13

Recursion is an abstract concept. Talking about whether or not it has in-place semantics is nonsense. (Unless of course the language specifies recursion semantics.) This idea is related to how it is nonsense to talk about the speed of a language.

How recursion is implemented is another question. For example, a compiler might perform tail call optimization where recursion can be converted to a loop under the hood among other things. In this case, recursion maintains constant stack space (assuming your architechure uses stacks :D)

**EDIT:** What does this all mean? It means that there exist recursive algorithms that are in-place when implemented in certain fashions. Thus the statement "All recursive algorithms are inherently not in-place" is false.

> **Comments:**
> **username_10**: There's nothing nonsensical about considering space usage for abstract recursive algorithms. Recursion has definite semantics regarding space complexity: if the base case uses O(1) space, each recursive step uses O(1) space beyond that used by the next lower level, and the recursion is k levels deep, then the space complexity is O(k). For Quicksort, k = log(n), so Quicksort uses O(log n) space. This is an inherent property of the algorithm and is entirely independent of language.  
> **username_9**: What about Chicken scheme for instance? No function in that implementation ever returns as everything is implemented as continuations that delve further into the "callstack".  
> **username_10**: What about it? It tends to use _more_ memory than a straightforward recursive algorithm analysis would suggest. (Thus the need to GC the C call stack when it overflows.) If you're suggesting that it doesn't implement recursion because nothing ever returns, then I don't understand how that relates to my previous comment.  
> **username_8**: @TedHopp: I think that what trinithis is saying is that something like whether “each recursive step uses O(1) space beyond that used by the next lower level” or not is determined only after giving the precise semantics of recursion such as whether tail call optimization is performed or not.  I agree with trinithis that this level of semantics is often considered outside of a description of an algorithm, and therefore it is often meaningless to discuss whether the space complexity of a recursive algorithm is O(1) or not.  (more)  
> **username_8**: @TedHopp: (cond’d) For example, “What is the space complexity of the factorial implemented by a recursion?” is not answerable because the description is not precise enough to talk about its space complexity.  
> **username_1**: @TsuyoshiIto, the jump from what this answer says and your interpretation of what it means seems like magic to me. I agree with two points made here. One by you: To talk about the space usage of recursive algorithms, you need to have a computational model that clarifies what is the space usage of function calls. One by trinithis: It really is about how function calls work, not necessarily recursive ones; to see this, thing about continuation-passing style programs. But statements like "talking about whether recursion has in-place semantics is nonsense" do not seem to address the question.  
> **username_8**: @Radu: I do not see any jump or magic here.  What I wrote in the comments is the only possible interpretation of trinithis’s answer for me.  
> **username_9**: I think Tsuyoshi filled in the blanks I may have hinted at, i.e. how function calls are implemented affect space usage by nature of the word "implementation".  
> **username_11**: @TsuyoshiIto: I think it's fair to say that the space complexity of a recursive algorithm is at least linear in the maximum recursion depth, unless all recursive calls are tail calls, in which case the space complexity depends on the precise semantics of the language or the implementation.  
> **username_11**: @trinithis: Chicken Scheme performs a global transformation to put the program in Continuation Passing Style. In this form, a recursive but not originally tail-recursive algorithm keeps the same space complexity of the original form: instead of a growing call stack you get a growing continuation object.  

---

### Answer by username_12 on 2012-01-03. Score: 8

Although not for sorting, note that there are algorithms that may naturally be described using recursion but that do not require storage of a call stack. For instance, quickselect can be described as a modified version of quicksort that makes only one of the two recursive calls of quicksort; however, using [tail recursion](http://en.wikipedia.org/wiki/Tail_call) for this call avoids the need for a call stack.

Similarly, reverse search procedures (e.g. for listing the vertices of a convex polytope or for various other combinatorial enumeration procedures) are really just performing a recursive traversal of some implicitly-defined tree, but don't need to store more than a constant number of tree nodes at a time — in this case there is more than one recursive call from each call, but the call stack does not need to be stored because it can instead be calculated from the structure of the tree that is being traversed.

> **Comments:**
> **username_1**: The second part reminds me of a cute puzzle I saw recently: Do an in-order traversal of a binary tree using $O(1)$ extra memory.  
> **username_13**: It took me several days, but I wrote a quick-sort variation that uses O(1) stack memory, though my peers at StackOverflow immediately called into question if it is still a quick-sort.  

---

### Answer by username_10 on 2012-01-01. Score: 2

Who says that Quicksort is an in-place sort? There is a [compact version of Quicksort](http://en.wikipedia.org/wiki/Quicksort#In-place_version) that uses an in-place partition algorithm, but the overall space usage is, as you say, O(log n).

> **Comments:**
> **username_0**: Yeah, I'm talking about the inplace version of Quicksort, but again in this inplace version there is inherent usage of O(log(n)) memory in the form of stack? so how is this inplace now? Am I missing somethig?! I believe inplace means you can't use more than a fixed amount of memory in your algorithm!  

---

### Answer by username_14 on 2012-01-10. Score: 0

In-place sorting algorithms are called so because only a constant number of elements are out of the input (probably an array) at any given time during the sorting process.
Recursion is only a technique that can be used to solve problems. It is defined as "calling itself directly or indirectly with an input of smaller size than the original problem size".
They are completely two different ideas.
So, there can be in place sorting algorithms which uses recursion.


---

### Answer by username_15 on 2012-01-01. Score: 0

All sorting algorithms on random-access arrays require O(lg(n)) space. Consider the size of the array indices. It requires `ceil(lg(n)/lg(2))` bits to represent an array index variable that can hold n distinct values. If your data is in a random-access array, you will need at least one such variable. Therefore, there is a minimum bound of `O(lg(n))` on your space complexity, regardless of what algorithm you use.

Note that mergesort cannot avoid this either. You can either have mergesort run in-place, in which case all merge phases (of which there are `O(lg(n))`) run in parallel for `O(lg(n))` space complexity, or you do a non-in-place sort with `O(n)` space complexity, or you overwrite your input array, in which case you need that index variable again.

Because this bound is rather fundamental (and typically not a problem), usually one does not bother mentioning it.

> **Comments:**
> **username_16**: Index size is a different issue (and often assumed to be O(1) in algorithmics), if you are counting it then quicksort and mergesort require O(log^2 n) memory, while insertionsort is O(log n). And in this setting, it is important to mention that time complexity of many sorting algorithms stops being O(n log n), since array access is then O(log n) not O(1).  
> **username_0**: @username_15 What you are saying is certainly a good point, but isn't the issue with the size of index more of an architectural issue rather than algorithmic. I mean, in analyzing algorithms we just don't care about practical limit in variables? But in the question I am asking its bit different, here number of such variables used is dependent on size of input and is independent of architecture...  
> **username_15**: I'm not referring to the number of variables, just the sheer number of bits needed to store an index of a given size. No matter what architecture you use, you'll need O(lg(n)) storage to store an index that counts up to n.  
> **username_10**: Index size is usually not considered because we're usually talking about a finite machine where the index size is a constant: log(address_space_size). (We usually use an `int` to index into an `int[10]` and the same `int` to index into an `int[500000]`.) Despite the fact that all problems are thus theoretically O(1) (since we have a finite space), we're interested in how much heap (or other auxiliary) storage will be needed as the problem grows. The size of index variables usually doesn't grow with problem size.  
> **username_5**: The standard integer RAM model assumes that each memory address  holds a w-bit integer, for some integer w ≥ lg n.  Standard operations on those integers—like comparisons, arithmetic, and indirection—require O(1) time.  The standard definition of an in-place algorithm is one that uses O(1) additional *words* of memory.  
> **username_17**: @TedHopp: If the index size is deemed constant, wouldn't a stack declared as `int stack[log(address_space_size)]` (which would work perfectly as a stack for quicksort) be constant size, too? Your reasoning leads to fundamental inconsistencies (as you already said, all problems are `O(1)` in your model) and all this discussions this is just babbling about one of them.  
> **username_5**: @username_17: No, that's a stack of O(w) words, not a stack of O(1) words.  The word size w is NOT considered constant.  Operations on w-bit integers are assumed to take constant time because of low-level parallelism in the hardware.  

---

### Answer by username_7 on 2012-01-10. Score: 0

Afaik, any programming language with good execution time optimizes tail recursion.

There are even algorithms for which it's easiest to code their "most in-place" variant in pure functional languages like Haskell because said algorithm requires considerable small modifications to a large data structure (see [this question pertaining to an example](https://stackoverflow.com/questions/7651058/are-there-versions-of-the-c-stls-associative-data-structures-optimized-for-nu)).

I'll grant that functional languages aren't nearly as explicit with identfying their in-place data.

> **Comments:**
> **username_0**: Hmm, but tail-recursion optimization isn't possible in all the cases! So, my question is actually for any generic recursive algorithm, its just that I gave some example :)  

---

