Search code examples
algorithmrecursiondivide-and-conquer

All divide and conquer approach use recursive functions or not necessarily?


Do all algorithms that use the divide and conquer approach use recursive functions or not necessarily?


Solution

  • Binary search is an application of the D&C paradigm. (As follows: split in two halves and continue into the half that may contain the key.)

    It can be implemented both recursively or non-recursively.

    Recursion is handy when you need to keep both "halves" of a split and queue them for later processing. A common situation is called tail recursion, when you only queue one of the halves and process the other immediately. In binary search, you just drop one of the halves.


    In a very broad sense, D&C is the father of all algorithms when stated as "break the problem into easier subproblems of the same kind". This definition also encompasses iterative solutions, often implemented without recursion.