[已解决]递归返回问题

zyj1214

def power(x, y):
    if y:
        return x * power(x, y-1)
    else:
        return 1
   
print(power(2, 3))

return x * power(x, y-1)这句我应该怎么理解？

最佳答案

月排行榜 / 总排行榜

Twilight6

2020-11-18 21:14:53

语言不好叙述，直接举例子吧：

假设 x = 2 , y = 3

调用 power(x, y) 将 x ，y代入函数 ：

power(2, 3) --> if 3 --> True --> return 2 * power(2, 3-1)

而 power(2, 3-1)  开始第一次递归：

power(2, 2)  --> if 2 --> True --> return 2 * power(2 , 2-1)

而 power(2, 2-1)  开始第二次递归：

power(2, 1)  --> if 1 --> True --> return 2 * power(2 , 1-1)

而 power(2, 1-1)  开始第三次递归：

power(2, 0)  --> if 0 --> False --> else -->  return 1

递归进入，依次返回：2 * 2 * 2 * 1

即 power(2, 3)  函数 return 2 * 2 * 2 * 1

跳转到最佳答案楼层

昨非

就相当于

1. a=x * power(x, y-1)
   
2. return a

复制代码

在返回的同时递归调用自己

昨非

执行：2的3次方->return 2*【执行：2的3-1次方】
执行：2的3-1次方->return 2*【执行：2的3-1-1次方】
执行：2的3-1-1次方->return 2*【执行：2的0次方】
执行：2的0次方->return 1     到这里结束，下面是一层层返回的过程

第一次返回：1*2
第二次返回：1*2*2
最后一次返回：1*2*2*2
返回结果就是2的3次方

zyj1214

能写一下详细的运算步骤吗？

昨非

zyj1214 发表于 2020-11-18 21:13
能写一下详细的运算步骤吗？

看二楼

Twilight6

语言不好叙述，直接举例子吧：

假设 x = 2 , y = 3

调用 power(x, y) 将 x ，y代入函数 ：

power(2, 3) --> if 3 --> True --> return 2 * power(2, 3-1)

而 power(2, 3-1)  开始第一次递归：

power(2, 2)  --> if 2 --> True --> return 2 * power(2 , 2-1)

而 power(2, 2-1)  开始第二次递归：

power(2, 1)  --> if 1 --> True --> return 2 * power(2 , 1-1)

而 power(2, 1-1)  开始第三次递归：

power(2, 0)  --> if 0 --> False --> else -->  return 1

递归进入，依次返回：2 * 2 * 2 * 1

即 power(2, 3)  函数 return 2 * 2 * 2 * 1

zyj1214

我是不是该这样理解：
a=x * power(x, y-1)
power(2,3)传入 power(x, y-1)
等于2× power(2, 3-1)  #power(2, 3-1)在传入 power(x, y-1)  y=2
等于2×（2× power(2, 2-1)）#power(2, 2-1)在传入 power(x, y-1)  y=1
等于2×（2×（2*power(2,1-1)））#power(2, 1-1)在传入 power(x, y-1)  y=0

Twilight6

zyj1214 发表于 2020-11-18 21:25
我是不是该这样理解：
a=x * power(x, y-1)
power(2,3)传入 power(x, y-1)

是的，正解

昨非

zyj1214 发表于 2020-11-18 21:25
我是不是该这样理解：
a=x * power(x, y-1)
power(2,3)传入 power(x, y-1)

差不多，也就是每层递归调用第二个参数逐渐从3减到0
返回的依次是1，2*1，2*2*1，2*2*2*1，也就是8（结果）