Java рекурсии возвращает строку

Question

public String starString(int n){    
    int m = (int)Math.pow(2,n); 
    String str=""; 
    str = starString(m-1,str);     
    return str; 
} 
private String starString(int n, String str){   
    String temp =""; 
    if (n<0) { 
     try{ 
      throw new IllegalArgumentException(); 
     } 
     catch(IllegalArgumentException ex){    
     }   
    } 
    else { 
     temp+=("*");    
     starString(n-1,str);   
    }      
    return temp;  
} 

Может кто-то пожалуйста, объясните мне, почему этот код возвращает одну звездочку, даже если его называют значением больше, чем n >= 0?

Я отлаживал и заметил, что после выброса исключения он снова повторяется, и все звездочки нарезаются на «». Я пробовал это много раз. Также требуется, чтобы вы выбрали IllegalArgumentException, если n < 0.

Answer 1

В Java струнами immuntable, следовательно, вам нужно присвоить новое значение temp (и передать temp в качестве параметра):

temp = starString(n-1, temp);   

Кроме того, вы должны были бы назначить str для temp, в противном случае каждый рекурсии просто возвращает одну звездочку:

String temp = str; 

гораздо проще, чище (и правильно) версию рекурсивный метод будет выглядеть следующим образом:

private String starString(int n){   
    String temp = "*"; 

    //only recurse as long as n > 0, i.e. the last invocation would be made with n = 0 
    if (n > 0){ 
    temp += starString(n-1);      
    }      
    return temp;  
} 

Обратите внимание, что вам даже не нужно передавать строку в качестве параметра. Также обратите внимание на то, что рекурсия здесь чрезмерна, использование цикла может вызвать много шума. Также обратите внимание, что конкатенация строк является дорогостоящей и быстро замедляется для более высоких значений n (из-за неизменяемых экземпляров строк, создаваемых снова и снова). В этом случае лучше использовать StringBuilder:

private String starString(int n){   
    StringBuilder s = new StringBuilder(); 
    for(int i = 0; i <= n; i++) { 
    s.append("*"); 
    } 
    return s.toString(); 
} 

На моей машине версия, цикл с помощью конкатенации занимает около 12 секунд при п = 100000, тогда как версия StringBuilder занимает 0,007 секунды.

Answer 2

Ваш код вызывает каждую рекурсию, сохраняет локальный temp, возвращает это и никогда не используется.