StackOverflowError for while finding co-prime pairs for 2 numbers using recursive function - Can we convert it to an iteration

Question

I wanted to Calculate num of Pairs of (m,n) where GCD(m,n)=x, say x=1 and 1<=m<=M=10^5 and 1<=n<=N=10^5.

M and N will be given

Note: I just want the number of possible pairs and not the pairs.

TIME LIMIT : 5 Secs

The below code works good for small numbers, but for larger ones it gives me StackOverflowError

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class TestClass{
static long M;
static long N;
static long totalCount = 1;

public static void main(String[] args) throws Exception{
    M = 100000;
    N = 2000;
    findCoPrimes(2, 1);
    findCoPrimes(3, 1);
    System.out.println(totalCount);
}

public static void findCoPrimes(int m, int n){
    if ((n > N) || (m > M)){
        return;
    }
    if (n != m && m <= N){
        totalCount++;
    }
    totalCount++;
    findCoPrimes(2*m - n, m);
    findCoPrimes(2*m + n, m);
    findCoPrimes(m + 2*n, n);
}
}

Can someone help me convert this recursive function to an iterative function to avoid the StackOverflow error.

Please help me find a solution for this. Any other better approaches will also be considered. There is a hint with this question - Use smart ways to find the prime factors and then find the number of co prime pairs. Brute force wont work.

All recursion can be unrolled with a stack data structure... recursion is just a way of using the computer's built-in stack instead of your own — Matt Coubrough, May 28 '14 at 04:35
Could you give results for M=9, N=4, for instance? Your program says the answer is 25, but when I enumerate them manually I come up with 19: {(1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (2,3), (2,5), (2,7), (2,9), (3,4), (3,5), (3,7), (3,8), (4,5), (4,7), (4,9)}. What am I missing/not understanding? — pjs, May 28 '14 at 17:40
@pjs you have missed (2,1)(3,1)(3,2)(4,1)(4,2)(4,3) So you are now with 25 :). Could you pls help. I could convert the code above into Iterative. But dint work good with higher nums! :( — Ajinkya Mahagaonkar, May 29 '14 at 10:38
There is some better approach. A Hint i got was - Use smart ways to find the prime factors and then find the number of co prime pairs. Brute force wont work. But no possible solution :( — Ajinkya Mahagaonkar, May 29 '14 at 10:40
So order matters? That surprises me. This is the straight word from your instructor? — pjs, May 29 '14 at 15:09

score 2 · Answer 1 · edited May 23 '17 at 11:50

2

To convert to an iterative function, you can create a stack object that you use to simulate the function stack.

Using a stack object will allow you to store your state in the heap instead of the stack which is usually set to 256K by default.

See general approach to converting to iteration here: https://stackoverflow.com/a/159777/276949

edited May 23 '17 at 11:50

Community

1
1

answered May 28 '14 at 04:32

Martin Konecny

57,827
19
139
159

so, instead of stack overflow, he'll eventually get Java's heap overflow :) I don't think that it'll solve the problem. – Oleg Gryb May 28 '14 at 04:38
1

Why not? The heap is able to store far more than the stack – Martin Konecny May 28 '14 at 04:39
You can increase stack size just like you can increase heap. – Oleg Gryb May 28 '14 at 04:45
1

@Oleg Gryb You don't need to increase the heap size (it's bigger than the stack by default), and by using your own stack data-structure instead of the JVM's stack you can manage and monitor the state of your stack - It gives you much finer control than relying on recursion. – Matt Coubrough May 28 '14 at 04:50
It doesn't matter what is bigger by default as long as you can change the max size easily. Managing and monitoring is not going to help much if you're running out of memory. Anyway, good luck with converting. – Oleg Gryb May 28 '14 at 05:06
Default stack size is about 128KB depending on platform whilst the default heap is at least 8MB so we're talking about a lot more memory to play with – Matt Coubrough May 28 '14 at 05:20

StackOverflowError for while finding co-prime pairs for 2 numbers using recursive function - Can we convert it to an iteration

1 Answers1