帮助创建递归函数C#

调用GetNumber(5,x)应产生与GetNumber5(x)相同的结果:

static void GetNumber(int num, int max) {
    Console.WriteLine(GetNumber(num, max, ""));
}
static int GetNumber(int num, int max, string prefix) {
    if (num < 2) {
        Console.WriteLine(prefix + max);
        return 1;
    }
    else {
        int count = 0;
        for (int i = max; i >= 0; i--)
            count += GetNumber(num - 1, max - i, prefix + i + " ");
        return count;
    }
}

start 小于0:

private static void GetNumberRec(int start)
{
  if(start < 0)
    return;

  // Do stuff

  // Recurse
  GetNumberRec(start-1);
}

private static void GetNumber5(int start)
{
    var count = 0;

    for (var i = 0; i <= start; i++)
    {
        for (var j = 0; j <= i; j++)
        {
            for (var k = 0; k <= j; k++)
            {
                for (var l = 0; l <= k; l++)
                {
                    count++;

                    Console.WriteLine(
                       (start - i) + " " +
                       (i - j) + " " +
                       (j - k) + " " +
                       (k - l) + " " +
                       l);
                }
            }
        }
    }

    Console.WriteLine(count);
}

请确认这是正确的。

递归版本应如下所示:

public static void GetNumber(int start, int depth)
{
    var count = GetNumber(start, depth, new Stack<int>());
    Console.WriteLine(count);
}

private static int GetNumber(int start, int depth, Stack<int> counters)
{
    if (depth == 0)
    {
        Console.WriteLine(FormatCounters(counters));
        return 1;
    }
    else
    {
        var count = 0;
        for (int i = 0; i <= start; i++)
        {
            counters.Push(i);
            count += GetNumber(i, depth - 1, counters);
            counters.Pop();
        }
        return count;
    }
}

FormatCounters 作为练习留给读者;)

我之前提供了一个简单的C#递归函数 here . 最顶端的函数最终拥有每个排列的一个副本,因此它应该很容易适应您的需要。。

我意识到在这一点上每个人都击败了我,但这里有一个愚蠢的Java算法(在语法上非常接近C,你可以试试)。

import java.util.ArrayList;
import java.util.List;

/**
 * The operational complexity of this is pretty poor and I'm sure you'll be able to optimize
 * it, but here's something to get you started at least.
 */
public class Recurse
{   
    /**
     * Base method to set up your recursion and get it started
     * 
     * @param start The total number that digits from all the days will sum up to
     * @param days The number of days to split the "start" value across (e.g. 5 days equals
     * 5 columns of output)
     */
    private static void getNumber(int start,int days)
    {
        //start recursing
        printOrderings(start,days,new ArrayList<Integer>(start));
    }

    /**
     * So this is a pretty dumb recursion.  I stole code from a string permutation algorithm that I wrote awhile back. So the
     * basic idea to begin with was if you had the string "abc", you wanted to print out all the possible permutations of doing that
     * ("abc","acb","bac","bca","cab","cba"). So you could view your problem in a similar fashion...if "start" is equal to "5" and
     * days is equal to "4" then that means you're looking for all the possible permutations of (0,1,2,3,4,5) that fit into 4 columns. You have
     * the extra restriction that when you find a permutation that works, the digits in the permutation must add up to "start" (so for instance
     * [0,0,3,2] is cool, but [0,1,3,3] is not).  You can begin to see why this is a dumb algorithm because it currently just considers all
     * available permutations and keeps the ones that add up to "start". If you want to optimize it more, you could keep a running "sum" of
     * the current contents of the list and either break your loop when it's greater than "start".
     * 
     * Essentially the way you get all the permutations is to have the recursion choose a new digit at each level until you have a full
     * string (or a value for each "day" in your case).  It's just like nesting for loops, but the for loop actually only gets written
     * once because the nesting is done by each subsequent call to the recursive function.
     * 
     * @param start The total number that digits from all the days will sum up to
     * @param days The number of days to split the "start" value across (e.g. 5 days equals
     * 5 columns of output)
     * @param chosen The current permutation at any point in time, may contain between 0 and "days" numbers.
     */
    private static void printOrderings(int start,int days,List<Integer> chosen)
    {
        if(chosen.size() == days)
        {
            int sum = 0;
            for(Integer i : chosen)
            {
                sum += i.intValue();
            }

            if(sum == start)
            {
                System.out.println(chosen.toString());
            }
            return;
        }
        else if(chosen.size() < days)
        {
            for(int i=0; i < start; i++)
            {
                if(chosen.size() >= days)
                {
                    break;
                }

                List<Integer> newChosen = new ArrayList<Integer>(chosen);
                newChosen.add(i);
                printOrderings(start,days,newChosen);
            }
        }
    }

    public static void main(final String[] args)
    {
        //your equivalent of GetNumber4(5)
        getNumber(5,4);

        //your equivalent of GetNumber5(5)
        getNumber(5,5);
    }
}