What is a recursion for Huffman encoding?
Huffman's algorithm uses the greedy heuristic, which is different from the dynamic programming approach in the other problem you mention. However, we can still define the cost recursively.

There are actually several options. In all cases, given a distribution $p_1,\ldots,p_n$, we will find a formula for $C(p_1,\ldots,p_n)$, which is the optimal cost of a prefix code.

Let's start with Huffman's algorithm itself:


$C(1) = 0$.
$C(p_1,\ldots,p_n) = p_i + p_j + C(p_1,\ldots,\widehat{p_i},\ldots,\widehat{p_j},\ldots,p_n,p_i+p_j)$, where $p_i,p_j$ (for $i &lt; j$) are the two smallest probabilities (i.e. $\max(p_i,p_j) \leq p_k$ for all $k \neq i,j$), and $\widehat{p_i}$ signifies that $p_i$ is removed. 


The proof that this recurrence is correct is not immediate.

If we want a Huffman-like recurrence whose correctness is immediate, we need to tweak this only slightly:


$C(1) = 0$.
$C(p_1,\ldots,p_n) = \min_{i&lt;j} [p_i + p_j + C(p_1,\ldots,\widehat{p_i},\ldots,\widehat{p_j},\ldots,p_n,p_i+p_j)]$. 


This recurrence holds since (i) given a code for $p_1,\ldots,\widehat{p_i},\ldots,\widehat{p_j},\ldots,p_n,p_i+p_j$ we can get a code for $p_1,\ldots,p_n$ which is worse by $p_i+p_j$ by splitting the node corresponding to $p_i+p_j$ into two, and (ii) given a code for $p_1,\ldots,p_n$, if we choose any two sibling leaves $p_i,p_j$ then $C(p_1,\ldots,p_n) = p_i + p_j + C(p_1,\ldots,\widehat{p_i},\ldots,\widehat{p_j},\ldots,p_n,p_i+p_j)$.

A short reflection reveals that we can always ensure $j = n$ (say), and this leads to a simpler recurrence:


$C(1) = 0$.
$C(p_1,\ldots,p_n) = \min_{i&lt;n} [p_i + p_n + C(p_1,\ldots,\widehat{p_i},\ldots,p_{n-1},p_i+p_n)]$. 


The last two recurrences are bottom-up. There is also a top-down recurrence:


$C(1) = 0$.
$C(p_1,\ldots,p_n) = 1 + \min_{S \sqcup T = [n]} [C(p_S) + C(p_T)]$, where the minimization is over all partitions of $\{1,\ldots,n\}$ into two non-empty sets, and $p_S = (p_i : i \in S)$.


In this recurrence we are splitting the root instead of merging two sibling leaves. I leave to correctness proof for the reader.

Only the first recurrence above can be implemented efficiently.