What is Recursive HCF and LCM in C- Embedded C Programming Course Online

🚀 Learn BLE on Linux (BlueZ) – Programming Part 1

Hands-on Bluetooth Low Energy course. Special price: ₹399

Enroll Now on Udemy →
💬 Need help or career guidance? Ask us!Contact Us →

Recursive HCF and LCM in C

Free C tutorial: find the highest common factor and least common multiple with recursion, Euclid’s algorithm and embedded-safe code.

Recursive HCF and LCM in C is the point where recursion finally pays off, because Euclid’s algorithm shrinks the problem so quickly that a handful of calls solves even large inputs. In this lecture of our free C programming course you will write the highest common factor and least common multiple of two numbers with recursive functions, compare a slow method with a fast one using real call counts, and see why the same arithmetic decides task schedules in embedded C programming. All code is original, compiled with GCC and its output is shown exactly as it ran.

What You Will Learn

  • What HCF (also called GCD) and LCM mean and how they relate to prime factors
  • How to write recursive HCF in C using subtraction and using the remainder operator
  • How to count recursive calls and see why Euclid with remainder is far faster
  • How to compute LCM from HCF without overflow, and by walking multiples recursively
  • Why every branch of a recursive function must return a value
  • Where HCF and LCM appear in scheduling, timers and C programming for embedded systems

Prerequisites

  • The prime factorization lectures just before this one
  • Recursion with a base case and a progress step
  • Fixed-width types from stdint.h
  • Passing state through function parameters instead of global variables

HCF and LCM Explained

The highest common factor of two numbers is the largest number that divides both exactly. The least common multiple is the smallest positive number that both divide exactly. They are linked to the prime factors you computed earlier: the HCF takes the primes the two numbers share, and the LCM takes every prime at its highest count.

HCF and LCM of 56 and 98 from their prime factors
562227
98277
HCF = shared primes2 × 7 = 14
LCM = highest count of each prime2 × 2 × 2 × 7 × 7 = 392

Useful identity

HCF(a, b) × LCM(a, b) = a × b. Once you have a fast HCF, the LCM costs one division and one multiplication. Check: 14 × 392 = 5488 = 56 × 98.

Recursive HCF in C: Subtraction Method

Euclid’s insight is that the common divisors of a and b are the same as the common divisors of the smaller number and the difference. So we can replace the larger number by the difference and repeat. When both numbers become equal, that value is the HCF. This gives a very natural recursive function.

/* Euclid with repeated subtraction, every branch returns */
static uint32_t ep_hcf_sub(uint32_t a, uint32_t b)
{
    ep_calls++;
    if (a == b) {
        return a;
    }
    if (a < b) {
        return ep_hcf_sub(a, b - a);
    }
    return ep_hcf_sub(a - b, b);
}

The base case is a == b. The step always shrinks one of the numbers, so the recursion must end. The counter ep_calls is a global used only to measure how many calls were made.

Subtraction method on 56 and 98
(56, 98)56 < 98→ (56, 42)
(56, 42)56 > 42→ (14, 42)
(14, 42)14 < 42→ (14, 28)
(14, 28)14 < 28→ (14, 14)
(14, 14)equal : return 14

The weakness of subtraction

If one number is much larger than the other, the subtraction method removes the smaller number one step at a time. For 5000 and 1 it makes exactly 5000 calls. With 1,000,000 and 1 the unoptimized program needs a million stack frames and crashed with a segmentation fault in our test. The same program compiled with -O2 printed the correct answer 1, because GCC converted the tail calls into a loop. That difference is a warning: code whose correctness depends on the optimization level is not safe firmware.

Recursive HCF in C: Remainder Method

Repeated subtraction of b from a ends with the remainder of a divided by b, so we can jump there directly using the % operator. This is the version Euclid’s algorithm is known for, and it needs far fewer calls.

/* Euclid with the remainder operator */
static uint32_t ep_hcf(uint32_t a, uint32_t b)
{
    ep_calls++;
    return (b == 0U) ? a : ep_hcf(b, a % b);
}
Remainder method on 56 and 98
ep_hcf(56, 98)b is not 0→ ep_hcf(98, 56 % 98 = 56)
ep_hcf(98, 56)b is not 0→ ep_hcf(56, 98 % 56 = 42)
ep_hcf(56, 42)b is not 0→ ep_hcf(42, 56 % 42 = 14)
ep_hcf(42, 14)b is not 0→ ep_hcf(14, 42 % 14 = 0)
ep_hcf(14, 0)b is 0 : return 14

Notice that the first call swapped the arguments automatically: when a is smaller than b, a % b is just a, so the next call has them in the right order. You never need a separate swap step. If either input is zero the function still behaves correctly: the HCF of any number and 0 is that number.

Recursive LCM in C

Method 1: use the identity

/* LCM through the HCF identity, divide first to dodge overflow */
static uint64_t ep_lcm(uint32_t a, uint32_t b)
{
    if (a == 0U || b == 0U) {
        return 0U;
    }
    return (uint64_t)(a / ep_hcf(a, b)) * b;
}

Two details matter. First, we divide a by the HCF before multiplying by b. Multiplying first would create the large product a times b, which can overflow even when the final LCM fits. Second, the result is 64 bits wide, because the LCM of two 32-bit numbers can need up to 64 bits. We define the LCM with zero as zero, a common convention that also prevents a division by zero.

Method 2: walk the multiples recursively

A second way follows the definition directly. Keep one running multiple of each number, always advance the smaller one, and stop when the two are equal. The recursion carries both multiples as parameters, so no global variables are needed.

/* LCM by walking multiples, state passed as parameters (no globals) */
static uint64_t ep_lcm_walk(uint32_t a, uint32_t b, uint64_t ma, uint64_t mb)
{
    ep_calls++;
    if (ma == mb) {
        return ma;
    }
    if (ma < mb) {
        return ep_lcm_walk(a, b, ma + a, mb);
    }
    return ep_lcm_walk(a, b, ma, mb + b);
}

You start it with ep_lcm_walk(a, b, a, b). Passing the multiples as parameters is important: keeping them in shared global variables would make the function impossible to use from two tasks at once, and a second call would start with stale values.

Walking multiples of 6 and 4
(6, 4)4 is smaller→ advance to 8
(6, 8)6 is smaller→ advance to 12
(12, 8)8 is smaller→ advance to 12
(12, 12)equal : LCM is 12

Complete Program and Measured Results

The test program applies all four functions to a set of pairs and prints how many calls each method used. Together with the functions above you need these includes, the counter and the main() below.

#include <stdio.h>
#include <stdint.h>

static unsigned ep_calls;

/* ep_hcf, ep_hcf_sub, ep_lcm and ep_lcm_walk go here */

int main(void)
{
    uint32_t pairs[][2] = { {56, 98}, {17, 5}, {48, 18}, {5000, 1}, {0, 9} };

    for (unsigned i = 0; i < sizeof pairs / sizeof pairs[0]; i++) {
        uint32_t a = pairs[i][0], b = pairs[i][1];

        ep_calls = 0;
        uint32_t h = ep_hcf(a, b);
        unsigned c_mod = ep_calls;

        printf("a=%u b=%u  hcf=%u (mod calls=%u)", a, b, h, c_mod);

        if (a != 0U && b != 0U) {
            ep_calls = 0;
            uint32_t h2 = ep_hcf_sub(a, b);
            printf("  sub hcf=%u (sub calls=%u)", h2, ep_calls);
        }
        printf("  lcm=%llu", (unsigned long long)ep_lcm(a, b));

        if (a != 0U && b != 0U && a < 100U && b < 100U) {
            ep_calls = 0;
            unsigned long long w = (unsigned long long)ep_lcm_walk(a, b, a, b);
            printf("  walk lcm=%llu (walk calls=%u)", w, ep_calls);
        }
        printf("\n");
    }
    return 0;
}
$ gcc -std=c99 -Wall -Wextra -O0 -o ep_hcf_lcm ep_hcf_lcm.c
$ ./ep_hcf_lcm
a=56 b=98  hcf=14 (mod calls=5)  sub hcf=14 (sub calls=5)  lcm=392  walk lcm=392 (walk calls=10)
a=17 b=5  hcf=1 (mod calls=4)  sub hcf=1 (sub calls=7)  lcm=85  walk lcm=85 (walk calls=21)
a=48 b=18  hcf=6 (mod calls=4)  sub hcf=6 (sub calls=5)  lcm=144  walk lcm=144 (walk calls=10)
a=5000 b=1  hcf=1 (mod calls=2)  sub hcf=1 (sub calls=5000)  lcm=5000
a=0 b=9  hcf=9 (mod calls=2)  lcm=0
PairHCFLCMRemainder callsSubtraction calls
56, 981439255
17, 518547
48, 18614445
5000, 11500025000
0, 9902not used

Comparing the Methods

The remainder method uses a handful of calls whatever the size of the numbers. In general the number of steps grows with the number of digits, not with the value; the worst case for 32-bit inputs is consecutive Fibonacci numbers and stays under 50 calls. The subtraction method can need as many calls as the larger number divided by the smaller. The walking method for LCM needs about LCM/a + LCM/b – 1 calls: for 17 and 5 that is 5 + 17 – 1 = 21, which matches the measured count.

MethodCalls neededStack depthUse it for
HCF by subtractionUp to larger / smallerSame as callsTeaching the idea
HCF by remainderUnder 50 for 32-bit valuesSmall and boundedReal code
LCM through HCFHCF calls plus one divisionSmall and boundedReal code
LCM by walkingAbout LCM/a + LCM/b – 1Same as callsTeaching the definition

This is the first recursive function in the chapter that is acceptable in embedded code: the depth of the remainder method has a provable small upper bound, which is exactly the condition we asked for in the previous lecture.

Real-World Uses in Embedded Systems

  • Scheduler hyperperiod: tasks with periods of 10 ms and 15 ms repeat their combined pattern every LCM = 30 ms. Real-time analysis uses the LCM of all periods.
  • Base tick selection: the HCF of all task periods is the largest tick that can serve every task exactly.
  • Fraction reduction: fractional baud rate or sample-rate ratios are simplified by dividing numerator and denominator by their HCF, which saves register bits.
  • Gear and pulley ratios: encoders and motor controllers reduce ratios to lowest terms to keep arithmetic small.

Common Mistakes and Troubleshooting

  • Dropping the return. Writing the recursive call as a plain statement, without return, leaves the function without a value on that path. The caller then uses an undefined result. GCC warns about this with -Wall (control reaches end of non-void function), so never ignore that warning.
  • Keeping state in globals. Storing the running multiples outside the function breaks repeated and concurrent calls.
  • Multiplying before dividing for LCM. The product a times b can overflow even when the LCM fits.
  • Using a 32-bit result for LCM. The LCM of two 32-bit values may need 64 bits.
  • Calling HCF with both arguments zero. The result is 0, which then causes a division by zero in the LCM. Handle zero first, as shown.
  • Relying on the optimizer. The subtraction method crashed at -O0 and worked at -O2 for the same input.

Best Practices, Performance and Security

  • Make sure every branch of a recursive function returns a value, and build with -Wall -Wextra.
  • Prefer the remainder form of Euclid’s algorithm for real code and keep subtraction for teaching.
  • Choose result types wide enough for the worst case, and divide before multiplying.
  • Performance: on cores without a hardware divider each % is a software routine, so on a Cortex-M0 an iterative binary GCD that uses only shifts and subtraction can be faster.
  • Security: inputs that come from outside, such as a sensor or a network packet, should be range checked before computing an LCM that is later used as a buffer size or timeout.

Summary and Key Takeaways

  • HCF takes the shared primes; LCM takes the highest count of every prime; HCF times LCM equals the product.
  • Euclid’s subtraction method is simple but can need as many calls as the larger number.
  • Euclid’s remainder method needs very few calls and has a bounded depth, which makes it suitable for embedded use.
  • Compute LCM as (a / HCF) times b in a wider type.
  • Every recursive path must return a value, and state belongs in parameters.

Conclusion

You have now seen recursion used well. Instead of one frame per unit of the input, Euclid’s remainder method shrinks the problem so fast that the stack stays tiny, and the call counts printed by the program prove it. You also practiced three habits that carry over to all firmware work: measure instead of guessing, pass state as parameters, and widen the result type before an arithmetic operation can overflow. The final lecture of this chapter brings the ideas together with output-prediction exercises, a quiz and interview questions. Keep following this free embedded C course to turn each of these small programs into confident C programming for embedded systems.

Frequently Asked Questions

What is the difference between HCF and GCD?

They are the same thing. HCF (highest common factor) is the term used in many textbooks and GCD (greatest common divisor) is the term used in most programming literature.

Why does Euclid’s algorithm work?

Any number that divides both a and b also divides a minus b and the remainder of a divided by b, and the reverse is also true. So the pair can be replaced by a smaller pair with the same common divisors until one reaches zero.

Is recursion safe for HCF in embedded C?

For the remainder form, yes in most cases, because the depth stays under about 50 for 32-bit inputs. An iterative loop is still the most conservative choice.

Why is the LCM calculated as a divided by HCF times b?

Dividing first keeps the intermediate value small. Computing a times b first can overflow the type even when the final LCM would fit.

What is the HCF of 0 and a number?

It is the number itself, because every number divides zero. The LCM involving zero is conventionally defined as zero.

Can I find the HCF of three numbers?

Yes. Take the HCF of the first two, then the HCF of that result with the third. The LCM of three numbers works the same way.

Finish the Functions Chapter

The next lecture tests your understanding with output-prediction exercises, a quiz and interview questions from the free embedded C course.

💬 Need help or career guidance? Ask us!Contact Us →

2 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

×

🚀 BLE on Linux (BlueZ)

Hands-on course. Only ₹399

Enroll Now →