递归陷阱——有27个人要喝水,每三个空瓶子可以换一瓶水,问需要买多少瓶水

时间:2021-09-12 03:53:54

 

有27个人要喝水,每三个空瓶子可以换一瓶水,问需要买多少瓶水?


完成这道题目时使用了递归,发现怎么也不对,后面找到错误,记录下来。


错误版本

public class buyWater {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		for (int i = 5; i < 27; i++) {
			int out = count(i, i);
			System.out.println("买 " + i + " 瓶,可以得到 " + out + " 瓶");
			if (out >= 27) {
				System.out.println("需要买水:" + i + " 瓶");
				return;
			}
		}
	}

	public static int count(int num, int out) {
		int a = num / 3;
		out += a;
		int b = num - 3 * a;
		while((a+b)>=3) out = count(a+b,out);
		return out;

	}
}
执行结果:
<span style="white-space:pre">	</span>没有打印输出,调试发现,程序一直在while循环中,out不断增加。
分析:
<span style="white-space:pre">	</span>当i=5,执行count,a=1,b=2,满足while循环,调用count()。执行下一级count(),a=1,b=0,不满足while条件,return。回到上一级count,a=1,b=2,a、b值没变,
这就是问题所在了。所以,一直在while循环。
本质在于形参和实参。进入count后,看似仍然使用的a和b,实际上不同的变量,生命周期到本级count执行完(即return)就结束,也不会影响外一级的参数值,所以永远满足while循环。


解决方案:

<span style="font-size:12px;">//		while((a+b)>=3) out = count(a+b,out);
		if(a+b>=3) out=count(a+b, out);</span>
使用if判断,下一届count返回时,尽管a、b值没变,但是if语句不会回去再执行一次。

注意:必须使用

<span style="font-size:12px;"><span style="white-space:pre">		</span>out = count(a+b,out);</span>
<span style="font-size:12px;"><span style="white-space:pre">	</span>不然只</span><span style="font-size: 12px; font-family: Arial, Helvetica, sans-serif;">count(a+b,out);仍然出现out就等于这一级count执行的结果,因为下一级的out只是个形参,不会改变out的值。</span>