Я уверен, что полностью понимаю, как работают методы только с одной рекурсией.Двойная рекурсия одним способом Java
Ex) вычисление факториала
public int factorial(int n){ //factorial recursion
if(n==0){
return 1;
}
else{
return n*factorial(n-1);
}
}
Для этих методов, я могу даже представить себе, что происходит в штабеля и какие значения возвращаются на каждом уровне стека.
Но когда я сталкиваюсь с методами с Двойными рекурсиями, начинается кошмар.
Ниже приведена проблема рекурсии с двойными рекурсиями от кодирующей биты.
Ex) Учитывая массив значений ints, можно ли выбрать группу некоторых из int, чтобы группа суммировалась с заданной целью? Если да, то верно. Если нет, false. Вы используете 3 параметра; начальный индекс начало, An int Array nums, target int value target.
Ниже приведено решение этой проблемы.
public boolean groupSum(int start, int[] nums, int target) {
if (start >= nums.length) return (target == 0);
if (groupSum(start + 1, nums, target - nums[start])) return true;
if (groupSum(start + 1, nums, target)) return true;
return false;
}
Мое желание понять это решение. Скажем, мне был присвоен массив {2,4,8} с начальным индексом = 0 и целевым значением 10. Таким образом, (0, {2,4,8}, 10) проходит через метод, функция возвращается -called на
if (groupSum(start + 1, nums, target - nums[start])) return true;
поэтому она становится (1,{2,4,8},8) и он делает снова и снова, пока индекс не достигнет начала
. когда он достигает 3. Стек на последнем уровне (?) переходит ко второму рекурсивному вызову. И здесь я начинаю терять следы происходящего.
Может ли кто-нибудь сломать это для меня? И когда люди используют двойную рекурсию (я знаю, что она очень неэффективна и на практике почти никто не использует ее для своей неэффективности, а просто пытается понять ее). Может ли они на самом деле визуализировать, что произойдет? или они просто используют его, надеясь, что базовый регистр и рекурсия будут работать правильно? Я думаю, что это относится вообще ко всем госзакупках, писавших сортировки слиянием, башни Ханоя alogrithm и т.д ..
Любая помощь очень ценится ..
Вы здесь придумываете терминологию. Это не «двойная рекурсия» - то, что вы показали, является обычной рекурсией. Кроме того, как однажды сказал мудрый человек: «Чтобы понять рекурсию, вы должны сначала понять рекурсию». – vaxquis
ну, наверное, я не понял рекурсии. Поэтому, пожалуйста, просветите меня. – Hello
быть моим гостем: http: // stackoverflow.com/questions/3021/what-is-recursion-and-when-should-i-use-it https://en.wikipedia.org/wiki/Recursion http://stackoverflow.com/questions/126756/examples- рекурсивных функций – vaxquis