统计前n个数中出现1的个数（递推式）

设fn(n)表示前n个数中出现1的数量，这里假设n为10234，则有：
对上述递推式进行讲解:
对于数10214，其出现的数字分布可以分为：
0-9999，10000-10214，将两个分布出现的1的次数相加即得总的1出现的次数。
对于分布10000-10214，我们发现最高位的1一共出现了215次，将这215次累加，那么之后出现的1只需统计除最高位之外的1了，于是问题转变成了求1-214分布的数字中出现1的个数。

对于数234，同理分为：
0-99，100-199，200-214
这里共出现了两次0-99的分布（0-99，100-199），统计0-99的1的个数乘以2。对于分布200-214，由于最高位不是1，那么剩余1的贡献就是求从0-14的数字中的1的次数。

依次处理，直到当前数为0。
设

则上述递推式可表示为：
利用该递推式，可以直接用递归算法做，也可以从最低位遍历到最高位，依次计算fn(0),fn(14),fn(214),fn(10214),后一项的计算依赖前一项的计算，因此也用循环来做。但是需注意，fn(214)直接跳到了fn(10214),因为fn(0214)==fn(214), 不可以重复计算。
并且也是可以直接递推出来的。