在这个例子中，这个递归是如何工作的？

Question

这就是经典的落蛋问题。我只是不明白这里的递归是如何工作的。它如何到达函数的末尾，每次递归发生时都会返回min+1？

请注意，我对递归的概念理解可能是有缺陷的。

/* Function to get minimum number of trials needed in worst 
case with n eggs and k floors */
int eggDrop(int n, int k) 
{ 
// If there are no floors, then no trials needed. OR if there is 
// one floor, one trial needed. 
if (k == 1 || k == 0) 
    return k; 

// We need k trials for one egg and k floors 
if (n == 1) 
    return k; 

int min = INT_MAX, x, res; 

// Consider all droppings from 1st floor to kth floor and 
// return the minimum of these values plus 1. 
for (x = 1; x <= k; x++) 
{ 
    res = max(eggDrop(n-1, x-1), eggDrop(n, k-x)); 
    if (res < min) 
        min = res; 
} 

return min + 1; 
}

Answer 1

递归有几种基本情况，when n == 1、when k == 0和when k == 1。

每个非基本情况调用都有相当多的递归调用。例如，如果我们想要调用eggDrop(2, 5)，我们将返回类似于

min (
  // **egg breaks**  **egg doesn't break**
  max (eggDrop (1, 0), eggDrop (2, 4) ),
  max (eggDrop (1, 1), eggDrop (2, 3) ),
  max (eggDrop (1, 2), eggDrop (2, 2) ),
  max (eggDrop (1, 3), eggDrop (2, 1) ),
  max (eggDrop (1, 4), eggDrop (2, 0) ),
)

请注意，这些情况中的每一个都会使我们转向其中一个基本情况。在第一列中，我们将n减少了1，在第二列中，我们将k减少了x，其中x是不大于k的正整数。由于每次递归调用都会使我们更接近基本情况，所以我们最终会走出谷底。

(您可以通过以下方式正式证明这一点:在每个递归调用中，n + k严格小于其父调用。这里我就不费心了；凭直觉就足够了。)

这应该解释了递归是如何实际工作的。

但请注意我们进行了多少递归调用：k * (k - 1) / 2。这意味着这个递归版本不太可能是一个性能非常好的解决方案。因此，这个问题通常用动态编程技术来解决。