python - 两个相似的递归代码
问题描述
我正在准备面试,但递归让我感到困惑。我对两个相似代码的 o/p 感到困惑
def fun(x):
if(x > 0):
x -= 1
fun(x)
print(x , end=" ")
x -= 1
fun(x)
# Driver code
a = 4
fun(a)
output=0 1 2 0 3 0 1
我很困惑,为什么在上面的代码 4 中,中间值没有像下面的代码一样被推送到堆栈中。
def fun(x):
if(x > 0):
fun(x-1)
print(x , end=" ")
x -= 1
fun(x)
# Driver code
a = 4
fun(a)
output=1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
解决方案
我修改了您的代码以显示确切的执行路径,以便您了解输出发生的原因。
第一个代码的修改版本:
def fun(x, depth=0):
print(" " * depth + f"in fun({x}) (depth {depth})")
print(" " * depth + f"if({x} > 0): (depth {depth})")
if(x > 0):
print(" " * depth + f"x = {x} - 1 = {x - 1} (depth {depth})")
x -= 1
print(" " * depth + f"calling fun({x}) (depth {depth})")
fun(x, depth + 1)
print(" " * depth + f"\"{x} \" printed (depth {depth})************")
print(" " * depth + f"x = {x} - 1 = {x - 1} (depth {depth})")
x -= 1
print(" " * depth + f"calling fun({x}) (depth {depth})")
fun(x, depth + 1)
# Driver code
a = 4
fun(a)
输出:
in fun(4) (depth 0)
if(4 > 0): (depth 0)
x = 4 - 1 = 3 (depth 0)
calling fun(3) (depth 0)
in fun(3) (depth 1)
if(3 > 0): (depth 1)
x = 3 - 1 = 2 (depth 1)
calling fun(2) (depth 1)
in fun(2) (depth 2)
if(2 > 0): (depth 2)
x = 2 - 1 = 1 (depth 2)
calling fun(1) (depth 2)
in fun(1) (depth 3)
if(1 > 0): (depth 3)
x = 1 - 1 = 0 (depth 3)
calling fun(0) (depth 3)
in fun(0) (depth 4)
if(0 > 0): (depth 4)
"0 " printed (depth 3)************
x = 0 - 1 = -1 (depth 3)
calling fun(-1) (depth 3)
in fun(-1) (depth 4)
if(-1 > 0): (depth 4)
"1 " printed (depth 2)************
x = 1 - 1 = 0 (depth 2)
calling fun(0) (depth 2)
in fun(0) (depth 3)
if(0 > 0): (depth 3)
"2 " printed (depth 1)************
x = 2 - 1 = 1 (depth 1)
calling fun(1) (depth 1)
in fun(1) (depth 2)
if(1 > 0): (depth 2)
x = 1 - 1 = 0 (depth 2)
calling fun(0) (depth 2)
in fun(0) (depth 3)
if(0 > 0): (depth 3)
"0 " printed (depth 2)************
x = 0 - 1 = -1 (depth 2)
calling fun(-1) (depth 2)
in fun(-1) (depth 3)
if(-1 > 0): (depth 3)
"3 " printed (depth 0)************
x = 3 - 1 = 2 (depth 0)
calling fun(2) (depth 0)
in fun(2) (depth 1)
if(2 > 0): (depth 1)
x = 2 - 1 = 1 (depth 1)
calling fun(1) (depth 1)
in fun(1) (depth 2)
if(1 > 0): (depth 2)
x = 1 - 1 = 0 (depth 2)
calling fun(0) (depth 2)
in fun(0) (depth 3)
if(0 > 0): (depth 3)
"0 " printed (depth 2)************
x = 0 - 1 = -1 (depth 2)
calling fun(-1) (depth 2)
in fun(-1) (depth 3)
if(-1 > 0): (depth 3)
"1 " printed (depth 1)************
x = 1 - 1 = 0 (depth 1)
calling fun(0) (depth 1)
in fun(0) (depth 2)
if(0 > 0): (depth 2)
第二个代码的修改版本:
def fun(x, depth=0):
print(" " * depth + f"in fun({x}) (depth {depth})")
print(" " * depth + f"if({x} > 0): (depth {depth})")
if(x > 0):
print(" " * depth + f"calling fun({x-1}) (depth {depth})")
fun(x-1, depth + 1)
print(" " * depth + f"\"{x} \" printed (depth {depth})************")
print(" " * depth + f"x = {x} - 1 = {x - 1} (depth {depth})")
x -= 1
print(" " * depth + f"calling fun({x}) (depth {depth})")
fun(x, depth + 1)
# Driver code
a = 4
fun(a)
输出:
in fun(4) (depth 0)
if(4 > 0): (depth 0)
calling fun(3) (depth 0)
in fun(3) (depth 1)
if(3 > 0): (depth 1)
calling fun(2) (depth 1)
in fun(2) (depth 2)
if(2 > 0): (depth 2)
calling fun(1) (depth 2)
in fun(1) (depth 3)
if(1 > 0): (depth 3)
calling fun(0) (depth 3)
in fun(0) (depth 4)
if(0 > 0): (depth 4)
"1 " printed (depth 3)************
x = 1 - 1 = 0 (depth 3)
calling fun(0) (depth 3)
in fun(0) (depth 4)
if(0 > 0): (depth 4)
"2 " printed (depth 2)************
x = 2 - 1 = 1 (depth 2)
calling fun(1) (depth 2)
in fun(1) (depth 3)
if(1 > 0): (depth 3)
calling fun(0) (depth 3)
in fun(0) (depth 4)
if(0 > 0): (depth 4)
"1 " printed (depth 3)************
x = 1 - 1 = 0 (depth 3)
calling fun(0) (depth 3)
in fun(0) (depth 4)
if(0 > 0): (depth 4)
"3 " printed (depth 1)************
x = 3 - 1 = 2 (depth 1)
calling fun(2) (depth 1)
in fun(2) (depth 2)
if(2 > 0): (depth 2)
calling fun(1) (depth 2)
in fun(1) (depth 3)
if(1 > 0): (depth 3)
calling fun(0) (depth 3)
in fun(0) (depth 4)
if(0 > 0): (depth 4)
"1 " printed (depth 3)************
x = 1 - 1 = 0 (depth 3)
calling fun(0) (depth 3)
in fun(0) (depth 4)
if(0 > 0): (depth 4)
"2 " printed (depth 2)************
x = 2 - 1 = 1 (depth 2)
calling fun(1) (depth 2)
in fun(1) (depth 3)
if(1 > 0): (depth 3)
calling fun(0) (depth 3)
in fun(0) (depth 4)
if(0 > 0): (depth 4)
"1 " printed (depth 3)************
x = 1 - 1 = 0 (depth 3)
calling fun(0) (depth 3)
in fun(0) (depth 4)
if(0 > 0): (depth 4)
"4 " printed (depth 0)************
x = 4 - 1 = 3 (depth 0)
calling fun(3) (depth 0)
in fun(3) (depth 1)
if(3 > 0): (depth 1)
calling fun(2) (depth 1)
in fun(2) (depth 2)
if(2 > 0): (depth 2)
calling fun(1) (depth 2)
in fun(1) (depth 3)
if(1 > 0): (depth 3)
calling fun(0) (depth 3)
in fun(0) (depth 4)
if(0 > 0): (depth 4)
"1 " printed (depth 3)************
x = 1 - 1 = 0 (depth 3)
calling fun(0) (depth 3)
in fun(0) (depth 4)
if(0 > 0): (depth 4)
"2 " printed (depth 2)************
x = 2 - 1 = 1 (depth 2)
calling fun(1) (depth 2)
in fun(1) (depth 3)
if(1 > 0): (depth 3)
calling fun(0) (depth 3)
in fun(0) (depth 4)
if(0 > 0): (depth 4)
"1 " printed (depth 3)************
x = 1 - 1 = 0 (depth 3)
calling fun(0) (depth 3)
in fun(0) (depth 4)
if(0 > 0): (depth 4)
"3 " printed (depth 1)************
x = 3 - 1 = 2 (depth 1)
calling fun(2) (depth 1)
in fun(2) (depth 2)
if(2 > 0): (depth 2)
calling fun(1) (depth 2)
in fun(1) (depth 3)
if(1 > 0): (depth 3)
calling fun(0) (depth 3)
in fun(0) (depth 4)
if(0 > 0): (depth 4)
"1 " printed (depth 3)************
x = 1 - 1 = 0 (depth 3)
calling fun(0) (depth 3)
in fun(0) (depth 4)
if(0 > 0): (depth 4)
"2 " printed (depth 2)************
x = 2 - 1 = 1 (depth 2)
calling fun(1) (depth 2)
in fun(1) (depth 3)
if(1 > 0): (depth 3)
calling fun(0) (depth 3)
in fun(0) (depth 4)
if(0 > 0): (depth 4)
"1 " printed (depth 3)************
x = 1 - 1 = 0 (depth 3)
calling fun(0) (depth 3)
in fun(0) (depth 4)
if(0 > 0): (depth 4)
推荐阅读
- php - 如何查看数组的所有成员?
- java - Spring Boot 为不安全的端点抛出 NotificationBroadcasterSupport::sendNotification NullPointerException
- azure-functions - Azure 函数(队列触发器),Web 应用共享数据类型最佳实践
- python - Argparse 在 CentOS 7 上无法正确解析参数
- authentication - Cakephp3 Tiny Auth 允许 Auth 失败
- flutter - 在 Yocto 上颤抖?
- apache-spark - 加入 Spark 返回重复的隐式数据类型不匹配
- postgresql - 基于同一张表刷新多个物化视图的触发器
- firebase - 可以像这样将 Auth0 集成到 Firebase 吗?
- python - 如何将具有键值对的列表转换为字典