I think that what the author calls "divide and conquer" is actually "recursion".
Also the complexity of naive fibonacci is exactly the fibonacci sequence so O(2^n) is correct but less precise than O(phi^n)
Also the complexity of naive fibonacci is exactly the fibonacci sequence so O(2^n) is correct but less precise than O(phi^n)
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...
"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".
That means all divide and conquer algorithms can be implemented without recursion.