Преобразовать итерационную функцию рекурсии

Question

java version "1.8.0_92" 

Привета,

Я пытаюсь преобразовать эту функцию, которая использует итерацию к рекурсивному.

public static String bitConversion(int x) { 
     List<Integer> binaryList = new ArrayList<Integer>(); 

     while(x > 0) { 
      binaryList.add(x % 2); 
      x /= 2; 
     } 

     StringBuilder stringBuilder = new StringBuilder(); 
     for(Integer binary : binaryList) { 
      stringBuilder.append(binary.toString()); 
     } 

     return stringBuilder.toString(); 
    } 

Моя попытка это

public static String bitConversion(int x) { 
     List<Integer> binaryList = new ArrayList<Integer>(); 

     if(x <= 0) { 
      StringBuilder stringBuilder = new StringBuilder(); 
      for(Integer binary : binaryList) { 
       stringBuilder.append(binary.toString()); 
      } 

      return stringBuilder.toString(); 
     } 
     else { 
      binaryList.add(x % 2); 
      return bitConvert(x/2); 
     } 
    } 

Одно дело, что мне нужно, чтобы иметь binaryList добавить Integer к. В первом условии, когда все будет закончено, мне нужно поместить их в построитель строк. И во втором условии мне нужно добавить их в список. Таким образом, список должен быть глобальным для обоих условий. Но по мере того как функция вызывает себя, список будет повторно инициализирован каждый раз.

Может ли любой совет по наилучшему способу написать эту рекурсивную функцию?

Большое спасибо за любые предложения.

Answer 1

В основном с рекурсией у вас есть 2 части: 1) условие завершения рекурсии 2) часть, в которой вы разбиваете задачу под рукой на меньшие куски и составляете их результаты.

public static String bitConversion(int x) { 
    // just simplifying my life here as negative numbers can be represented 
    // in a few ways and usually it's additive code I don't want to deal 
    // with here :) 
    if (x < 0) { 
     throw new IllegalArgumentException("Not implemented for negatives"); 
    } 

    // recursion termination condition for 0 and 1 
    if (x <= 1) { 
     return String.valueOf(x); 
    } 

    // recurision 
    int leastSignificantBit = x % 2; 
    String significantBits = bitConversion(x/2); 
    return significantBits + leastSignificantBit; 
} 

Answer 2

Ваше условие конца рекурсии - x == 0, после чего вы возвращаете пустую строку. Когда x> 0, вы должны просто рекурсивно вызвать метод для x/2.

Итак, что-то вроде этого?

public static String bitConversion(int x) { 
    if (x == 0) { 
     return ""; 
    } 
    return (x % 2) + bitConversion(x/2); 
} 

Answer 3

public static String bitConversion(int x) { 
    if (x <= 0) return ""; 
    else return x % 2 + bitConversion(x/2); 
} 

Как о чем-то, как этот выше. Плохо то, что он не использует StringBuilder. Но вы можете реализовать аналогичный, который вернет StringBuilder, а затем перенесет вызов в .toString другим способом.