Recursive GCD

Original: Cmmdc recursiv

O(log n)C++1741 lines2 examples

The idea

Euclid's algorithm written recursively: gcd(a, 0) = a, and gcd(a, b) = gcd(b, a % b). The recursive call is the last operation in the function (tail recursion), so nothing is left to compute on the way back. We also print the number of calls, to see how quickly a remainder of 0 is reached.

Original description (Romanian)

Algoritmul lui Euclid scris recursiv: cmmdc(a, 0) = a, iar cmmdc(a, b) = cmmdc(b, a % b). Autoapelul este ultima operație din funcție (recursivitate „de coadă”), deci nu mai rămâne nimic de calculat la întoarcere. Afișăm și numărul de apeluri, ca să vedem cât de repede se ajunge la rest 0.

Complexity: O(log(min(a, b)))
Grade: Grade 10 (Clasa a X-a)
Chapter: Recursion

Examples

Example 1

Input

48 18

Expected output

6 4

Example 2

Input

7 0

Expected output

7 1

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

cmmdc-recursiv.cpp

/*
 * Titlu: Cmmdc recursiv
 * Clasa: 10
 * Capitol: Recursivitate
 * Descriere: Algoritmul lui Euclid scris recursiv: cmmdc(a, 0) = a, iar
 *            cmmdc(a, b) = cmmdc(b, a % b). Autoapelul este ultima operație din
 *            funcție (recursivitate „de coadă”), deci nu mai rămâne nimic de calculat
 *            la întoarcere. Afișăm și numărul de apeluri, ca să vedem cât de repede
 *            se ajunge la rest 0.
 * Complexitate: O(log(min(a, b)))
 *
 * Exemplu
 * Intrare: 48 18
 * Ieșire: 6 4
 *
 * Exemplu
 * Intrare: 7 0
 * Ieșire: 7 1
 */
#include <iostream>
using namespace std;

int apeluri;

long long cmmdc(long long a, long long b)
{
    apeluri++;
    if (b == 0)
        return a;
    return cmmdc(b, a % b);
}

int main()
{
    long long a, b;
    cin >> a >> b;
    long long d = cmmdc(a, b);
    cout << d << ' ' << apeluri << '\n';
    return 0;
}

Input (stdin)

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.