3

I have been doing my homework about recursion and I realized something very strange.

import java.util.Scanner;
public class Recursive{

    public static void main ( String [] args){
        Scanner scan = new Scanner(System.in);
        while(true){
            System.out.println("Please Enter the Number");
            int n = scan.nextInt();
            int upper = (int)Math.pow(10, n);
            int lower = (int)Math.pow(10, n - 1);
            printNumbers(upper, lower);
        }
    }

    public static void printNumbers(int upperBound , int lowerBound){
        if(upperBound < lowerBound){
            System.out.println("Start Point");
        } else if (isOrdered(upperBound)){              // Line 18
            int holder = upperBound;
            printNumbers(upperBound - 2, lowerBound);
            System.out.print(holder + " ");
        } else{
            printNumbers(upperBound - 2, lowerBound);   // Line 23
        }
    }

    public static boolean isOrdered(int number){    
        if(number < 10) return true;
        return (number % 10 > (number / 10) % 10) && isOrdered(number / 10);
    }
}

At the above code, the program checks whether or not digits in the number are increasing order left to right. I ask for user to enter input n to find out how many digits each number will have. Program works perfectly find for the n values 1 , 2 , 3 , 4. But the program acts strange when we enter in different order. For example, I can enter 4 as many as I want but when I enter 3 and 4, program crashes with infinite recursion in the printNumbers method. I do not understand that since the program works for 3 and for individually but we enter 3, get the result we enter 4 and it crashes Why it is crashing?

PS: I made the while(true)at the main method just for checking. At the below it is the stack trace.

Exception in thread "main" java.lang.StackOverflowError
    at Recursive.printNumbers(Recursive.java:18)
    at Recursive.printNumbers(Recursive.java:23)
    at Recursive.printNumbers(Recursive.java:23)
    at Recursive.printNumbers(Recursive.java:23)
    ...
Socowi
  • 25,550
  • 3
  • 32
  • 54
asimtot
  • 63
  • 1
  • 6
  • Can you please [edit] your question to point out where and how it crashes? – Federico klez Culloca Apr 14 '21 at 08:01
  • I edit the question. I add stack trace and explicitly refer why it is crashing – asimtot Apr 14 '21 at 08:08
  • So you don't have a crash but a stackoverflow error due to a missing or incorrect "end" condition in your recursion - or just too many recursions. Since you're your upper bound is `10^n` and your lower bound is `10^n-1` doing a recursion by just decreasing the upper bound by 2 can lead to a lot of recursions, e.g. for `n=4` you'd have a recursion depth of about 4500. – Thomas Apr 14 '21 at 08:08
  • 1
    Yes but for input 3 it works. for input 4 it works. I enter 3 then enter 4, then stack overflow. My theory was java does not making stack trace empty so for that there is no enough room for new method calls. On the other hand I can enter 4 as many as I want and this refutes my theory. – asimtot Apr 14 '21 at 08:11
  • Threads have their own stacks and stack size is limited, so it's expected for stack to be full after a while. The reason you can enter 4 as much as you want might be some kind of a memory optimization JVM does. – onur Apr 14 '21 at 08:42
  • Note that in real world applications you shouldn't have so deep recursions anyway since you'd always risk a stack overflow. Instead you might want to build the algorithm in a non-recursive manner. In your case a simple loop would already do the trick. – Thomas Apr 14 '21 at 08:47
  • @Asimtot , here is the output for 3 4 3 , its not crashing . 3 Start Point 124 126 128 134 136 138 146 148 156 158 168 178 234 236 238 246 248 256 258 268 278 346 348 356 358 368 378 456 458 468 478 568 578 678 Please Enter the Number 4 Start Point 1234 1236 1238 1246 1248 1256 1258 1268 1278 1346 1348 1356 1358 1368 1378 1456 1458 1468 1478 1568 1578 1678 2346 2348 2356 2358 2368 2378 2456 2458 2468 2478 2568 2578 2678 3456 3458 3468 3478 3568 3578 3678 4568 4578 4678 5678 Please Enter the Number 3 Start Point 124 126 128 134 136 138 146 148 156 158 168 178 234 236 238 246 248 – Knowledge_seeker Apr 14 '21 at 09:16
  • @Knowledge_seeker I could reproduce OP's problem with openjdk16 on Linux. What version of java did you use? Also, did you try `1`, `2`, `3`, `4`? – Socowi Apr 14 '21 at 10:18
  • Please do NOT put such information into comments, always edit your question instead. All relevant information should be IN the question. – GhostCat Apr 14 '21 at 10:52
  • I used javaSE11, I have used – asimtot Apr 14 '21 at 16:43

0 Answers0