递归计算向非递归计算转换模板 -- 续

要论速度，通项公式也不便宜.
我觉得LZ需要的是，能够根据一个递归公式自动推算出同项公式的程序.
这个东西，能够作出来就很NB哦.哪怕只是针对某一类递归函数.

通项公式大部分时候是比较便宜的 CPU那句话说的就是这个意思...... 时间复杂度降了


要做这个东西其实麻烦在依赖数学比较多 复数运算+高次方程+多元方程组
如果能找到相应的lib 就很容易搞定了

所以说实话 楼主这个把递归转换成递推意义不大 情况太特定了 仅仅针对实数域上的递归函数有效

这个问题,要看你计算n的有多少大,(1+√5)/2]^n,n是25的时候就已经超出65535了.再往上算,Int型就不够往上的大整数计算都是靠快速傅立叶变换做的,FFT 的主要的瓶颈是蝶形运算,这就需要用到非常好的矩阵算法库.如果是大浮点数的话可能还需要快速数论变换.这种计算量就非常之大了.



与这些东西都无关,
关键的部分在于,你要能证明针对某一类型的递归函数推导出它的通项公式的这一过程是可计算的.
自己手动推导通项公式，在这里没有多大意义.

推导过程组合数学已经有了 不过把它用计算机描述出来需要 复数运算+高次方程+多元方程组 这几个东西

整型范围不是0-65535呀 那是16位机的整型......
n次方硬件浮点运算很快的 你试试Fibonacci的通项公式就知道了 比递推快多了......

FFT的话......只适用于特定领域的BT需求>_< 一般是超过机器浮点运算表示范围或者精度范围才会用到 像这种组合数学游戏是不需要的 一般语言本身提供的幂运算足够了......

另外 不管怎么变换 幂运算只能变得更快不是么..... 要不还不如直接乘了 复杂度最多也就O(logN)吧？O(logN)跟O(N)相差可不少

汗 学数学的思维就是强大 提到幂运算立刻就想到FFT了

线形/差分递推式的求解当然是有的.
但是我这里强调的是,推导的过程是可计算的.
比如Fib,你首先是要找到生成函数.x/(1-x-x^2) ，然后根据生成函数找到通项公式.
当然通过特征方程找通项公式也很容易,但是特征方程如何找到呢?这样一种找法是不是可计算得?
比如说,A(n)=1+1/A(n-1),A(n) 你能不能找到一种机械的算法找到他的同项公式?



即便是幂求解很快,问题是通项公式都是那么简单的吗?
比如找硬币问题的通项公式，给你1，2，5分的硬币.就算你找到了特征方程,你仍然要解8个待定系数的，5次方程才能找到通项公式.你觉得这个解法是搞通项公式快,还是动态规划法快?

所以我说复杂搜索楼主的模板处理不了 简单的（比如我说的复数运算+高次方程+多元方程组 就是指常系数线性的递推关系 所有常系数线性齐次的差分方程解都是通项公式都是幂运算没错吧）又有快速计算的通项公式

比如说你又如何从1，2，5分问题的搜索算法找出DP算法呢？其实这个跟递归的形式没有关系 重点在于搜索跟DP算法的差距。Functional语言同样要用递归来描述DP算法。

剩下楼主这个模板适用的 也就剩下尾递归了。而在算法比较熟练的人手里尾递归几乎不可能出现(要是能写出递推公式来，有多少人傻到直接翻成递归去算)，且不少编译器能识别并转换尾递归 所以说 这有多大意义？

我觉得在语法树上识别尾递归并且加以优化才算比较有意义的研究 建议楼主往这方向发展发展

PS.要是我我能找到任何一个递推的机械计算方法，我第一个就找出
A(n)=A(n-1)+1/n,A(1)=1来 哥德巴赫猜想基本就差不多了 hiahia

不仅仅是尾部递归吧？比如说如下递归:
f(x)=(f(x/4-1) + f(x/6-2))/f(x-2)
这个可比尾部递归复杂多了，但是能通过上面的模板进行转换。不过我不知道这属于哪一类递归，其实我也不知道该怎样给递归公式分类。

这个帖子是我从当前应用开发中总结出来的一条规律，出自实际业务中的需求，现在程序运行的非常好。其实我没想过要在数学理论上研究一番然后发表一篇类似论文的东西。数学的发展远远的超过了时代，复杂的数学模型在自然界都很难找到对应的存在，更何况在当前的商业应用中。比如自从毕业后，我还从来没有使用过如复数的计算等东东。

当然了，如果各位是数学方面的专业人才，是应该研究研究，数学理论的发展就看你们的了。

一个问题是。
如果楼主只是为了提高时间效率，只需要用查表法(结果缓存)本身就够了。
反正都是缓存结果，递归形式和非递归形式的时间效率和空间效率是一样的。
为什么还需要用那个复杂的模型转换呢？

简单的说 如果能写出这种公式了
这类问题直接用for从小到大就可以了
f[0]=XXX;f[1]=XXX;f[3]=XXX;
for(x=3;x<n;x++)
{
    f[x]=(f[x/4-1]+f[x/6-2])/f[x-2];
}