difference in space complexity on using recursive program

Question

I want to know difference(greater or lesser) between space complexity of a recursive and non recursive program with lowest space complexity.I know that recursion uses stack in its operations,but does recursion always increase space complexity.Can recursion be helpful in reducing space complexity?I will also appreciate any guidance for a good tutorial of stack use in recursion.Please also provide an short example for clarification if possible.

See http://stackoverflow.com/q/10821059/395857 – Franck Dernoncourt Sep 02 '13 at 19:35 — Franck Dernoncourt, Sep 02 '13 at 19:35

usamec · Accepted Answer · 2013-09-02T19:12:51.197

3

Recursion can increase space complexity, but never decreases. Consider for example insert into binary search tree. Nonrecursive implementation (using while cycle) uses O(1) memory. Recursive implementation uses O(h) memory (where h is the depth of the tree).

In more formal way: If there is a recursive algorithm with space complexity O(X), then there always is nonrecursive algorithm with space complexity O(X) (you can just simulate recursion by using stack). But it doesn't go the other way (see example above).

edited Sep 02 '13 at 19:12

answered Sep 02 '13 at 18:55

usamec

2,156
3
20
27

The question is: does recursion **always** increase space complexity? – Franck Dernoncourt Sep 02 '13 at 19:03
what about a program for finding max and min in an array.I assume the best space complexity for iterative program is O(n).But we can find same answer in O(log n) using recursive program with divide and conquer approach OR I m wrong in my answer. – WSS Sep 03 '13 at 08:34
1

If you count the input array into space complexity, than both approaches have O(n) space complexity. If you don't count the array, than D&C approach has O(log n) space complexity and iteration approach has O(1) space complexity (you need just 2 variables). – usamec Sep 03 '13 at 10:32
If your data structure is mutable, and you have Tail Call elimination, then you can insert into an ordered binary tree in constant space. (Just the top node in of the current subtree). Only if you have to construct a new tree as a result of the insert (to make purely functional data structures) is it required to keep partially constructed nodes on the stack for later use. – WorBlux Sep 03 '13 at 18:34

score 1 · Answer 2 · answered Sep 02 '13 at 19:48

You can achieve exactly the same space complexity with tail recursion as loop iteration if your implementation language support TCO.

int acc=1;
(for int i=1; i<=n; i++) {
  acc*=i;
}
return acc;

Is the same as:

int fact (int i, int acc) {
  if( i == 1) 
     return acc;
  return fact(i--, i*acc);
}
return fact(n);

difference in space complexity on using recursive program

2 Answers2