> For the complete documentation index, see [llms.txt](https://mm.ricky.moe/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mm.ricky.moe/algorithm/algorithm-and-data-structure/di-gui/di-gui-wen-ti.md).

# 递归问题

假设你有一个3升的容器和一个5升的容器（以及充足的水源），如何精确地取出4升水来？

（为了下文叙述的方便，我们不妨把3升的容器和5升的容器分别记做容器A和容器B）。这里提供一种解法：

将A装满（3升），全部倒入B 再次将A装满（3升），用A中的水将B装满，此时A有1升，B有5升 B中的水全部倒出，将A中的1升水倒入B，此时A没有水，B有一升 再次将A装满（3升），将A中的水全部倒入B，此时B中恰有4升的水 

这样的问题存在一个万能的解法吗？答案是肯定的。注意到，用3升的容器和5升的容器量出4升的水，这一看似复杂的步骤可以简单地概括为：不断地将整杯整杯的A往B里倒，期间只要B被装满就把B倒空。