Recursion is not the same as divide and conquer. Divide and conquer is a category of algorithms that you would often implement with recursion, but you don't have to.

For example, consider the bottom-up implementation of merge sort [1]. This implementation is not recursive, but merge sort uses divide and conquer regardless of whether or not you implement it top-down or bottom-up.

On the other hand, the naive fibonacci implementation that runs in exponential type is recursive, but it does not use divide and conquer.

[1]: https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implement...

"Recursion" is part of the "how" of the "why" of "divide and conquer" :P

Seems you got down-voted. I guess you're doing competitive programming? People that are good at CP never call "recursion with memoization" as "divide and conquer". Yeah, they just call it recursion.

"Divide and conquer" in CP world seems to be specific to those problems whose subproblems are not overlapping (therefore completely "divided"), e.g. merge sort, segment trees.

Considering the classic problem "Tower of Hanoi", is it "divide and conquer"? No to CP people, and even Wikipedia [0] does not explicitly regard it as "divide and conquer".

[0]: https://en.wikipedia.org/wiki/Tower_of_Hanoi

All recursion can be translated into a loop and a stack. In the tail recursive case you don’t even need a stack, a loop would suffice.

That means all divide and conquer algorithms can be implemented without recursion.