CODEWITHSUNDEEP
recursioniterationbinary-tree
Timeless
Timeless

Reputation: 7537

iterative or recursive to implement a binary search tree?

I'm learning Data Structures & Algorithms now.

My lecture notes have an implementation of a binary search tree which is implemented using a recursive method. That is an elegant way, but my question is in real life code, should I implement a binary search tree recursively, will it generate a lot of calling stack if the tree has large height/depth number.

I understand that recursion is a key concept to understand lots of data structure concepts, but would you choose to use recursion in real life code?

Upvotes: 6

Views: 5004

Answers (4)

mightyWOZ
mightyWOZ

Reputation: 8315

its true that recursion is intutive and elegent and it produces code that is clear and concise. its also correct that some methods such as quick sort, DFS etc. are really hard to implement iterativelly. but in practice recursive implementations are almost always going to be slow when compared to iterative counterparts because of all the function calls (To really understand the performance hit I suggest you learn how much book keeping stuff assembler has to do for a single function call).

the optimizations that we talk about are not applicable to every recursive method in general and manny compilers and interpreters dont even support them.

so in summary if you are writing something which is performance critical such as a data strucute then stay away from recursion (or use it if you are sure that your compiler/interpreter got you covered)

PS: CLRS (introduction to algorithms, page 290, last line) suggests that iterative search procedure for a BST is faster compared to recursive one.

Upvotes: 1

Chris Dargis
Chris Dargis

Reputation: 6043

"I understand that recursive is a key concept to understand lots of data structure, but will you choose to use recursive in real life code?"

After first learning about recursion I felt the same way. However, having been working in the Software industry for over a year now, I can say that I have used the concept of recursion to solve several problems. There are often times that recursion is cleaner, easier to understand/read, and just downright better. And to emphasize a point in the previous answer, a tree is a recursive data structure. IMO, there is no other way to traverse a BST :)

Upvotes: 4

Sam I am says Reinstate Monica
Sam I am says Reinstate Monica

Reputation: 31194

A tree is recursive by nature. Each node of a tree represents a subtree, and each child of each note represents a subtree of that subtree, so recursion is the best bet, especially in practice where other people people might have to edit and maintain your code.

Now, IF depth becomes a problem for your call stack, than I'm afraid that there are deeper problems with your data structure (either it's monstrously huge, or it's very unbalanced)

Upvotes: 8

Eduardo
Eduardo

Reputation: 8392

Many times, the compiler can optimize your code, to avoid creating a new stack frame for each recursive call (look up tail recursion, for example). Of course, it all depends on the algorithm and on your data structure. If the tree is reasonably balanced, I don't think a recursive algorithm should cause any problems.

Upvotes: 2

Related Questions