理解这个递归函数

Question

我是altering/improving这个递归函数。我的意图是添加一个全局 class 变量 nrOfFails 来存储搜索不成功的所有迭代。

我调用函数如下：

{
    ArrayList<Integer> solutions = new ArrayList<>();
    int[] money1= {2,2,2,5,10,10,20}
    int targe1 = 24
    System.out.print(solutions(money1,target1,solutions))
}

 /**
   * Returns the number of ways of creating specified target value as a sum of money starting with c
   * @param money the set of coins
   * @param c Index of the array
   * @param target the amount to give back
   * @return number of ways
   */
  private static int solutions(int[] money, int c, int target, ArrayList<Integer> s)
  {
    assert money!=null : "array should be initialized";
    assert c>=0&&c<=money.length;
    nrOfFails = 0;

    if(target==0)
    {
      showSolution(s);
      return 1;
    }
    if(target<0)
      return 0;
    if(c>=money.length)
      return 0;
    else
    {
      s.add(money[c]);
      int with = solutions(money, c + 1, target - money[c], s);
      s.remove(s.size()-1);
      int without = solutions(money, c + 1, target,s);
      return with + without;
    }
  }

  private static void showSolution(ArrayList<Integer> s)
  {
    System.out.print(s);
  }

我想出了一个'counting'不成功迭代的原始方法，但我想用递归来解决这个问题。

至于原始方案。我试图在任何迭代中检查 money[] 的内容是否有一个不包含目标数量倍数的值，然后我们徒劳地搜索。用一个for，一个计数器来判断有没有公倍数，没有就白找了。

Answer 1

让我们考虑一下您要计算的 "iterations where the search was unsuccessful"。

一个这样的情况是当你传递一个负数 target 给递归调用（这意味着 solutions(money, c + 1, target - money[c], s) 递归调用中的 target - money[c] < 0）。

另一种情况是当您在达到目标总和之前运行超出数组元素时（即当 c >= money.length 时）。

因此，在这两种情况下，您应该增加 nrOfFails 计数器。我将它们统一为一个条件，使代码更短：

static int nrOfFails = 0;
private static int solutions(int[] money, int c, int target, ArrayList<Integer> s)
{
    assert money != null : "array should be initialized";
    assert c >= 0 && c <= money.length;

    if (target == 0) {
        showSolution(s);
        return 1;
    } else if (target < 0 || c >= money.length) {
        nrOfFails++;
        return 0;
    } else {
        s.add(money[c]);
        int with = solutions(money, c + 1, target - money[c], s);
        s.remove(s.size() - 1);
        int without = solutions(money, c + 1, target, s);
        return with + without;
    }
}

您必须在第一次调用 solutions 之前将静态变量重置为 0。

请注意，您在初次调用递归方法时忘记了 c 参数。我在这里添加了它。我还添加了 nrOfFails:

的重置和打印

nrOfFails = 0;
ArrayList<Integer> solutions = new ArrayList<>();
int[] money1= {2,2,2,5,10,10,20};
int target = 24;
System.out.println(solutions(money1,0,target,solutions));
System.out.println ("number of fails = " + nrOfFails);

这会产生以下输出：

[2, 2, 10, 10]
[2, 2, 20]
[2, 2, 10, 10]
[2, 2, 20]
[2, 2, 10, 10]
[2, 2, 20]
6
number of fails = 110

理解这个递归函数

Understanding this recursion function

java

loops

recursion

tail-recursion