Написание рекурсивного метода немного похоже на составление плана по выстраиванию домино и выбиванию их из строя. Вы должны предвидеть, как каждый отдельный рекурсивный вызов (домино) добавит свою часть к выполнению всей задачи.
Это означает, что «мясо» рекурсивного метода находится не в рекурсивной части, а в «конечных случаях» - частях кода, которые выполняются, когда вы не собираетесь повторно вызывать метод, последнее домино в цепочке, которую вы нажимаете, чтобы начать веселье.
Итак, давайте посмотрим на ваш первый пример, рекурсивная программа для (целочисленного) деления. Алгоритм деления, который вы пытаетесь реализовать, "для положительных d и n, пусть n (0) будет n. Продолжайте вычитать d из n (i) шаг за шагом, пока на каком-то шаге q n (q) не станет меньше d . Ваш ответ q. "
Ключ в том, чтобы сначала взглянуть на случай КОНЦА. Что если в начале n уже меньше d? Затем вы сделали «ноль шагов», поэтому ваш результат деления равен 0.
В псевдокоде:
int divide(int n, int d) {
if (n < d) {
return 0;
}
....
}
А что если n не меньше d (больше или равно d)? Затем мы хотим попробовать еще один шаг в процессе деления с меньшим n. То есть снова запустите функцию деления с «тем же d» и n = «старое n» - d. Но как только это разделение заканчивается, оно только говорит нам, сколько шагов вычитания потребовалось для (n-d) / d. Мы знаем, что н / д требует еще один шаг. Таким образом, мы должны добавить этот шаг к результату:
int divide(int n, int d) {
if (n < d) {
return 0;
} else {
return divide( n-d, d ) + 1;
}
}
Что на самом деле говорит это второе возвращение? Он говорит: «Я не знаю, как вычислить результат сам, но я знаю, что он ОДИН БОЛЬШЕ, чем результат для функции« делить (nd, d) »). Поэтому я передам этот метод вызову» а затем просто добавьте один к тому, что он мне вернет. "
И процесс продолжается. Мы продолжаем добавлять домино «делить» в цепочку, пока не достигнем операции деления, где n «сжалось», чтобы быть меньше, чем d ... наш конечный случай, наш нулевой результат. Теперь мы опрокидываем первое домино (последнее, которое мы добавили в цепочку), возвращая «0». И домино начинают падать. Каждый раз, когда одно домино опрокидывает другое домино, мы добавляем «1» к результату метода, пока, наконец, первый вызов метода не станет последним падением домино, и он вернет результат деления.
Давайте попробуем несколько примеров:
12/18
разрыв (12,18)
---> возвращает 0, поскольку 12 меньше 18
результат равен 0.
* * Тысяча двадцать восемь 20/5:
divide(20, 5)
---> returns divide(20-5, 5) + 1
------> returns divide(15-5, 5) +1
---------> returns divide(10-5, 5) +1
------------> returns divide(5-5, 5) +1
---------------> returns 0, since 5-5 is 0, which is less than 5
and now the dominoes fall...
------------> returns 0 + 1
---------> returns 1 + 1
------> returns 2 + 1
---> returns 3 + 1
result is 4.
* +1032 * 8/3:
divide(8, 3)
---> returns divide(8-3, 3) + 1
------> returns divide(5-3, 3) +1
---------> returns 0, since 5-3 is 2, which is less than 3
and now the dominoes fall...
------> returns 0 + 1
---> returns 1 + 1
result is 2.