Home > Mobile >  Why the recursion isn't working?, the idea is that it must return if a number can be written as
Why the recursion isn't working?, the idea is that it must return if a number can be written as

Time:07-05

public class Main {
public static void main(String[] args) {
    int num = 3;
    sumPower3(num);
}

private static boolean sumPower3(int num) {
    return sumPower3(num, 0);
}

private static boolean sumPower3(int num, int power) {
    if(num==0) {
        return true;
    }
    if(num<0) {
        return false;
    }
    
    return sumPower3((int)(num-Math.pow(3, power)), power 1) || sumPower3(num, power 1);
}

}

Write a recursive Boolean static method, which accepts as a parameter a positive integer (real) The method should check if this number can be written as a sum of powers of 3. Each power of 3 can appear in the amount at most once. If the number can be written like this, the method will return the value true, otherwise it will return false

CodePudding user response:

The recursive call sumPower3(num, power 1) may arbitrarily increase the value of the exponent, causing stack overflow error. To solve the problem, set a maximum value for this parameter - log(num,3) - and terminate the recursion when its value exceeds that limit.

public class Maim {
    public static void main(String[] args) {
        System.out.println(sumPower3(2296)); // true: 3^0   3^3   3^4   3^7 == 2296
        System.out.println(sumPower3(2297)); // false
        System.out.println(sumPower3(2298)); // true: 3^1   3^3   3^4   3^7 == 2298
    }

    private static boolean sumPower3(int num) {
        return sumPower3(num, 0, Math.log(num)/Math.log(3.0)); // set limit for power
    }

    private static boolean sumPower3(int num, int power, double limit) {
        if(num==0) {
            return true;
        }
        if(num<0 || power > limit) {        // check limit for power
            return false;
        }
        return sumPower3((int)(num-Math.pow(3, power)), power 1, limit) || sumPower3(num, power 1, limit);
    }
}
  • Related