CODEWITHSUNDEEP
algorithm
user1755278
user1755278

Reputation:

Running time for recursive and iterative

I know there are some algorithms which take same running time for both recursive and iterative strategy. But I can't decide on that base.

Is that possible an algorithm with both recursive and iterative strategy will always take same running time?

Upvotes: 1

Views: 114

Answers (3)

SomeWittyUsername
SomeWittyUsername

Reputation: 18338

It can be of the same time complexity but the constant overhead will probably differ (recursive will probably be more expensive). In addition, recursion adds an extra space complexity that's not present if iterative approach is used.

Upvotes: 0

Vesper
Vesper

Reputation: 18747

Yes, if an algorithm can be optimized to use tail recursion, then it can be converted to iterative without extra code, thus will have the same execution time.

Upvotes: 2

Azeem Bande-Ali
Azeem Bande-Ali

Reputation: 305

Every recursive algorithm can be reduced to an iterative algorithm (with the same running time). http://en.wikipedia.org/wiki/Recursion_(computer_science)#Recursion_versus_iteration

Upvotes: 3

Related Questions