Complete the code for the following problem in

three programming languages C++, Scheme, and Prolog.

[30 points]

foo(x,y)= { x if y ? 0

y if x ? 0

x+foo(x-1,y-2) if ? y

y+foo(x-2, y-3) if < y

}

Assume that both x and y are originally non-negative integers greater than 0

For example:

foo(5, 6) = 6+ foo(3, 3)

foo(3, 3)= 3 + foo(2, 1)

foo(2, 1)= 2 + foo(1, -1)

foo(1, -1) = 1

Thus, foo(5, 6) = 6 +3 + 2 + 1 = 12

You mustuse recursion and follow the Fantastic Four-Step Abstract approach to solve the problems. You must indicate these steps in the comments in your program.

(Note, a Prolog rule does not return a value. You can use an additional parameter to hold the return value.)

1.1

Solve the problem in C++: Define foo(x, y) function and write a main function to call foo(x, y). [10 points]

1.2

Solve the problem in Scheme: Define a procedure and call the procedure. [10 points]

1.3

Solve the problem in Prolog: Define a rule foo(X, Y, Z), where Z is used for the return

value.You may also use foo(X, Y) and use one of the parameters to hold the return value. [10 points]