这里以 P4999为例，

状态 $f_{i,1/0}$ 代表从高到低填到第 $i$ 位了当前已经填的这些位是等于 $x$ 的这些位还是小于 $x$ 的这些位，这种情况下的方案数。

$g$ 代表数位之和。

状态 $f_{pos,sum}$ 代表位置 $[pos+1,len]$ 已经填完了，这些数位之和在 $sum$ 的情况下，数位 $[1,pos]$ 无 $limit$ 的情况下，所有数的数位之和。

递归式：

LL dfs(int pos, bool limit, int sum)
{
    if(!pos) return sum;
    if(!limit && ~f[pos][sum])
        return f[pos][sum];
    int up = limit ? a[pos] : 9; // 上限
    LL res = 0;
    for(int i = 0; i <= up; i++)
        res = (res + dfs(pos - 1, limit && i == up, sum + i)) % MOD;
    if(!limit)
        f[pos][sum] = res;
    return res;
}
LL solve(LL x)
{
    int len = 0;
    while(x)
    {
        a[++len] = x % 10;
        x /= 10;
    }
    return dfs(len, true, 0);
}

递推式：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;  
const int MOD = 1e9 + 7;

int a[22];
LL f[22][2];
LL g[22][2];

LL solve(LL x)
{
    memset(a, 0, sizeof(a));
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    int len = 0;
    while(x)
    {
        a[++len] = x % 10;
        x /= 10;
    }
    f[len + 1][1] = 1;
    for(int i = len + 1; i >= 2; i--)
        for(int j = 0; j <= 1; j++)
            for(int r = 0; r <= 9; r++)
            {
                if(j == 1 && r > a[i - 1]) continue;
                f[i - 1][j && (r == a[i - 1])] = (f[i][j] + f[i - 1][j && (r == a[i - 1])]) % MOD;
                g[i - 1][j && (r == a[i - 1])] = (g[i - 1][j && (r == a[i - 1])] + g[i][j] + f[i][j] * r) % MOD;
            }
    return (g[1][0] + g[1][1]) % MOD;
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        LL l, r;
        scanf("%lld%lld", &l, &r);
        LL ans = (solve(r) - solve(l - 1) + MOD) % MOD;
        cout << ans << endl;
    }
    return 0;
}

两种写法的时间复杂度是一样的，但是递推是从高位往低位递推，低位借助高位的信息实现状态转移； 而递归是通过记录已经搜索过的后缀信息，实现高位到低位的跨越，相当于先处理出低位再转移到高位。 根据多叉树的结构，记录前缀状态所花费的空间明显比记录后缀所花费的空间要少，假如记录的状态值域大一点的话就有爆空间的风险。

而递归式的写法比递推式的写法思维难度要低一些。

所以孰优孰劣？