Consider the following function F2 Define F2XY IF Y 0 RETURN

Consider the following function F2:

Define F2(X,Y)

IF Y= 0 RETURN 0

ELSE IF X = 0 RETURN (2 * Y)

ELSE IF Y = 1 RETURN 2

ELSE RETURN F2((X-1), F2(X, Y-1))

In prose: if the value of Y (the second argument) is 0, return 0. Otherwise, if the value of

the first argument (namely X) is 0, return 2 times the value of Y. Otherwise, if the value

of Y is 1, return 2. Otherwise, call this function F2 on two values: the first is X-

1, and the second is the result of calling F2 on X and (Y-1).What is the value of F2(3,3)?

Solution

=========================================================

------------
Answer:
------------

   F2(3,3) = 65536

--------------------
Explanation:
--------------------

   Since the given function is a recursive call, Internally it calls for multiple times till it resolved the expression.
  
Below is the trace for the same.

   x =3 y = 3
  
       F2(2,F2(3, 2))
       x =3 y = 2
          
           F2(2,F2(3, 1))
           x =2 y = 2
                  
               F2(1,F2(2, 1))
               x =1 y = 2
          
                   F2(0,F2(1, 1))
                   RETURN 4
                  
           x =2 y = 4
                  
           F2(1,F2(2, 3))
           x =2 y = 3
      
               F2(1,F2(2, 2))
               x =2 y = 2
      
                   F2(1,F2(2, 1))  
                   x =1 y = 2
      
                   F2(0,F2(1, 1))
                   RETURN 4
                  
               x =1 y = 4
      
               F2(0,F2(1, 3))
               x =1 y = 3
      
                   F2(0,F2(1, 2))
                   x =1 y = 2

                   F2(0,F2(1, 1))
                   RETURN 4      
                  
                   x =1 y = 16

                               F2(0,F2(1, 15))
                               x =1 y = 15

                               F2(0,F2(1, 14))
                               x =1 y = 14

                               F2(0,F2(1, 13))
                               x =1 y = 13

                               F2(0,F2(1, 12))
                               x =1 y = 12

                               F2(0,F2(1, 11))
                               x =1 y = 11

                               F2(0,F2(1, 10))
                               x =1 y = 10

                               F2(0,F2(1, 9))
                               x =1 y = 9

                               F2(0,F2(1, 8))
                               x =1 y = 8

                               F2(0,F2(1, 7))
                               x =1 y = 7

                               F2(0,F2(1, 6))
                               x =1 y = 6

                               F2(0,F2(1, 5))
                               x =1 y = 5

                               F2(0,F2(1, 4))
                               x =1 y = 4

                               F2(0,F2(1, 3))
                               x =1 y = 3

                               F2(0,F2(1, 2))
                               x =1 y = 2

                               F2(0,F2(1, 1))
                              
  
   All iternal sub function returned in stack format and result to pop out to compute final expression.
   RESULT = 4
   RESULT = 8
   RESULT = 16
   RESULT = 32
   RESULT = 64
   RESULT = 128
   RESULT = 256
   RESULT = 512
   RESULT = 1024
   RESULT = 2048
   RESULT = 4096
   RESULT = 8192
   RESULT = 16384
   RESULT = 32768
   RESULT = 65536
   RESULT = 65536
   RESULT = 65536

Final value of F(3,3) = 65536
=========================================================