Question

Determine the output of the following pseudo-code. Also, explain how did you get this output.

fun(int n){
   if (n==1) then return;
   println(n);
   if (n%2=0) then
     fun(n/2);
   else
     fun(3*n + 1);
}
Main(){
  fun(14);
}

Answer 1

In writing pseudocode you have a syntax error at line 4 "if(n%2=0) then".

I am assuming the line is "if(n%2==0) then".

Output of the code:

14
7
22
11
34
17
52
26
13
40
20
10
5
16
8
4
2

Now let's check how we got the output:

Note: There are two recursive calls in function one if n is even (fun(n/2)) and one if n is not even (f(n*3+1)). Recursion terminating condition is if n is 1.

Initially function is called at value 14:

fun(14): according to the function definiton if n == 4 control should be returned from the function, but 14 is not equals to 1 so this condition fails.

Now function is printing n in new line (assuming println is printing in new line), So 14 will be printed to the output screen.

Now function is cheking if n is even or odd, 14 is even so fun(14/2) (fun(7)) is called.

Similarly:

fun(7):

prints 7 and calls f(3*7+1) is called which is fun(22). (because 7 is odd in function definiton on odd condition f(n*3+1) is called)

fun(22):

  prints 22 and calls fun(22/2) => fun(11)

Similarly,

fun(11): prints 11, calls fun(11*3+1) => fun(34)

fun(34): prints 34, calls fun(34/2) => fun(17)

fun(17): prints 17, calls fun(17*3+1) => fun(52)

fun(52): prints 52, calls fun(52/2) => fun(26)

fun(26): prints 26, calls fun(26/2) => fun(13)

fun(13): prints 13, calls fun(13*3+1) => fun(40)

fun(40): prints 40, calls fun(40/2) => fun(20)

fun(20): prints 20, calls fun(20/2) => fun(10)

fun(10): prints 10, calls fun(10/2) => fun(5)

fun(5): prints 5, calls fun(5*3+1) => fun(16)

fun(16): prints 16, calls fun(16/2) => fun(8)

fun(8): prints 4, calls fun(4/2) => fun(2)

fun(2): prints 2, calls fun(2/2) => fun(1)

  fun(1): Here control is returned from the function.