C# Counting Items Without Recursion

Question

I need to solve a test question that asks to count how many apples can be eaten in total when X apples are given as a start amount, Y apples are eaten every time, and 1 apple is added every time apples are eaten.

My current solution uses a recursive function and therefore would cause an infinite loop if Y is smaller than X or if given X is way large.

public class Apples
{
    // Counts iterations. If we eat less than we add new every, it'll loop infinetely!
    private static int _recursions;

    private static int _applesRemaining;
    private static int _applesEaten;


    public static int CountApples(int startingAmount, int newEvery)
    {
        if (newEvery > startingAmount) newEvery = startingAmount;
        Console.WriteLine("startingAmount: " + startingAmount + ", newEvery: " + newEvery);

        _applesRemaining = startingAmount;

        /* Eat 'newEvery' amount */
        _applesRemaining -= newEvery;
        _applesEaten += newEvery;

        Console.WriteLine("Eat: " + newEvery + ", remaining: " + _applesRemaining);

        /* Get one additional candy */
        _applesRemaining += 1;
        Console.WriteLine("Added 1.");

        if (_applesRemaining > 1 && _recursions++ < 1000)
        {
            CountApples(_applesRemaining, newEvery);
        }
        else
        {
            if (_recursions > 1000) Console.WriteLine("ABORTED!");

            /* Eat the one we've just added last. */
            _applesEaten += 1;
        }

        return _applesEaten;
    }


    public static void Main(string[] args)
    {
        Console.WriteLine(CountApples(10, 2) + "\n");
    }
}

How can I make this more efficient? There's probably a more elegant way to do this but I can't figure it out.

EDIT: Original test question text:

/**
 * You are given startingAmount of Apples. Whenever you eat a certain number of
 * apples (newEvery), you get an additional apple.
 *
 * What is the maximum number of apples you can eat?
 *
 * For example, if startingAmount equals 3 and newEvery equals 2, you can eat 5 apples in total:
 * 
 * Eat 2. Get 1. Remaining 2.
 * Eat 2. Get 1. Remaining 1.
 * Eat 1.
 */

Answer 1

Not sure if you are restricted in the answer but with some maths you can come up with the following method:

public int CheatEatenApples(int startingApples, int newEvery)
{
    var firstGuess = (double)startingApples*newEvery/(newEvery-1);

    if (firstGuess%1==0) // Checks if firstGuess is a whole number
    {
        return (int)firstGuess-1;
    }
    else
    {
        return (int)firstGuess;
    }
}

The first guess is calculated using the fact that we keep getting new apples so for every newEvery apples we've eaten one of them was free! Of course this actually breaks down if the first guess is a whole number. This would require the free apple to have been given in order to allow us to eat it. Confusing so lets look at an example.

If we have 3 apples and we get a new apple every two then our first guess is 6 apples. However that's three free apples and we'd only get the third one after we've eaten 6 which relies on three free ones! So in this case we need to take one off. The rest of the time we can just round down to remove the fractional part which represents how close we are to a free apple.

And this just goes to show that the maths you learn at school can be used in the real world. The above is a few simple calculations and is probably going to be faster than most iterative/recursive methods of calculating this.

Additional note: It was pointed out in a now deleted comment that this could be better done using integer arithmetic for the firstGuess calculation. This would save needing to cast back to int for the return value. The reason it is written as it is currently is partly because it is the way I was thinking about it when writing it and partly because while I was iterating for the right answer I was viewing that decimal part while debugging (to confirm it was only when firstGuess was whole that I needed to do something special).

If you did change to integer maths instead then the if condition would need to be changed (since it would no longer work as is) and you would then end up with Sefe's answer.

Final Note:

If you did want to do an iterative technique then the following method matches the specification:

public int CalculateEatenApples(int startingApples, int newEvery)
{
    int applesEaten = 0;
    int apples = startingApples;
    while (apples>0)
    {
        applesEaten++;
        apples--;
        if (applesEaten%newEvery==0)
        {
            apples++;
        }
    }
    return applesEaten;
}

Its pretty straightforward. while you have apples it increases the count of ones you've eaten and decreases those you have left. Then if the number you have eaten is a multiple of newEvery then it adds an extra one.

Answer 2

Recursion for this problem seems like overkill so I'd suggest an alternative mathematical approach.

Lets start with the fact that we'll always eat at least X apples. The real question is how much apples in total will have been added after everything gets eaten.

Say that ni will be the number of apples remaining after i "eatings". Then:

n0 = X
n1 = X - Y + 1
n2 = X - 2Y + 2
...
ni = X - i(Y - 1)

Solving for ni = 0 will give us i - the number of "eatings" required to eat everything:

ni = 0 = X - i(Y - 1) => i = X / (Y - 1)

Now we know how many times we'll eat, so the total number of apples that are going to be eaten is the original X plus the number of times Y apples get eaten (since every time we get an extra apple when doing so):

tot = X + roundDown(i) = X * roundDown(X / (Y - 1))

We round down the result since setting ni = 0 captures a partial number of "eatings" that then result in partial apples.

Example:

X = 7, Y = 3 => tot = 7 + roundDown(7 / (3 - 1)) = 7 + roundDown(3.5) = 10
starting with 7:
0 eaten, 7 remain
3 eaten, 1 gained, 5 remain
3 eaten, 1 gained, 3 remain
3 eaten, 1 gained, 1 remains
1 eaten, nothing gained, nothing remains
--
10 eaten in total

Answer 3

If you only want to count the apples eaten without tracking the progress you need no recursion and no loop. You can simply calculate the result with linear O(1) code:

int result = apples + apples / (eatenPerRound - 1);
if ((apples % (eatenPerRound - 1)) <= 1) {
    result--;
}
Console.WriteLine($"Total number of {result} apples eaten.");

Answer 4

Here is a running example of how I understood your problem:

using System.IO;
using System;

class Program
{
    static void Main()
    {
        Console.WriteLine(GetNumberOfApplesEaten(100,5));
    }

    public static int GetNumberOfApplesEaten(int X, int Y)
    {
        int result = 0;

        // while we can eat 'Y' apples
        while(X >= Y)
        {
            // we eat & count those apples
            result += Y;
            X -= Y;
            // we add an extra apple
            X++;
        }
        // we eat what's left
        result += X;

        return result;
    }
}

Edit

I changed X > Y to X >= Y so it matches your specs.

Check javascript equivalent:

function getNumberOfApplesEaten(X,Y) {
    var result = 0;

    // while we can eat 'Y' apples
    while(X >= Y) {
        // we eat & count those apples
        result += Y;
        X -= Y;
        // we add an extra apple
        X++;
    }
    // we eat what's left
    result += X;

    return result;
}

console.log(getNumberOfApplesEaten(3,2))

Answer 5

I don't have a C# toolchain at hand, so the example below is in Python Community edits have made the example C#! Magic!

As said in the comments, this is an iterative problem, not a recursive one.

var apples = 100;
var eaten = 0;
var eatPerRound = 5;
var gainPerRound = 1;

while(apples > 0)
{
    apples -= eatPerRound;
    eaten += eatPerRound;
    apples += gainPerRound;
    Console.WriteLine($"Round {round}: {eaten} apples eaten, {apples} left");
}

---

Round 1: 5 apples eaten, 96 left
Round 2: 10 apples eaten, 92 left
Round 3: 15 apples eaten, 88 left
Round 4: 20 apples eaten, 84 left
Round 5: 25 apples eaten, 80 left
Round 6: 30 apples eaten, 76 left
Round 7: 35 apples eaten, 72 left
Round 8: 40 apples eaten, 68 left
Round 9: 45 apples eaten, 64 left
Round 10: 50 apples eaten, 60 left
Round 11: 55 apples eaten, 56 left
Round 12: 60 apples eaten, 52 left
Round 13: 65 apples eaten, 48 left
Round 14: 70 apples eaten, 44 left
Round 15: 75 apples eaten, 40 left
Round 16: 80 apples eaten, 36 left
Round 17: 85 apples eaten, 32 left
Round 18: 90 apples eaten, 28 left
Round 19: 95 apples eaten, 24 left
Round 20: 100 apples eaten, 20 left
Round 21: 105 apples eaten, 16 left
Round 22: 110 apples eaten, 12 left
Round 23: 115 apples eaten, 8 left
Round 24: 120 apples eaten, 4 left
Round 25: 125 apples eaten, 0 left