使用递归实现买汽水（华为面试题）

￡神魔★判官ぃ 2022-06-11 03:29 188阅读 0赞

今天老范问了我一个问题  
**问题：**  
一个人买汽水，一块钱一瓶汽水，三个瓶盖可以换一瓶汽水，两个空瓶可以换一瓶汽水  
问20块钱可以买多少汽水？  
注意：使用递归

这一题乍一看，哎哟，这么简单，能买几瓶？恩。。  
五瓶！  
为啥啊？

多了我喝不完啊！

老范说，喝不完关你屁事，又不是给你喝

哦哦哦，那没事儿了，我想想。  
在知道自己的人生安全得到了保障之后，我冷静下来仔细思考了如何用递归实现这个问题

**首先想了想什么是递归**

1.  方法内调用自己的方法的现象称为递归调用
2.  递归现象允许程序执行到某个阶段时整体调用重新来过

**以及递归的注意事项：**

1.  方法内部调用自己的方法不能100%成立，否则就是死循环
2.  递归层数尽量少，因为会消耗内存，运行效率低

不能100%成立也就是说，要有终止条件，达成某个条件，就要跳出递归调用

瓶盖和空瓶子换饮料，这是一个怎么样的过程？了解了这个过程，才能分析出这中间哪些变量在发生变化，转换，以及变化到哪个程度，就不满足继续递归的条件了，也就是满足终止条件了。

![1块钱和2块钱的置换过程][1_2]  
(这是用processon画的[https://www.processon.com/][https_www.processon.com]很好用）  
(推荐一波，processon速打钱来！！！！！)  
drink表示购买和置换的饮料  
cup表示瓶盖  
bottle表示空瓶子  
首先分析每一个成员变量，

*  1drink=1cup+1bottle;
 *  3cup=1drink;
 *  2bottle=1drink;

\*\*所以置换的过程就是cup-3，drink+1 或者bottle-2，drink+1的过程。  
所以递归调用的条件就是每一轮置换后，cup>=3||bottle>=2, &&drinks<1也就是跳出递归的条件是：每一轮置换后cup<3&&bottle<2 &&drinks<1\*\*

因为在这个过程中，三个元素drink， cup， bottle都有连续的变化，所以递归调用时要将三个参数都传就去。  
定义方法体  
\`public static int Soda(int drink, int cup, int bottle)\{

\}  
\`  
除了第一轮之外，每一轮的drink=cup/3+bottle/2, cup=cup%3, bottle=bottle%2  
所以我本来是这么写的（错的）：

public static int Soda(int drinks,int caps,int bottles){
    
            if(caps<3&&bottles<2&&drinks<1){
                return drinks;
            }else{
                caps+=drinks;bottles+=drinks;
                drinks=caps/3+bottles/2;
                caps%=3;  bottles%=2;
                return Soda(drinks,caps,bottles)+drinks;
            }
        }

得出来是93，我惊呆了，拿给老范，老范说，不不不还有更多，应该是113。

113，那就是说，我缺少20个，正好是第一轮拿钱买的20个。我分析了一下，发现这个代码在第一次递归过程中，return Soda(drinks,caps,bottles)+drinks 这后面跟的drinks已经被第二次置换的drinks替换掉了，导致少了第一次花20块大洋买的drinks。

所以得调整顺序  
将drinks=caps/3+bottles/2的过程放在return内部  
return Soda(caps/3+bottles/2,caps,bottles)+drinks;  
然后崩了，因为caps%=3；bottles%=2已经发生了，所以caps/3+bottles/2已经小于1了，直接满足了终止条件跳出了循环

将这两句调换顺序并放在if前，这样在每次递归时，首先将caps和bottles置换掉，之后再加上就不会影响drinks的置换数量。

1.  caps%=3; bottles%=2;
2.  caps+=drinks;bottles+=drinks;

然后我还发现，终止条件caps<3&&bottles<2&&drinks<1有点啰嗦，因为caps+=drinks;bottles+=drinks;只要drinks<1,就表示caps和drinks肯定满足终止条件。

最终代码：

public static int Soda(int drinks,int caps,int bottles){
            caps%=3;  bottles%=2;
            caps+=drinks;  bottles+=drinks;
            if(caps<3&&bottles<2){
                return drinks;
            }
            else{
                return Soda(caps/3+bottles/2,caps,bottles)+drinks;
            }
        }

得出113瓶。。。。  
久久不能释怀，感觉错过了一个亿 v\_v

[1_2]: /images/20220611/0752865b04b24b149c877dc0f8855a98.png
[https_www.processon.com]: https://www.processon.com/