跟踪简单的递归函数

Question

我越来越接近揭穿这个递归的谜团,只有一件事我无法在这行代码中追踪,这就是最后的返回值,243如果我调用rec()它传递值5.这应该是跟踪:

n: 4 *3: 12
n: 3 *3: 9
n: 2 *3: 6
n: 1 *3: 3
n: 0 *3: 0
n: 1 *3: 3

result: 243

正确？它是如何得到243的结果的？

int rec(int n)
{
if (n == 0)
    return 1;


return 3 * rec(n-1);
}

Answer 1

你的函数计算:3 ^ n.

数字3乘以n-1个呼叫的结果.

f(n) = 3*f(n-1) ;

f(0) = 1;

f(1) = 3*f(0) = 3*1 = 3;

f(2) = 3*f(1) = 3*3 = 9;

f(3) = 3*f(2) = 3*3*f(1) = 3*3*3 = 27

...

f(5) = 3*3*3*3*3 = 243