recursive algorithm to find divisors, without the use of loops-CodePudding

I'm trying to find an algorithm to print all the divisors of n (including 1 and n), but it can only be recursive with 1 input and no loops at all. I tried toying with prime numbers and maybe looking for a pattern but I can't seem to find a way without a for or a while. So the declaration of the function has to be void divisors( int n ) and it needs to be recursive. I don't want a full code since it is an assignment, I'm more looking for a hint, or a perspective that i might be missing

CodePudding user response：

From what I understand:

The declaration of the function has to be void divisors( int n )
It needs to be recursive
No ~~capes~~ loops

One solution is to use indirect recursion. This allows a helper function to be implemented to maintain state in an extra parameter, but the helper function can call upon divisors(). In so doing, it is recursively called.

So, for example, you could use signed values to indicate divisors() should print the negative value as a divisor.


void divisors (int n) {
    if (n > 0) {
        printf("divisors of %d:", n);
        divisors2(n, 1);
    }
    else if (n < 0) printf(" %d", -n);
    else printf("\n");
}

And the recursive divisors2() would call divisors() with a negative parameter to print a found divisor.


void divisors2 (int n, int p) {
    if (p > n) {
        divisors(0);
        return;
    }
    if (!(n % p)) divisors(-p);
    divisors2(n,   p);
}

CodePudding user response：

As documented by @CraigEstey, the the classic recursive approach would require a second argument. Since the prototype is fixed, you need another way to keep track the current divisor. You can:

use a global variable
use a local static variable.
use part of the argument for the divisor, drastically reducing the range of values for the initial call.

This is not very elegant but does not seem to break the rules.

Here is an example with a thread local static variable:


void divisors(int n) {
    static _Thread_local int p = 0;
    if (p   == 0) {
        printf("divisors of %d:", n);
    }
    if (p > n) {
        printf("\n");
        p = 0;
        return;
    }
    if (n % p == 0) {
        printf(" %d", p);
    }
    divisors(n);
}

If you are willing to abuse the rules a bit more, here is an even simpler one that meets the criteria:

conforming prototype void divisors(int n)
no for or while loops
use of recursion


void divisors(int n) {
    int p = 1;
    if (n <= 0) return;
    printf("divisors of %d:", n);
  next:
    if (n % p == 0) printf(" %d", p);
    if (p   < n) goto next;
    printf("\n");
    divisors(0);  // dummy recursive call
}

CodePudding user response：

This can not be done with a single argument.

I realized this (as did others)

Eric came up with the rationale/proof in the comments, so I'll summarize them here:

Maybe, but OP does not say the problem specification dictates that signature. Rather, they say “So the declaration of the function has to be…,” suggesting that signature is their own conclusion from the one-input requirement. If so, it is not correct; a requirement that there be one input admits the possibility of other signatures. – Eric Postpischil

Suppose the routine is passed a number n and should print all the divisors of n. Given that the routine must be recursive, it might call itself with some factor of n, say f. That recursive call will print all the factors of f. Then the call that was passed n must otherwise print all the factors of n that are not also factors of f, which I will call the extra factors. Perhaps it might do this with its own code or it might do it with recursive calls. However, a problem is that the number of such factors varies. For example, if n is 14 and f is 7, there are two extra factors, 2 and 14… – Eric Postpischil

… However, if n is 30 and f is 15, there are four extra factors, 2, 6, 10, and 30. There can be arbitrarily many extra factors. This implies the routine cannot do a fixed amount of printing; it must use some loop. But using a loop, other than recursion, is prohibited. Also, printing the extra factors cannot be done by a recursive call to the routine, since 1 is a factor of any positive integer, so any recursive call must print 1; it cannot be limited to 2, 6, 10, and 30. Therefore, if a no-loop recursive solution is possible, it cannot be accomplished by passing only the number to be factored. – Eric Postpischil

From the above:

So, while we need:

void divisors(int n)

This, does not preclude a helper function (e.g.)

void divrec(int n,int f)

Where f is the current divisor/factor to test.

Printing 1 and n as factors has to be special cased.

But, after that, divrec can call itself recursively, starting with divisors calling with: divrec(n,2). If crafted carefully, the compiler optimizer will do "tail recursion" so we don't blow up the stack.

The actual function is so simple, it's hard to "hint" at it without just actually showing it, but:

If f > n, stop/return.
If n is divisible by f, then print f and divide n by f.
Otherwise, increase f by 1.
recursively call divrec with the updated n and f values.

IMO, the resulting C code is easier to understand than the pseudocode description here.

Here is the sample code. It is annotated:

#include <stdio.h>

typedef long long num;

#define DIVME(_expr) \
    do { \
        printf("EXPR: " #_expr "\n"); \
        divisors((num) _expr); \
    } while (0)

void
prt(num f)
{

    printf(" %lld",f);
}

void
divrec(num n,num f)
// n -- remaining number
// f -- current factor to try
{

    // at this point, we've "looped" f all the way from 2 to n
    if (f > n)
        return;

    // got a factor:
    // (1) print it
    // (2) reduce the number down
    // (e.g.) number divisible by 2 -- next try is (n / 2,2)
    if ((n % f) == 0) {
        prt(f);
        n /= f;
    }

    // number is _not_ divisible by current factor -- increase the factor by 1
    // (e.g.) number is _not_ divisible by 2 -- next try is (n,3)
    else
        f  = 1;

    // ensure "tail recursion" so we do _not_ blow up the stack
    // (with optimization)
    // NOTE: on my system, this generates an internal loop in the asm insts
    // generated
    divrec(n,f);
}

void
divisors(num n)
{

    // special case for n/1:
    prt(1);
    prt(n);
    printf("\n");

    divrec(n,2);
    printf("\n");
}

int
main(void)
{

    DIVME(2 * 3 * 5 * 7 * 11 * 13 * 17 * 23 * 29 * 31 * 3 * 7 * 13 * 13);

    return 0;
}

Here is the program output:

EXPR: 2 * 3 * 5 * 7 * 11 * 13 * 17 * 23 * 29 * 31 * 3 * 7 * 13 * 13
 1 37462588393230
 2 3 3 5 7 7 11 13 13 13 17 23 29 31

Special casing 1 n in divisors seems pretty clean to me. But, it might be closer to the "letter of the law" to special case in divme (at the cost of a slightly slower/fatter divrec):

void
divrec(num n,num f)
// n -- remaining number
// f -- current factor to try
{

    do {
        if (f == 1) {
            prt(1);
            prt(n);
            printf("\n");
            f = 2;
            break;
        }

        // at this point, we've "looped" f all the way from 2 to n
        if (f > n)
            return;

        // got a divisor:
        // (1) print it
        // (2) reduce the number down
        // (e.g.) number divisible by 2 -- next try is (n / 2,2)
        if ((n % f) == 0) {
            prt(f);
            n /= f;
            break;
        }

        // number is _not_ divisible by current factor -- increase the factor
        // by 1
        // (e.g.) number is _not_ divisible by 2 -- next try is (n,3)
        f  = 1;
    } while (0);

    // ensure "tail recursion" so we do _not_ blow up the stack
    // (with optimization)
    // NOTE: on my system, this generates an internal loop in the asm insts
    // generated
    divrec(n,f);
}

void
divisors(num n)
{

    divrec(n,1);
    printf("\n");
}

CodePudding user response：

updated

Assuming you can only use an int parameter as in:

void divisors(int n)

Cheat and use the upper bits of the parameter, n passed in as a way to stash the current divisor. There's some reasonable assumptions: 2's complement, 8-bit bytes, and an int is at least 32-bit wide. But that's pretty much universal these days.

For any pair of factors for n, x and y with x<y, then x will be at most sqrt(n). It takes half the number of bits to hold the square root of a number. So 1/3 of our bits for the divisor and the other 2/3 of our bits for the value we are attempting to factor.

The compromise if that on a 32-bit int, the range is limited to 20-bits, or 0 <= n <= 1048575

void divisors(int n)
{
    unsigned int un = (unsigned int) n;
    size_t width = sizeof(n) * 8;

    // we can use up to 1/3 of our bits to hold the
    // divisor
    size_t divprecision = (width / 3);
    size_t valueprecision = width - divprecision;

    unsigned int divisor = un >> valueprecision;
    unsigned int mask = (unsigned int)(-1);
    mask = mask >> divprecision;

    unsigned int value = un & mask;

    if (divisor == 0)
    {
        divisor = 1;
    }

    if (value % divisor == 0)
    {
        printf("%d\n", divisor);
        printf("%d\n", value / divisor);
    }

    divisor  ;

    // the stopping point is when divisor >= sqrt(value), or divisor*divsor > value
    if ((divisor * divisor) > value)
    {
        return;
    }
    
    un = (divisor << valueprecision) | value;
    divisors(un);

Invoking divisors(1048575) prints: