Do all recursive problems have optimal substructure?

Question

I am reading about dynamic programming and I understand the overlapping subproblem requirement but not sure why optimal substructure is explicitly stated. Are there problems that can be solved recursively that do not have an optimal substructure?

Answer 1

I think there is some confusion in terminology here. Part of the problem is what we mean by problem and algorithm. But there is more to it:

1. Textbooks like CLRS introduce the notion of optimal substructure as a property of problems (and not algorithms directly). That's because an algorithm often transforms a problem statement into other problem/s and, as a result, an algorithm may establish a link between problem solutions with subproblem solutions. Indeed, CLRS defines optimal substructure as follows: "A problem exhibits optimal substructure if a solution to the problem contains solutions to its sub-problems". While it doesn't say this directly, the term "contains" implies through an algorithm.

2. Just because a problem (and actually all problems) may accept a recursive formulation or algorithm, it doesn't of course mean of course that every algorithm to solve it is indeed recursive (this is in relation to Yuval Filmus's answer). For a particular algorithm to be recursive, it must call itself recursively.

3. Similarly, just because an algorithm may involve some form of iteration or even recursion (e.g. in some of its subroutines), it doesn't mean that the algorithm is actually solving the original problem recursively.

4. Last but not least, just because an algorithm is recursive, it does not mean it solves a problem with optimal substructure where solutions to the original problem are the result of combining solutions to sub-problems of the same type. For example, if you write an algorithm to sort numbers, and this algorithm sorts the input and then once it's done sorting, it e.g. calls itself recursively with a NOP in each call for some depth of recursion, that does not mean that the algorithm is actually building the sorted sequence (the solution to the stated problem) from solutions to subproblems, and thus exploiting the optimal substructure of the problem.

Answer 2

Every problem can be solved recursively. Recall first that every problem can be solved using an algorithm which uses a WHILE loop and conditionals. Indeed, the operation of a CPU can be described in this way. We can adapt this solution to a (tail) recursive procedure as follows.

The parameters are the instruction pointer, the content of the registers, and the content of memory. The procedure performs the instruction that the instruction pointer is pointing at, modifying the instruction pointer, the registers, and the memory. Then (unless the instruction was HALT), it calls itself recursively with the updated instruction pointer, register contents, and memory contents.

Answer 3

When solving an optimization problem recursively, optimal substructure is the requirement that the optimal solution of a problem can be obtained by extending the optimal solution of a subproblem (see for example, Cormen et al. 3ed, ch. 15.3).

Consider for example the problem of finding a simple shortest $s$-$t$ path in a directed graph with non-negative distances. Such a path must visit a predecessor $u$ of $t$. So if you are able to recursively find the shortest $s$-$u$ path for all predecessors $u$ of $t$, you can find a shortest $s$-$t$ path. In this case you have an optimal substructure.

Contrast this with finding a simple longest $s$-$t$ path. Such a path must also visit a predecessor $u$ of $t$. However, it isn't true that the longest $s$-$t$ path can be obtained by extending some longest $s$-$u$ path for a predecessor $u$ of $t$, since such a path may already visit $t$, and so its extension may not be a simple path, and you cannot remove the resulting cycle to make the path simple, since this can make it shorter. In this case you don't have an optimal substructure.

The longest $s$-$t$ path can be found by choosing a different kind of subproblem that has optimal substructure. If you define $C(s,t,V)$ as the longest path from $s$ to $t$ without visiting the vertices in $V$, you get \begin{align*} C(s,t,V)= \begin{cases} \max_{u\in N^{-}(t)\setminus V} C(s,u,V\cup\{t\})+d_{ut}, & \text{if $s\neq t$ and $N^{-}(t)\setminus V\neq \emptyset$},\\ -\infty, & \text{if $s\neq t$ and $N^{-}(t)\setminus V=\emptyset$},\\ 0, & \text{if $s=t$}, \end{cases} \end{align*} where $N^-(t)$ is the set of predecessors of vertex $t$, and $d_{uv}$ is the distance between $u$ and $v$.

Answer 4

The article you were reading might not be not good enough for educational purpose, especially for a beginner in dynamic programming. It is not accurate enough, either.

It is apparent, as noticed by Marcus Ritt that article copies from the Wikipedia article on dynamic programming, a lot.

However, that article is not up to date with the following statement at the latest version of Wikipedia,

Likewise, in computer science, if a problem can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have optimal substructure.

We can compare the statement above with the following statement in the article, where "recursively" instead of "optimally" is used to define optimal substructure, which is not correct.

Likewise, in computer science, a problem that can be broken down recursively is said to have optimal substructure."

---

Are there problems that can be solved recursively that do not have an optimal substructure?

This question is more or less off the point in the sense that being recursive is not related to being optimal. Not directly.

The truism would be that problems that can be solved recursively should have recursive substructures. Likewise, if an optimization problem can be solved by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have optimal substructure.

If we have to answer that question head-on, then the answer is, of course, yes and plenty of them. We can compute Fibonacci numbers recursively, but there is no apparent optimal substructure in Fibonacci numbers. We can compute recursively the factorials which does not have substructure that can be called optimal reasonably.

In fact, Yuval's answer presents a common view that explained why most programs can be considered or adapted as solving problems recursively.

---

It might have been better had you followed an excellent textbook, such as the most popular textbook Introduction to Algorithm by CLRS, in case you have not read it yet. Its chapter 15, Dynamic Programming explains the basic concepts and techniques about dynamic programming clearly. Section 3 of that chapter, elements of dynamic programming, elaborates on the components of dynamic programming, "Optimal substructure", "Overlapping subproblems", "Reconstructing an optimal solution" and "Memoization".