Различные способы использования рекурсии в Java

Я думаю о нескольких элегантных способах написания простой Lisp-подобной рекурсивной функции в Java, которая, скажем, простое суммирование.

В Common Lisp это будет так:

(defun summation(l)
 (if l
 (+ (car l) (summation (cdr l)))
 0))

(summation '(1 2 3 4 5)) ==> 15

В Java одним из многих возможных решений было бы:

public int summation(int[] array, int n) {
 return (n == 0)
 ? array[0]
 : array[n] + summation(array, n - 1);
}
CALL: 
summation(new int[]{1,2,3,4,5}, 4); //15

1) Есть ли какой-либо возможный способ НЕ использовать индекс n?

2) Или оставьте свое решение (нетеративное), которое вы считаете интересным.

Благодарю.

5 ответов

Если вы используете метод List.subList, он может выполнять итерацию внизу. Вместо этого вы можете использовать Queue, чтобы избежать итерации. Например:

public int sum(Queue queue) {
 return queue.isEmpty() ? 0 : (queue.poll() + sum(queue));
}


Обычно я решаю такую рекурсию с публичным API, который не требует параметра индекса и частного API с любой подписью я # d, как это было бы. Для этого я бы разделил его так:

public int summation(int[] numbers) {
 return summation(numbers, numbers.length - 1);
}

private int summation(int[] numbers, int till) {
 return (till < 0) ? 0 : numbers[till] + summation(numbers, till - 1);
}

Обратите внимание, что вы должны проверить till < 0 поскольку это правильно обрабатывает пустой массив.

Другим способом было бы не использовать массив, но любой Iterable:

public int summation(Iterable<integer> numbers) {
 return summation(numbers.iterator());
}

private int summation(Iterator<integer> numbers) {
 return (numbers.hasNext()) ? numbers.next() + summation(numbers) : 0;
}
</integer></integer>

Подсказка: порядок вызовов в numbers.next() + summation(numbers) важен, так как next() вызов next() должен быть выполнен первым.


Использование Java Collections - что-то вроде этого должно дать вам представление об устранении n и рекурсии с точки зрения размера списка:

public int summation( List<integer> list ) {
 return list.isEmpty()
 ? 0
 : list.get( list.size - 1 ) + summation( list.subList( 0 , list.size() - 1 ) );
}
</integer>

Ура,


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

public static int sumToN(int n) {
 if( n == 0 ){
 return 0;
 }
 return n + sumToN(n - 1);
}


public class HelloWorld{


static int sum=0;
static int c;

 public static void main(String []args){

 int[] y={1,2,3,4,5};

 c=y.length;
 System.out.println( summation(y)); //15

 }

 public static int summation(int[] array) {

 c--;
 if(c<0){
 return sum;
 }
 else{
 sum+=array[c];
 return summation(array);

 }
}

}

licensed under cc by-sa 3.0 with attribution.