递归伪代码:打印语句的执行顺序

Question

我不确定下面的代码将打印出什么。谁能尽可能详细地解释一下吗?这是递归吗?

void h ( int n )
   if ( n >=  4 )
      h ( n / 2 )
   end if 
   print n 
end h

调用h(16)执行时输出什么?

Answer 1

为什么不看看程序输出的一个小整数值，比如n == 42 ?下面是伪代码的Python实现:

def h(n):
    if n >= 4:
        h(n/2)
    print(n)

我假设n/2在这里意味着浮点除法，这部分从伪代码中是不清楚的。h(42)将put out:

2.625
5.25
10.5
21.0
42

发生了什么:首先n是42,42 >= 4。因此，调用h(21)。21 >= 4，所以叫h(10.5)。10.5 >= 4，所以叫h(5.25)。5.25 >= 4，所以叫h(2.625)。最后是2.625 < 4，所以不会再调用h。相反，输出2.625。现在h(2.625)完成了，h(5.25)可以继续打印5.25，以此类推，直到h(42)通过打印42完成调用链。因此，总结h(n)的作用:h(n)将连续地将n除以2，直到n < 4，然后以相反的顺序打印这些除法的结果。

您应该能够计算出h(16)现在将打印的内容。