C Functions & Recursion Exercises with Solutions

Cascading recursion tree and function call frames in C.
Cascading recursion tree and function call frames in C.

Problem Statement

Write a recursive C function that computes the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of an array of K positive integers using the Euclidean algorithm and pointer pass-by-reference.

Real-World Systems Context

In digital signal processing (DSP), timer frequency prescalers, and task scheduling runqueues, computing common timing multiples across multiple hardware timers is a frequent operation. This challenge tests recursive mathematical derivation and modifying multiple return values via pointers.

Requirements:

  1. Implement long long gcd(long long a, long long b) recursively using the Euclidean algorithm: gcd(a, b) = gcd(b, a % b) with base condition b == 0.
  2. Implement long long lcm(long long a, long long b) using (a / gcd(a, b)) * b to prevent premature integer overflow.
  3. Implement void find_array_gcd_lcm(int k, long long arr[], long long *out_gcd, long long *out_lcm) using pointer dereferencing for output parameters.

Complexity & Editorial

Algorithmic Breakdown: Euclidean Recursion & Overflow Prevention

Calculating the GCD and LCM across an arbitrary array of integers requires combining recursive number theory with careful memory management:

  1. The Recursive Euclidean Algorithm:
    The Euclidean algorithm is based on the mathematical principle that the GCD of two numbers also divides their difference. Rather than subtracting repeatedly, the modulo operation computes the remainder in a single step:
    gcd(a, b) = gcd(b, a % b)
    The base case triggers when b == 0, returning a. This converges in logarithmic time O(log(min(a, b))).

  2. Preventing Multiplication Overflow in LCM:
    The mathematical formula for LCM is (a * b) / gcd(a, b). However, multiplying a * b first can cause 64-bit integer overflow even if the final LCM would comfortably fit in a long long.
    By dividing first:
    lcm(a, b) = (a / gcd(a, b)) * b;
    we guarantee that the intermediate quotient remains small, preventing arithmetic overflow.

  3. Pass-by-Reference in C:
    Because C functions cannot return multiple values by value, we pass pointers (long long *out_gcd, long long *out_lcm). Dereferencing them (*out_gcd = current_gcd) directly mutates the caller's stack variables.

Starter Code

#include <stdio.h>

// Recursive Euclidean algorithm
long long gcd(long long a, long long b) {
    // TODO: Base case and recursive call
    return 0;
}

long long lcm(long long a, long long b) {
    // TODO: (a / gcd(a, b)) * b
    return 0;
}

// Function modifying outputs via pointers
void find_array_gcd_lcm(int k, long long arr[], long long *out_gcd, long long *out_lcm) {
    // TODO: Loop through array and accumulate overall GCD and LCM
}

int main(void) {
    int k;
    if (scanf("%d", &k) != 1 || k < 2) return 1;

    long long arr[10];
    for (int i = 0; i < k; i++) {
        scanf("%lld", &arr[i]);
    }

    long long result_gcd = 0;
    long long result_lcm = 0;

    find_array_gcd_lcm(k, arr, &result_gcd, &result_lcm);

    printf("Array GCD: %lld | Array LCM: %lld\n", result_gcd, result_lcm);
    return 0;
}

Frequently Asked Questions

Can this recursive GCD function cause a stack overflow?

No, because the Euclidean algorithm reduces values by at least half every two steps (Lamé's Theorem). The maximum recursion depth rarely exceeds 50 frames even for 64-bit integers.

Why does C not allow returning multiple values like Python or Go?

C is a low-level language designed to map cleanly onto CPU architectures. Hardware return registers (like RAX on x86-64) hold only a single scalar value. Returning multiple values is achieved via pointers or structs.

Related exercises