English
Menu

Data Structures and Algorithms

A function f(x, y) is defined as “if y is 0, return x; otherwise return f(y, x mod y)”. When f(84, 36) is called, what is the return value, and how many times is f called, including the first call?

  1. AReturns 12; called 3 times
  2. BReturns 12; called 4 times
  3. CReturns 6; called 3 times
Show answer and explanation

Answer: A. Returns 12; called 3 times

f(84, 36) calls f(36, 12) because 84 mod 36 = 12; that calls f(12, 0) because 36 mod 12 = 0; and since y is 0, it returns 12. The calls are f(84, 36), f(36, 12) and f(12, 0), three in total, and this is the Euclidean algorithm for the greatest common divisor. Because the function returns the result of its recursive call directly (tail recursion), a compiler that performs tail call optimization can turn it into a loop, so it does not keep using stack space however deep the recursion goes.

  • A. Correct. f(84, 36) → f(36, 12) → f(12, 0), three calls, returning 12, the greatest common divisor of 84 and 36.
  • B. The recursion ends at f(12, 0), when y becomes 0, so there is no fourth call.
  • C. The greatest common divisor of 84 and 36 is 12 (84 = 12 × 7, 36 = 12 × 3).
Practice this topic Back to topic

Related calculators

Sorting algorithm visualizerWatch 7 sorting algorithms (bubble, selection, insertion, shell, merge, quick and heap) step by step as bar charts, and compare their comparison and write countsDijkstra's algorithm calculatorCompute shortest paths and distances from a list of weighted edges, and follow each step of finalizing vertices in a table and a diagram

Books on Data Structures and Algorithms Ad

As an Amazon Associate I earn from qualifying purchases.

More Data Structures and Algorithms questions

  1. A function fib(n) for Fibonacci numbers is defined recursively as “if n is 1 or less, return n; otherwise return fib(n−1) + fib(n−2)”. When fib(5) is called, how many times is fib called, including the first call?
  2. You pay 8 yen with coins of 1 yen, 4 yen and 6 yen. Which correctly relates the number of coins chosen by a greedy algorithm, which uses as many of the largest coin as possible first, to the minimum number of coins?
  3. A knapsack with capacity 8 is filled with items chosen from four items with (weight, value) of (2, 3), (3, 4), (4, 5) and (5, 6). There is only one of each item and items cannot be split. What is the maximum total value with a total weight of 8 or less?
  4. Which is a characteristic of the Boyer-Moore algorithm for finding a pattern in a string?
  5. A dynamic array, when an element is added while it is full, allocates a new area with twice the capacity and copies all elements into it. If 1,000 elements are added one at a time to an empty array of capacity 1, how many element copies are made in total?