Код рекурсии Java

Question

public class Temp { 
    public static void main(String[] args) { 
     System.out.println(recursion(1, 100)); 
     System.out.println(recursion(4, 5)); 
     System.out.println(recursion(99, 100)); 
     System.out.println(recursion(100, 100)); 
    } 

    public static int recursion(int m, int n) { 
     int number = 0; 
     if (m == 1) { 
      number = ((2 * n) - 1); 
     } else { 
      number = 2 * recursion(m - 1, n - 1); 
     } 
     return number; 
    } 
} 

Когда я запускаю этот код, последние два теста возвращают 0, и я знаю, что они должны быть большими числами, вот почему? Как я могу определить стоимость последних двух?

Answer 1

Вы столкнулись с арифметическим переполнением. int может хранить только значения между -2^31 и 2^31-1. Чтобы справиться с цифрами, это большой, вам нужен более подходящий тип данных, например BigInteger.

Answer 2

В какой-то момент вы превысили максимальное число для типа int. Тогда результат умножения становится отрицательным, тогда - нулем.

m = 31, n = 32 : number = -1073741824 
m = 32, n = 33 : number = -2147483648 

Следующий шаг умножить их (т = 33, п = 34):

System.out.println((-1073741824) * (-2147483648)); 

Что 0.

Начиная с этого момента, все равно 0.