CODEWITHSUNDEEP
javarecursion
blutuu
blutuu

Reputation: 590

Given a number, find which numbers below it divide it using recursion

I can't seem to figure this one out. I need to count how many numbers below a given number in which it is divisible.

Here is what I've tried:

public int testing(int x) {
    if (x == 0) {
        System.out.println("zero");
        return x;
    }
    else if ((x % (x-1)) == 0) {
        System.out.println("does this work?");
        x--;
    }

    return testing(x-1);
}

That doesn't work and I don't know where to go from here. Anyone know what to do?

Upvotes: 1

Views: 316

Answers (6)

Marconius
Marconius

Reputation: 713

This is not a task that should be solved with recursion.

If you MUST use recursion, the simplest way to do it is to have a second parameter, which is essentially an "I have checked until this number". Then you can increase/decrease this (depending on if you start at 0 or the initial number) and call the recursive on that.

Thing is, Java isn't a functional language, so doing all this is actually kind of dumb, so whoever gave you this exercise probably needs a bop on the head.

Upvotes: 2

alterfox
alterfox

Reputation: 1695

Using recursion:

private static int getFactorCount(int num) {
    return getFactorCount(num, num - 1);
}

private static int getFactorCount(int num, int factor) {
    return factor == 0 ? 0 : (num % factor == 0 ? 1 : 0)
            + getFactorCount(num, factor - 1);
}   

public static void main(String[] args) {
    System.out.println(getFactorCount(20)); // gives 5
    System.out.println(getFactorCount(30)); // gives 7
}

Upvotes: 0

tbodt
tbodt

Reputation: 17017

There is no need to use recursion here. Here's a non-recursive solution:

public int testing(int n) {
    int count = 0;
    for (int i = 1; i < n; i++)
        if (n % i == 0)
            count++;
    return count;
}

BTW, you should probably call this something other than testing.

Upvotes: 0

SJuan76
SJuan76

Reputation: 24895

This is what is wrong:

 public int testing(int x) {

If you want to make it recursive, you need to pass both the number to test and the number that you are currently checking. The first one will not change through the recursion, the second one will decrement. You cannot do what you express with only one parameter (unless you use a global variable).

Upvotes: 2

jeff
jeff

Reputation: 4333

You have a problem with your algorithm. Notice the recursion only ends when x == 0, meaning that your function will always return 0 (if it returns at all).

In addition, your algorithm doesn't seem to make any sense. You are basically trying to find all factors of a number, but there's only one parameter, x.

Try to make meaningful names for your variables and the logic will be easier to read/follow.

public int countFactors(int number, int factorToTest, int numFactors)
{
  if (factorToTest == 0) // now you are done
    return numFactors;
  else
    // check if factorToTest is a factor of number
    // adjust the values appropriately and recurse
}

Upvotes: 0

chrylis -cautiouslyoptimistic-
chrylis -cautiouslyoptimistic-

Reputation: 77234

Your problem is that your expression x % (x - 1) is using the "current" value of x, which decrements on every call to the recursive function. Your condition will be false all the way down to 2 % (2 - 1).

Using a for loop is a much better way to handle this task (and look at the Sieve of Eratosthenes), but if you really have to use recursion (for homework), you'll need to pass in the original value being factored as well as the current value being tried.

Upvotes: 0

Related Questions