-1

I'm using a parallel recursion to evaluate if a number is odd or even. I used long type but I'm running into StackOverflowError when input number(x) has 5 digits or more. I don't get why.

static boolean Odd(long n) {
if (n == 0) return false;
else return Even(n - 1);     
}

static boolean Even(long d) {
if (d == 0) return true;
else return Odd(d - 1);  
}

public static void main(String[] args) {
    long x = 0; 
    while(x>=0) {
        System.out.println("Insert number");
        x = SavitchIn.readLong();
        boolean isOdd = Odd(x);
        if(isOdd) {
            System.out.println("Odd number");
        }else {
            System.out.println("Even number");
    }
    }
}
Tomerikoo
  • 18,379
  • 16
  • 47
  • 61
Baffo
  • 61
  • 5
  • 4
    "*StackOverflowError when input number(x) has 5 digits or more*" this would create 5 digits or more of stack frames, which is the most likely reason why the stack overflow happens. [What is a StackOverflowError?](https://stackoverflow.com/q/214741) – VLAZ Nov 27 '21 at 07:57
  • _Why_ recursion is needed instead of checking the least significant bit to be 0 (even) or 1(odd)? – Nowhere Man Nov 27 '21 at 08:43
  • 1
    @AlexRudenko it's not *needed* but it's a classical way to demonstrate mutual recursion. As with many introductory examples, it's overly simplistic and ultimately not something you'd place in real code *as is*, however, the point is to demonstrate the concept. A *real* example would be a recursive descent parser but it tends to be distracting as it has other stuff thrown in. The even/odd mutual recursion example is overall not worse than the typical example showin OO with `Student` and `Teacher` extending `Person` or `Cat` and `Dog` extending `Animal`. They are all flawed with aim of teaching. – VLAZ Nov 27 '21 at 08:50

1 Answers1

0

To understand why you get StackOverflowError, you need to understand what happens when you make a function call in your code and how that is executed in the actual processor.

When you run a program, all of the associated code and symbols are loaded in the memory and then executed one line after another. You have a register called Program Counter which basically acts as a pointer to the current line of code that is executed.

However, when the line to be executed is a function, the code for the function is not available immediately on the next memory address. Rather, this function will be available at a different location in memory. So when the processing unit sees a function call, it copies several important stats like the Program Counter [PC] (to know how far along the code has been executed), register values, etc., and pushes this data into a stack. The reason this data structure is a stack can be explained with the following simple code example:

public class Example {
  public int func1() {
    int a = 10, b = 20;
    int c = a+b;
    return c;
  }
  
  public int func2() {
    int a = 100;
    int b = func1();
    return a*b;
  }

  public static void main(String args[]) {
    int attr = 10;
    int result = func2() / 10;
    System.out.println(result);
  }
}

In this example, as you know, code execution starts at ```main```` function. So line 1 of the main function is executed and sets the attr variable to 10. Then it goes to line 2 and here, it sees that there is a function call namely func2.

So at this time, the system will push the PC, and other memory into the stack, and then move to the location of func2. In func2, line 1 is executed setting the value of a to 100. Line 2 of func2 is again a function call and hence again all the data is now again pushed onto the stack on top of the previous push and func1 is executed.

In func1, we have no function calls and hence no more stack pushes happen. Func1 has 3 lines of code which get executed one after the other. However, just because we reached the end of func1, it does not mean that we have finished executing the code. We still have to execute the rest of func2 and main. The first set of code we need to execute is func2 because func2 called func1. This is exactly what we have in the stack as well (the top of the stack has func2 values). So we pop it, continue executing func2 and once that is done, we go back to the stack and see there is an entry from the main function. So we pop that out and complete execution.

Now that we have this bit of understanding, in your code, you see that the Odd() and Even() method call each other recursively. For a small number of 5, we see the following happening:

Main( 
  -push-> Odd(5 
    -push-> Even(4 
      -push-> Odd(3 
        -push-> Even(2 
          -push-> Odd(1 
            -push-> Even(0 
              [return's true]
            ) -pop-> 
          ) -pop->
        ) -pop->
      ) -pop-> 
    ) -pop-> 
  ) -pop-> 
)

So in this case, for a small number like 5, we see that the size of the stack goes as high as 6. Now for a 5 digit number like 99999, the maximum size of the stack will be 100000 which is an extremely large number for the stack. Remember that for every stack entry, we will be copying the PC, registers, etc. on the stack.

This is why you see a StackOverflowError for 5 digit numbers. The size of the stack becomes very high when the number of digits is 5 which is probably beyond the capabilities of the processor that is running your code.

whiplash
  • 695
  • 5
  • 20