algorithm - a 的 b 次方 - 递归算法

Question

根据代码中使用的乘法运算，我很难理解以下递归算法。

int power(int a, int b) {
    if (b < 0) {
        return 0;
    } else if (b == 0) {
        return 1;
    } else {           
        return a * power(a, b - 1);
    }
}

对于输入 (3,7)，结果将是 2187。总共进行了 6 次递归调用:

Initial values - 3,7
First recursive call(3,6)
Second recursive call(3,5)
Third recursive call(3,4)
Fourth recursive call(3,3)
Fifth recursive call(3,2)
Sixth recursive call(3,1)

给定以下公式:

a * power(a, b - 1)

每次递归调用是否将 a 和 b 的值相乘？这没有意义，因为最后会返回 81。我试图了解每个递归调用的乘法运算中的因数和乘积。

Answer 1

您必须记住，a 在每一步都乘以递归函数调用的结果。你可能会这样看:

power(3,7)
= 3 * power(3,6)
= 3 * 3 * power(3,5)
= 3 * 3 * 3 * power(3,4)
= 3 * 3 * 3 * 3 * power(3,3)
= 3 * 3 * 3 * 3 * 3 * power(3,2)
= 3 * 3 * 3 * 3 * 3 * 3 * power(3,1)
= 3 * 3 * 3 * 3 * 3 * 3 * 3 * power(3,0)
= 3 * 3 * 3 * 3 * 3 * 3 * 3 * 1 // by definition when b = 0

在每个步骤中，我们都将对 power(a,b) 的调用替换为 a * power(a,b-1)，如函数定义的那样，直到我们到达 power(3,0)。这有助于弄清楚发生了什么吗？