CODEWITHSUNDEEP
algorithm
user8174813
user8174813

Reputation:

One should choose recursion over iteration?

Why should one choose recursion over iteration, when a solution has the same time complexity for both cases but better space complexity for iterative?

Upvotes: 0

Views: 97

Answers (3)

Omar Essam El-Din
Omar Essam El-Din

Reputation: 1873

Some Benefits for Recursion

  • Code is Perfect Elegant (compared to loops)

  • very useful in backtracking data structures like LinkedList, Binary Search Trees as the recursion works by calling itself in addition stack made especially for this recursive calls and each call chained by its previous one

Upvotes: 0

jwimberley
jwimberley

Reputation: 1748

Here's a particular example of a case where there are extra considerations. Tree search algorithms can be defined recursively (because each subtree of a tree is a tree) or iteratively (with a stack). However, while a recursive search can work perfectly for finding the first leaf with a certain property or searching over all leaves, it does not lend itself to producing a well-behaved iterator: an object or function state that returns a leaf, and later when called again returns the next leaf, etc. In an iterative design the search stack can be stored as a static member of the object or function, but in a recursive design the call stack is lost whenever the function returns and is difficult or expensive to recreate.

Upvotes: 1

Avinash Roy
Avinash Roy

Reputation: 973

Iteration is more difficult to understand in some algorithms. An algorithm that can naturally be expressed recursively may not be as easy to understand if expressed iteratively. It can also be difficult to convert a recursive algorithm into an iterative algorithm, and verifying that the algorithms are equivalent can also be difficult.

Recursion allows you to allocate additional automatic objects at each function call. The iterative alternative is to repeatedly dynamically allocate or resize memory blocks. On many platforms automatic allocation is much faster, to the point that its speed bonus outweighs the speed penalty and storage cost of recursive calls. (But some platforms don't support allocation of large amounts of automatic data, as mentioned above; it's a trade-off.)

recursion is very beneficial when the iterative solutions requires that you simulate recursion with a stack. Recursion acknowledges that the compiler already manages a stack to accomplish precisely what you need. When you start managing your own, not only are you likely re-introducing the function call overhead you intended to avoid; but you're re-inventing a wheel (with plenty of room for bugs) that already exists in a pretty bug-free form.

Upvotes: 0

Related Questions