Do recursive functions have a minimum space complexity of O(N)?

Question

I was thinking about recursive functions. Take a simple function, for example one to print a linked list recursively:

void print(list *list){
  if(list){
     cout << list->data
     print(list->next);
  }
}

At first this seems like a pretty innocuous function, but isn't it storing an address (labeled by the variable list) in every stack frame? Assume there is no tail-call optimization. We need space for N addresses, where N is the size of the list. The space needed grows linearly in proportion to the size of the list.

I can't think of how you would implement a recursive function without having at least one local variable or argument stored on the stack. So, it seems as though every recursive function is going to have at best linear space complexity. If this is the case, then wouldn't it almost always be advisable to use iteration over recursion?

A compiler [could trivially optimize this](http://stackoverflow.com/a/34129/721269) to not keep anything on the stack. — David Schwartz, Nov 17 '13 at 08:11
@DavidSchwartz: Of course, but the OP states in the middle paragraph, "*Assume there is no tail-call optimization*". — Gabe, Nov 17 '13 at 15:03

score 10 · Answer 1 · answered Nov 17 '13 at 07:48

10

While all non-optimized function calls can be assumed to consume a stack frame, it's not always the case that a recursive algorithm that operates on N elements will require a stack O(N) in size.

A recursive tree-traversal algorithm uses O(lg N) stack frames, for example, as does a recursive QuickSort.

answered Nov 17 '13 at 07:48

Gabe

84,912
12
139
238

2

This is a very good point. I should have said a non-constant amount of space, but the spirit of the question is still the same. – ordinary Nov 17 '13 at 07:53

score 3 · Accepted Answer · answered Nov 17 '13 at 07:41

3

You're right, the space complexity of the piece of code is linear in the size of the list, assuming no tail call optimization.

In general, recursion will make things a little slower and more memory hungry, yes. But you can't always asymptotically improve on this by implementing it iteratively, since for non-tail recursive functions, you will need to manually maintain the stack anyway in an iterative implementation, so you will still use the same amount of memory.

Think of a depth first traversal. You will need to store each node on the stack, together with which child you need to visit next, so that after you return from visiting one of its children, you know which node to go to next. Recursion makes this very easy, since it abstracts all the ugly bookkeeping. An iterative implementation will not be asymptotically better, and I'd expect the practical differences to be very, very little as well.

A lot of times, recursion makes things easier without sacrificing anything. In your case, there is no point for it - it's just a pedagogical example of recursion.

answered Nov 17 '13 at 07:41

IVlad

43,099
13
111
179

Lol! I keep typing questions into the comment box and before I can submit them you make an edit which answers the exact question. Hilarious. But I still have one more. You mention there is a speed sacrifice that is made with recursion. Why is that? – ordinary Nov 17 '13 at 07:45
@ordinary - sorry about that, I usually need about 5 minutes to get everything out there :P. There is a speed sacrifice because calling a function takes time - it's not exactly an instant operation. The parameters you have, the return address, everything needs to be added to the implicit stack recursion creates. This does not affect the big-oh (well, it will if you're using recursion where you really shouldn't, like in your example), but in practice, there will be a (probably tiny) difference. – IVlad Nov 17 '13 at 07:49
So recursion is essentially syntactic sugar? How does it affect the big-o in my example (or in any example)? isn't the big-o still linear in this case? – ordinary Nov 17 '13 at 07:52
@ordinary - It usually doesn't affect the (asymptotic) running time. It can affect the space used, like in your example. An iterative implementation of what you posted will have `O(1)` space complexity, while your implementation has `O(length of list)`. If you use recursion right and / or your compiler optimizes tail recursion, this doesn't happen either. – IVlad Nov 17 '13 at 08:02

score 2 · Answer 3 · answered Nov 17 '13 at 07:48

2

Answer is no, e.g. traversal of (complete) binary tree has space complexity of O(log N), i.e. the depth of the tree.

answered Nov 17 '13 at 07:48

Aki Suihkonen

19,144
1
36
57

score 1 · Answer 4 · answered Nov 17 '13 at 07:45

You're correct. You don't even need variables, the return address itself already occupies space. There are methods to avoid deep nesting in recursion (tail recursion) and modern compilers do it automatically in many cases. But besides that, the iteration will be preferable over recursion from space complexity aspect.

Do recursive functions have a minimum space complexity of O(N)?

4 Answers4