CODEWITHSUNDEEP
algorithmdivide-and-conquer
Andrew Tobey
Andrew Tobey

Reputation: 923

Does any divide-and-conquer algorithm use recursion

I am arguing with a fellow student, as he wants to convince me that there is a possibility that a divide-and-conquer algorithm can be implemented without the use of recursion.

Is this truly the case?

Upvotes: 2

Views: 340

Answers (2)

Gentian Kasa
Gentian Kasa

Reputation: 776

There's an important thing to understand: using or not recursion is an implementation decision. Recursion is not necessary to add computing power (at least not to a Turing complete language). Look up "Tail recursion" for an easy example of how to transform a recursive function to a non recursive one (in the case of a divide-et-impera algorithm you can remove at most 1 of the recursive calls with this method).

A function/algorithm that is computable with recursion is computable also without it. What matters is if the language with which you implement the algorithm is Turing complete or not.

Let's make an example. The mergesort algorithm can be implemented also in a non recursive way using a queue as an auxiliary data structure to keep track of the various merges.

Upvotes: 0

Eric J.
Eric J.

Reputation: 150108

Any algorithm that can be implemented with recursion can also be implemented non-recursively.

Recursion and iteration are equally expressive: recursion can be replaced by iteration with an explicit stack, while iteration can be replaced with tail recursion. Which approach is preferable depends on the problem under consideration and the language used.

http://en.wikipedia.org/wiki/Recursion_%28computer_science%29#Recursion_versus_iteration

Upvotes: 7

Related Questions