CODEWITHSUNDEEP
recursionpseudocode
user3735557
user3735557

Reputation: 47

recursive pseudocode: order of execution of print statements

I am not sure what the following code will print out. Can someone please explain in the best detail possible? Is this recursion?

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

What is printed when the call h (16) is executed?

Upvotes: 0

Views: 108

Answers (1)

timgeb
timgeb

Reputation: 78700

Why not look at the output of the program for a small integer value, say n == 42? Here's a Python implementation of your pseudo-code:

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

I am assuming that n/2 means floating point division here, that part is unclear from your pseudo-code. h(42) will put out:

2.625
5.25
10.5
21.0
42

Here's whats happening: First n is 42, and 42 >= 4. Hence, h(21) is called. 21 >= 4, so h(10.5) is called. 10.5 >= 4, so h(5.25) is called. 5.25 >= 4, so h(2.625) is called. Finally 2.625 < 4, so there's not another call to h. Instead, 2.625 is printed. Now h(2.625) is finished and h(5.25) can continue and print 5.25, and so on, until h(42) finishes the call-chain by printing 42. So to summarize what h(n) does: h(n) will continuously divide n by two until n < 4, then print the results of these divisions in reverse order.

You should be able to work out what h(16) will print now.

Upvotes: 1

Related Questions