In general, in a recursive and non-recursive implementation of a problem…
2015
In general, in a recursive and non-recursive implementation of a problem (program):
- A.
Both time and space complexities are better in recursive than in non-recursive program.
- B.
Both time and space complexities are better in non-recursive than in recursive program.
- C.
Time complexity is better in recursive version but space complexity is better in non-recursive version of a program.
- D.
Space complexity is better in recursive version but time complexity is better in non-recursive version of a program.
Attempted by 844 students.
Show answer & explanation
Correct answer: B
Answer summary:
The most accurate general statement is that time complexity is usually the same for recursive and non-recursive implementations of the same algorithm, while recursive implementations typically use more space because of the call stack. Therefore, non-recursive versions commonly have better space complexity.
Time complexity: Equivalent algorithms implemented recursively or iteratively generally have the same asymptotic time complexity. Recursion can add constant-factor overhead from function calls but does not usually change the order of growth.
Space complexity: Recursive implementations use extra call-stack space proportional to the recursion depth, so they often require more auxiliary space than iterative versions (which can sometimes run in constant extra space).
Exceptions and notes: Tail-call optimization can eliminate the extra stack for some recursive functions, making their space usage similar to iterative versions. Also, choosing recursion can change the algorithmic approach (e.g., divide-and-conquer), which may affect time or space beyond just the recursion/iteration difference.
Conclusion: None of the provided option statements is fully correct. A concise correct claim is: time complexity is generally similar between recursive and non-recursive implementations, while non-recursive implementations generally have better space complexity because recursion adds call-stack usage.