Why was the memory limit exceeded and how can I avoid this?

Question

Code

import java.util.*;

public class AlmostPerfect {

    public static void main(String[] args) {
        Scanner x = new Scanner(System.in);

        while(x.hasNext()) {
            int n = x.nextInt();
            int sum = recursion(n, n-1, 0);
            if (sum == n) {
                System.out.println(n + " perfect");
            } else if ((n - sum) <= 2) {
                System.out.println(n + " almost perfect");
            } else {
                System.out.println(n + " not perfect");
            }
        }
    }

    public static int recursion(int n, int x,int sum) {

        if(x == 0){
            return sum;
        }
        else if (n % x == 0) {
            sum += x;
            return recursion(n, x-1, sum);
        }
        else{
            return recursion(n, x-1, sum);
        }
    }
}

I want to basically find what's wrong with my solution... There exists a solution for this, but I can't understand the memory limit exceeded property.

Problem link: https://open.kattis.com/problems/almostperfect

`n` can be as large as one billion. Think about the worst case: when the value of `n` is `1e9`, what happens to the stack? Also, there are some other bugs in your code and scope for optimization. — Sufian Latif, Jul 10 '18 at 16:49
@Andreas anything that can be done with loop can be done with recursion, and vice versa. — EvOlaNdLuPiZ, Jul 10 '18 at 17:05
@EvOlaNdLuPiZ Sure, if you maintain your own stack of backtracking information, any recursion can be written as a loop, but the code may be more complex. However, *this* code doesn't need any backtracking information, so it can be done with a ***simple*** loop. — Andreas, Jul 10 '18 at 17:08
Recursion will run on OutOfMemory by keeping the old recursion variables OR run on StackOverflowException if the stack of calls reach a size of Integer.MAX_VALUE. Whatever come first, the best solution is to use a for loop instead — Marcos Vasconcelos, Jul 10 '18 at 17:14
regardless of memory management techniques the problem in the post is bounded by memory limits, meaning the program can only go so far in processing certain numbers before the hardware can no longer support processing. for clarification, peek at this answer to get some insight on your system [link](https://stackoverflow.com/questions/25552/get-os-level-system-information) — EvOlaNdLuPiZ, Jul 10 '18 at 17:14
Just a side note, your `recursion` method unnecessarily duplicates the `recursion(n,x-1,sum)` call. You could use `if(x==0){ return sum; } else { if (n % x == 0) { sum+=x; } return recursion(n,x-1,sum); }` instead, or even make it a one-liner: `return x==0? sum: recursion(n, x-1, n%x == 0? sum+x: sum);`. If your JVM had tail call optimization, it could run this method for any positive `x`, but since most JVMs don’t have it, you better use a loop. — Holger, Jul 10 '18 at 17:29

score 0 · Answer 1 · edited Dec 16 '20 at 15:28

If you must prefer a recursive solution, you can limit the depth of the recursion, to avoid stack overflow.

You can do it be running the recursive solution on continuous intervals, one interval at time:

import java.util.stream.IntStream;

public class AlmostPerfect {

    // Defines the recursive iteration depth. increase it and you run into
    // Stack overflow
    private static int RECURSION_DEPTH = 5000;

    public static void main(String[] args) {

        // Run comparison test between recursive and non recursive solutions
        IntStream.range(1, 200000).forEach(i -> {

            double sumRecursive = recursionWithLimitedDepth(i);
            double sumIterative = iterative(i);

            if((sumRecursive != sumIterative)) {
                System.out.println("for " + i + " " + sumRecursive + "<>" + sumIterative);
                return;
            }

            if((i%20000) == 0) {
                System.out.println("20,000 numbers successfully checked");
            }
        });

        System.out.println("Test finished");
    }

    // Helper method for recursive solution
    public static double recursionWithLimitedDepth(int n) {

        double sum = 0;
        int rangeStart = n-1;
        int rangeEnd = rangeStart - RECURSION_DEPTH;

        while (rangeStart > 0) {
            sum += recursionWithLimitedDepth(n, rangeStart, rangeEnd, 0);
            rangeStart = (rangeEnd - 1) >= 0 ? rangeEnd - 1 : 0;
            rangeEnd = (rangeStart - RECURSION_DEPTH) >= 0 ? rangeStart - RECURSION_DEPTH : 0;
        }

        return sum;
    }

    // Run recursive solution on a limited range defined by rangeStart, rangeEnd
    public static double recursionWithLimitedDepth(int numberToTest, int rangeStart,
                                                   int rangeEnd, double sum) {
        if(rangeStart == 0) {
            return sum;
        }
        else if ((numberToTest % rangeStart) == 0) {
            sum += rangeStart;
        }

        if(rangeStart == rangeEnd) {
            return sum;
        }

        return recursionWithLimitedDepth(numberToTest, rangeStart-1, rangeEnd, sum);
    }

    // Simple iterative to test against
    public static double iterative(int n) {

        double sum = 0;

        for(int x = n-1; x > 0; x--) {
            if((n%x) == 0) {
                sum += x;
            }
        }
        return sum;
    }
}

Note that sum is double to avoid Integer overflow (tested with Integer.MAX_VALUE).

Why was the memory limit exceeded and how can I avoid this?

Code

1 Answers1

Linked