recursion - 尝试将递归函数更改为迭代函数

Question

我正在尝试将递归函数转换为迭代函数。偶数/奇数的计算不同的部分是我无法弄清楚如何获得迭代解决方案。以下是有问题的功能。

public static int a(int n)
{
    if(n==1) return 1;
    else if(n%2 == 0) return a(n/2)*4;
    else return (a((n-1)/2)+a((n+1)/2))*2;
}

这个函数是我对这个视频中描述的问题的解决方案（你需要在给定数量的钩子周围绑多少圈，以便移除一个钩子解开所有剩余的圈）。

得到的序列是 1, 4, 10, 16, 28, 40, 52, 64, 88, 112, ... 它的增加值确实有一些规律性。

我设法获得了 2^n 序列中值的解决方案：4^(log(n)/log(2))

但是，是否有针对全系列的迭代解决方案？

标签： recursion

Answer 1

想了半天，自己也确实找到了一个迭代的解决方案。它可能不是最优的，因为它比递归解决方案复杂得多（并且比递归解决方案慢很多）。

public static int b(int n)
{
    int k = 1, result = 1;
    for (int i = 0; i < Math.Ceiling(Math.Log(n, 2)); i++)
    {
        for (; k < ((n < (Math.Pow(2, i + 1))) ? n : (Math.Pow(2, i + 1))); k++)
        {
            result += (int)(3 * (Math.Pow(2, i)));
        }
    }

    return result;
}