Theoretical foundations of Divide and Conquer When it comes to the design of algorithms, one often employs the following techniques:


Dynamic Programming
The Greedy-Strategy
Divide-and-Conquer


While for the first two methods, there are well-known theoretical foundations, namely the Bellman Optimality Principle and matroid (resp. greedoid) theory, I could not find such a general framework for algorithms based on D&amp;C. 

Firstly, I am aware of something that we (or rather, the prof) introduced  in a functional programming class,  called an "algorithmic skeleton", that arose in the context of combinators. As an example hereof, we gave such a skeleton for D&amp;C algorithms as follows: 

Definition: Let $A,S$ be non-empty sets. We call the elements of $S$ solutions, and the elements of $P:=\mathfrak{P}(A)$ (that is, the subsets of $A$) are referred to as problems.
Then, a D&amp;C-skeleton is a 4-tuple $(P_\beta, \beta, \mathcal{D}, \mathcal{C})$, where: 


$P_\beta$ is a predicate over the set of problems and we say that a problem $p$ is basic iff $P_\beta(p)$ holds.
$\beta$ is a mapping $P_\beta \rightarrow S$ that assigns a solution to each basic problem. 
$\mathcal{D}$ is a mapping  $P \rightarrow \mathfrak{P}(P)$ that divides each problem into a set of subproblems.
$\mathcal{C}$ is a mapping $P\times \mathfrak{P}(S) \rightarrow S$ that joins the solutions (depending on kind of a "pivot problem") of the subproblems to produce a solution. 


Then, for a given skeleton $s=(P_\beta, \beta, \mathcal{D}, \mathcal{C})$ and a problem $p$, the following generic function $f_s: P\rightarrow S$ computes a solution (in the formal sense) for $p$:

$f_s(p)= \left\{
  \begin{array}{l l}
    \beta(p) &amp; \quad \text{if $p$ is basic}\\
    \mathcal{C}(p,f(\mathcal{D}(p))) &amp; \quad \text{otherwise}
  \end{array} \right.$

where in the second line we use the notation $f(X) := \{f(x)  : x\in X\}$ for subsets $X$ of the codomain of a mapping $f$.

However, we did not further examine the underlying, "structural" properties of problems that can be formulated this way (as I said, it was a functional programming class and this was only a small example). Unfortunately, I could not find further reference on this very approach. Hence I don't think the above definitions are quite standard. If someone recognizes what I have stated above, I would be glad about related articles.

Secondly, for the greedy strategy we have the famous result that a problem is correctly solved by the general greedy algorithm if and only if its solutions constitute a weighted matroid. Are there similar results for D&amp;C-algorithms (not necessarily based on the method outlined above)?
A formal treatment (somewhat resembling the model proposed in the question) of the subject using what is called pseudo-morphisms (that is, functions that are almost morphisms, with some pre- and post-computation done), as well as considerations of complexity analysis and parallel implementation of such algorithms are given in:

An algebraic model for divide-and-conquer and its parallelism by Zhijing G. Mou and Paul Hudak
 (in The Journal of Supercomputing , Volume 2, Issue 3, pp. 257-278, November 1988)