Является ли увеличение аргумента функции хорошим способом обновить «счетчик» с помощью рекурсии?
Я практикуюсь с рекурсией и смотрю на вопрос:
"Напишите рекурсивную программу, входными данными которой являются массив A и число x. Программа должна вывести количество вхождений x в A".
Это мое рабочее решение:
public int countOccurrencesOfX_Recursive(int[] array, int x, int index, int occurrences) {
if (index == array.length) {
return occurrences;
}
if (array[index] == x) {
return countOccurrencesOfX_Recursive(array, x, index+1, occurrences+1);
} else {
return countOccurrencesOfX_Recursive(array, x, index+1, occurrences);
}
}
Я не мог придумать другого способа сделать это без введения дополнительных аргументов функций. Это не кажется замечательным, потому что это зависит от аргумента вхождения, установленного на 0, но пользователь может ввести любое целое число, которое ему нравится. Мой вопрос в том, считается ли это хорошим способом ведения счетчика при использовании рекурсии, а если нет, то как бы вы это сделали?
Ответы 3
Обычное решение этой проблемы состоит в том, чтобы иметь нерекурсивную функцию публичный, которую вызывают ваши пользователи, которая, в свою очередь, вызывает рекурсивную функцию частный.
Например:
public static int recursiveCount(int[] array, int value) {
return recursiveCountInternal(array, value, 0, 0);
}
private static int recursiveCountInternal(int[] array, int value, int index, int count) {
if (index == array.length) {
return count;
}
if (array[index] == value) {
count++;
}
return recursiveCountInternal(array, value, index + 1, count);
}
На самом деле это можно сделать одним методом без переменной count в качестве одного из параметров.
Я видел этот стиль рекурсии раньше, и он выглядит нормально.
Что вы можете сделать, так это создать перегруженную функцию, которая просто вызывает эту функцию с начальным значением occurrences, равным 0, например:
public int countOccurrencesOfX_Recursive(int[] array, int x, int index) {
return countOccurrencesOfX_Recursive(array, x, index, 0);
}
и сделать рекурсивную функцию приватной. Это избавит вас от опасений, что пользователи введут любое число.
Вы можете вернуть 1+результаты из остальной части строки.
private static int countOccurencesofIntInarrayRec(Integer[] nums, int target){
if (nums == null || nums.length==0) return 0;
int addNum = nums[0]==target?1:0;
return countOccurencesofIntInarrayRec(Arrays.copyOfRange(nums, 1, nums.length),target) + addNum;
}
Это здорово, только что изменил свое решение на то же самое, что вы только что опубликовали :) это отличный совет, приветствую человека