c - 在循环内使用时递归如何展开？

Question

需要了解递归在切杆问题中是如何发生的。

这是代码片段:

int cutRod(int price[], int n)
{
   if (n <= 0)
     return 0;
   int max_val = INT_MIN;

   for (int i = 0; i<n; i++)
       max_val = max(max_val, price[i] + cutRod(price, n-i-1));

   return max_val;
}

在 for 循环中使用递归树会是什么样子？

Answer 1

考虑它的递归关系可能会有所帮助。在这种情况下，它有点棘手，因为每次递归调用中输入的大小都不同。在这种情况下，您可以使用:

T(n) = T_1(n-1) + T_2(n-2) + ... T_n(0)

例如 T(5) = T(4) + T(3) + T(2) + T(1) + T(0)

我在这里有点滥用符号(这更符合您用来查找大 Oh 复杂性的方法)。 + 在这种情况下实际上并没有添加任何东西，而是表明这些调用是在调用堆栈的同一级别(相同的递归深度)进行的

虽然从这个关系中画出一棵树应该很容易