Rewrite Recursive algorithm more simply - Euler 15

Question

I would like to rewrite the functionality of this algorithm (which I used to solve ProjectEuler problem 15) in a non recursive way.

Yes, I realise there are many better ways to solve the actual problem, but as a challenge I would like to simplify this logic as much as possible.

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++;
    }
}

And tests:

[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);
}

EDIT: Here is another simple function written in both ways:

//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;
}

Any hints would be greatly appreciated. I've tried dynamic programming solution (which uses a more maths based approach), and an equation to successfully solve the puzzle.

I wonder - can this first algorithm be made non recursive, simply?

possible duplicate of [Way to go from recursion to iteration](http://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration) — Kirk Woll, Jun 05 '12 at 01:46
If you mean you want to preserve the algorithm without using recursive call, so stack and loop might be used to mimic the recursion, yet I don't see any point to do so. — tia, Jun 05 '12 at 01:51
Thanks...agreed that doing a stack and loop wouldn't make things simpler.. — Dave Mateer, Jun 05 '12 at 03:12

score 0 · Accepted Answer · answered Aug 26 '13 at 17:20

The non-recursive solution is:

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;

Just for information, this problem should have been solved on the paper, the answer for NxM grid is C(N+M,N), where C is the combination function - http://en.wikipedia.org/wiki/Combination

Rewrite Recursive algorithm more simply - Euler 15

1 Answers1