Let a and b be positive integers Suppose a function Q is def

Let a and b be positive integers. Suppose a function Q is definded recursively as follows:

Q(a, b) = 0 if a < b

Q(a, b) = Q(a-b, b) + 1, if b <= a

(a) Find the value of Q(17,4)

(b) What does this function do? Find Q(861, 6)

PLEASE SHOW DETAIL SOLUTION.

Solution

Solution (a) The value of Q(17,4) is 4.

Step 1: Q(17,4)

As 4<=17 [b<=a] then second case is true then it calls Q(a-b,b)+1 = Q(13,4) + 1

Step 2: Q(13,4)

As  3<=13 [b<=a] then second case is true then it calls Q(a-b,b)+1 = Q(9,4) + 1

Step 3: Q(9,4)

As 4<=9 [b<=a] then second case is true then it calls Q(a-b,b)+1 = Q(5,4) + 1

Step 4:  Q(5,4)

As 4<=5 [b<=a] then second case is true then it calls Q(a-b,b)+1 = Q(1,4) + 1

Step 5:  Q(1,4)

As 1<4 [a<b] then first case is true Q(a,b)=0

Step 6: As the recursive end in the step 5 then it backtracks as it was called 4 times and every times it add 1 to it so the final solution is \'4\'

(b) This function is a recursive function and is used to find the quotient of the two positive numbers a and b,

The value of Q(861,6) is 143.