更简单地重写递归算法 - 欧拉15

我想以非递归方式重写此算法的功能（我用它来解决ProjectEuler问题15）。更简单地重写递归算法 - 欧拉15

是的，我意识到有很多更好的方法来解决实际问题，但作为一个挑战，我想尽可能简化这个逻辑。

public class SolveRecursion 
{ 
    public long Combination = 0; 
    public int GridSize; 

    public void CalculateCombination(int x = 0, int y = 0) 
    { 
     if (x < GridSize) 
     { 
      CalculateCombination(x + 1, y); 
     } 
     if (y < GridSize) 
     { 
      CalculateCombination(x, y + 1); 
     } 
     if (x == GridSize && y == GridSize) 
      Combination++; 
    } 
}

而且测试：

[Test] 
public void SolveRecursion_GivenThree_GivesAnswerOf20Routes() 
{ 
    solveRecursion.GridSize = 3; 
    solveRecursion.CalculateCombination(); 
    var result = solveRecursion.Combination; 
    Assert.AreEqual(20, result); 
} 

[Test] 
public void SolveRecursion_GivenFour_GivesAnswerOf70Routes() 
{ 
    solveRecursion.GridSize = 4; 
    solveRecursion.CalculateCombination(); 
    var result = solveRecursion.Combination; 
    Assert.AreEqual(70, result); 
}

编辑：这是一个用两种方式另一种简单的功能：

//recursion 
private int Factorial(int number) 
{ 
    if (number == 0) 
     return 1; 
    int returnedValue = Factorial(number - 1); 

    int result = number*returnedValue; 
    return result; 
} 

//loop 
private int FactorialAsLoop(int number) 
{ 
    //4*3*2*1 
    for (int i = number-1; i >= 1; i--) 
    { 
     number = number*i; 
    } 
    return number; 
}

任何提示将不胜感激。我已经尝试了动态编程解决方案（它使用了更多的基于数学的方法）以及成功解决难题的等式。

我想知道 - 第一个算法可以做成非递归吗？

来源

2012-06-05 Dave Mateer

[从递归到迭代的方式]可能的重复（http://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration） –

如果你意味着你不想使用递归调用来保存算法，所以栈和循环可能被用来模仿递归，但我没有看到有任何意见要这样做。 – tia

谢谢...同意做一个堆栈和循环不会让事情变得更简单.. –

的非递归的解决方案是：

const int n = 4; 
int a[n + 2][n + 2] = {0}; 

a[0][0] = 1; 
for (int i = 0; i < n + 1; ++i) 
    for (int j = 0; j < n + 1; ++j) { 
     a[i][j + 1] += a[i][j]; 
     a[i + 1][j] += a[i][j]; 
    } 

std::cout << a[n][n] << std::endl;

只为信息，这个问题应该得到了解决在纸上，为N×M个网格中的答案是C（N + M，N），其中C是组合功能 - http://en.wikipedia.org/wiki/Combination

来源

2013-08-26 17:20:46 frangulyan

更简单地重写递归算法 - 欧拉15

回答

相关问题