-1

ちょうどウォーミングアップをしていて、これに出くわしました：

http://codingbat.com/prob/p145416

3 つのメソッドの違いは、再帰呼び出しで start パラメーターを追加する方法です。

最初にリストされた2番目の関数で解決しましたが、悪名高いstackoverflowエラーが発生しました。最初のものでは、stackoverflow エラーは発生しません。このサイトに何か問題がありますか、それとも 1 と 2 の違い、つまり Java 言語の微妙な部分がありますか?

public boolean groupSum(int start, int[] nums, int target) {
    if (start >= nums.length) 
        return (target == 0);

    return groupSum(start+1, nums, target - nums[start]) || groupSum(start+1,      
       nums, target);
}

------------ これらはスタック オーバー フロー エラーを引き起こします --------------

public boolean groupSum(int start, int[] nums, int target) {
    if (start >= nums.length) 
        return (target == 0);

    return groupSum(start++, nums, target - nums[start]) || groupSum(start++,      
       nums, target);
}

public boolean groupSum(int start, int[] nums, int target) {
    if (start >= nums.length) 
        return (target == 0);

    return groupSum(++start, nums, target - nums[start]) || groupSum(++start,      
       nums, target);
}
4

2 に答える 2

4

This is a notoriously subtle bug. Take a look at this recursive call:

groupSum(start++, nums, target - nums[start])

Notice that you are passing start++ as the first parameter. This uses the postfix ++ operator, which does the following:

  • Increment start, then
  • Return the value that start used to have.

In other words, this will update the local copy of start to be start + 1, then pass the old value of start into the recursive call. This means that start never changes from call to call, so the base case never triggers, hence the stack overflow. You can confirm this by putting a System.out.println statement at the top of your function.

There may be other issues here, but I suspect this is your culprit.

Hope this helps!

于 2013-05-31T05:55:26.090 に答える
1

++start (known as pre-increment) evaluates to start+1. start++ (known as post-increment, as in the increment is done AFTER evaluation) evaluates to start. Both of them set the value in the variable to start+1 as a side-effect of evaluation. So, when you do start++ you pass start to the next call of the method, which passes start to the next call of the method... you never reach the base case and you recurse infinitely.

于 2013-05-31T05:55:06.173 に答える