C# Recursion Logic

Question

I am attempting to write a function in which the number of nested loops is dependent upon an integer (numStroke) passed into it. For example, when numStrokes is 1, the code executed should be:

double checkProfitability(GameState state, int numStrokes)
{
    double[] possiblePayoffs = new double[50000];
    int pPIndex = 0;
    double sumOfPayoffs = 0;
    double averagePayoff = 0;

    for (int i = 0; i <= 5; i++)
    {
        // Populate possiblePayoffs[]
    }

    for (int ii = 0; ii < pPIndex; ii++)
    {
        sumOfPayoffs += possiblePayoffs[i];
    }

    averagePayoff = sumOfPayoffs / pPIndex;

    return averagePayoff;
}

When numStrokes is 3, it should be:

double checkProfitability(GameState state, int numStrokes)
{
    double[] possiblePayoffs = new double[50000];
    int pPIndex = 0;
    double sumOfPayoffs = 0;
    double averagePayoff = 0;

    for (int i = 0; i <= 5; i++)
    {
        state.colors[i]++;

        for (int j = 0; j <= 5; j++)
        {
            state.colors[j]++;

            for (int k = 0; k <= 5; k++)
            {
                // Populate possiblePayoffs[]
            }

            state.colors[j]--;
        }

        state.colors[i]--;
    }

    for (int ii = 0; ii < pPIndex; ii++)
    {
        sumOfPayoffs += possiblePayoffs[i];
    }

    averagePayoff = sumOfPayoffs / pPIndex;

    return averagePayoff;
}

Linked is the extra example of when numStrokes is 6, just in case what I'm trying to do isn't already clear:

http://hastebin.com/hemolikodo.avrasm

So far, I have come up with the following attempt to implement numStrokes amount of nested loops, but it does not work (if for no other reason, because the function tries to create another copy of int i when it calls itself recursively). I'm not sure if this code is even the right approach. I'm not even certain that I should be trying to do this recursively. I considered just using a giant if statement that executes code based on the value of numStrokes, but a more general implementation seemed preferable.

double checkProfitability(GameState state, int numStrokes, int i)
{
    double[] possiblePayoffs = new double[50000];
    int pPIndex = 0;
    double sumOfPayoffs = 0;
    double averagePayoff = 0;

    if (numStrokes == 0)
    {
        // Populate possiblePayoffs[]
    }
    else
    {
        for (int i = 0; i <= 5 && numStrokes >= 1; i++)
        {
            checkProfitability(state, --numStrokes, i);
        }
    }

    for (int ii = 0; ii < pPIndex; ii++)
    {
        sumOfPayoffs += possiblePayoffs[ii];
    }

    averagePayoff = sumOfPayoffs / pPIndex;
    richTextBox1.Text = averagePayoff.ToString();

    return averagePayoff;
}

Can anyone explain how to implement this properly?

Edit: The problem is that I don't know how many nested loops I need until run time.

that shouldn't even compile since you define two variables with the same name. — Steffen Winkler
– Steffen Winkler, Commented Jun 10, 2014 at 13:13
You are modifying state.colors, but then don't even use that in the "return" value that uses a pIndex and possiblePayoffs that are not modified. — crashmstr
– crashmstr, Commented Jun 10, 2014 at 13:14
@crashmstr state.colors[] is used to assign values to possiblePayoffs. I replaced the algorithm with the comment // Populate possiblePayoffs[] because the code is lengthy. — user10478
– user10478, Commented Jun 10, 2014 at 13:18
@Steffen Winkler That is correct, the code as stated does not work for that very reason. I'm open to a correction which would fix the problem you mentioned, and cause the code to behave like the "unrolled" examples above it, or a whole new way to approach the problem of a contingent number of nested loops. — user10478
– user10478, Commented Jun 10, 2014 at 13:22

Atomosk · Accepted Answer · 2014-06-11 03:00:22Z

1

for (int i = 0; i < Math.Pow(6, numStrokes); i++)
{
    int innerForIndex = i;
    for (int j = 0; j < numStrokes; j++)
    {
        colors[innerForIndex % 6]++;
        innerForIndex /= 6;
    }

    //populate your possiblePayoffs[]

    innerForIndex = i;
    for (int j = 0; j < numStrokes; j++)
    {
        colors[innerForIndex % 6]--;
        innerForIndex /= 6;
    }

}

numStrokes for loops from 0 to 5 inclusive means you have total Math.Pow(6, numStrokes) elements. You use your inner loops indexes to increment/decrement some cololrs array. Those indexes can be easily calculated from element number. For numStroke == 3 example k can be calculated as innerForIndex % 6, j as (innerForIndex / 6) % 6, i as ((innerForIndex / 6) / 6) % 6.

answered Jun 11, 2014 at 3:00

Atomosk

2,0172 gold badges23 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Enigmativity · Accepted Answer · 2014-06-11 05:40:36Z

This is the closest I think I can get you to a solution for this.

First up this is the checkProfitability method:

double checkProfitability(GameState state, int numStrokes)
{
    var possiblePayoffs = new double[50000];
    computePayoffs(state, possiblePayoffs, Enumerable.Empty<int>(), numStrokes);
    var averagePayoff = possiblePayoffs.Select(x => (double)x).Average();
    richTextBox1.Text = averagePayoff.ToString();
    return averagePayoff;
}

The recursion is now in the computePayoffs method:

void computePayoffs(GameState state, int[] possiblePayoffs,
    IEnumerable<int> values, int numStrokes)
{
    if (numStrokes == 0)
    {
        // Populate possiblePayoffs[]
    }
    else
    {
        for (int i = 0; i <= 5; i++)
        {
            state.colors[i]++;
            computePayoffs(
                    state,
                    possiblePayoffs,
                    values.Concat(new [] { i }),
                    numStrokes - 1);
            state.colors[i]--;
        }
    }
}

Kevin Cook · Accepted Answer · 2014-06-10 13:23:59Z

0

for (int i = 0; i <= 5 * numstrokes; i++)
{
    // Populate possiblePayoffs[]
    if(i % 5 == 0)
    {
        //start of next loop
    }
}

Why not do this?

edited Jun 10, 2014 at 13:23

answered Jun 10, 2014 at 13:17

Kevin Cook

1,9321 gold badge15 silver badges16 bronze badges

1 Comment

user10478 Over a year ago

// Populate possiblePayoffs[] is not supposed to happen until the innermost nested loop though. The problem is that I don't know how many nested loops I need until run time, not that the number of iterations through each loop is variable.

Binesh Nambiar C · Accepted Answer · 2014-06-10 13:29:58Z

0

The question is not clear. But I think recursion will help you to solve these type of cases. What i could understand is you need to do some looping numstocks*6(The below code will loop this much time. If this is the case The code will be structured as(Didn't test it. May need some minor modifications)

double checkProfitability(GameState state, int numStrokes)
{
if(numStrokes!=0)
{
    for (int i = 0; i <= 5; i++)
    {
       checkProfitability(state,numStrokes-1);
    }
}
//your code  //calls this code numStrokes*6 times
}

More over beware of stackoverflow Exception also

answered Jun 10, 2014 at 13:29

Binesh Nambiar C

1621 gold badge2 silver badges10 bronze badges

1 Comment

user10478 Over a year ago

I think I actually need to loop 6 ^ numStrokes times, rather than 6 * numStrokes, but yeah, your code is on the right track. What I don't understand is how this can work without passing i into the function. If numStrokes = 2, for example, I need to execute: for (int i = 0; i <= 5; i++) {state.colors[i]++; for (int j = 0; j <= 5; j++) {state.colors[j]++; // Do other stuff; state.colors[j]--;} state.colors[i]--;}. I cannot see how incrementing and decrementing state.colors[i] and state.colors[j] are possible without passing in the iteration number.

Collectives™ on Stack Overflow

C# Recursion Logic

4 Answers 4

Comments

Comments

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related