递归算法的复杂度通常很难衡量，一般都认为是每次递归分支数的递归深度次方。但通常情况下没有这个大，如果我们可以保存每次子递归的结果的话，递归算法的复杂性等于不同的节点个数。这也是动态规划算法思想的由来。
看一下下面这个算法题目，据称是百度的笔试题：
简述：实现一个函数，对一个正整数 n ，算得到 1 需要的最少操作次数：
如果 n 为偶数，将其处以 2 ；如果 n 为奇数，可以加 1 或减 1 ；一直处理下去。
要求：实现函数（实现尽可能高效） int func(unsigned int n)； n 为输入，返回最小的运算次数。
我不确定是不是对 n 的操作次数有一个简单的刻画，尝试着想了一会儿，似乎不太容易想到。但后来发现这个题目本质上不是算法题，而是算法分析题。因为仔细分析可以发现，题目中给的递归构造本身就是非常高效的。
直接按照题目中的操作描述可以写出函数：
int function (unsigned int n)
{
if (n == 1) return 0;
if (n % 2 == 0)
return 1 + function(n / 2);
return 2 + min(function((n + 1) / 2), function((n - 1) / 2));
}
在递归过程中，每个节点可以引出一条或两条分支，递归深度为$ \log n$ ，所以总节点数为$ n$ 级别的，但为何还说此递归本身是非常高效的呢？
理解了动态规划的思想，就很容易理解这里面的问题。因为动态规划本质上就是保存运算结果的递归，虽然递归算法经常会有指数级别的搜索节点，但这些节点往往重复率特别高，当保存每次运算的节点结果后，在重复节点的计算时，就可以直接使用已经保存过的结果，这样就大大提高了速度（每次不仅减少一个节点，而且同时消灭了这个节点后面的所有分支节点）。
在这个问题里是什么情况呢？仔细分析就会发现，在整个搜索数中，第$ k$ 层的节点只有两种可能性$ n>>k$ 和$ (n>>k) - 1$ 。这意味着整个搜索树事实上只有$ 2\log n$ 个节点。所以这个递归算法本质上的运算复杂度只有$ O(\log n)$ 。这已经是最优的了。
Q. E. D.
