Обьясните, пожалуйста, как работает данная рекурсия, к примеру, если х принимает 25:
public static int pow(int x) {
if (x==1) {
return 1;
} else {
return pow(x / 2) + 1;
}
}
Методу pow () в процессе работы будут передаваться числа 25 -> 12 -> 6 -> 3 -> 1, пока в качестве аргумента x не будет единица, после чего выполнится return 1;
Далее будет выполнится строка return pow(x/2) + 1; и соответственно возвращаться
2 -> 3 -> 4 -> 5, т.е. результатом функции pow(25) будет 5.
Попробую объяснить по своему:
При вызове этого метода передается параметр типа Integer со значением 25.
Проверяем равно ли оно единице, и если нет то идем в блок else.
Снова вызываем этот же метод но уже передаем значение 25/2 то есть 12
(маленькое объяснение почему 12 : т.к. мы делим целочисленное значение, результат получается так же целочисленное значение, то есть все что после точки отбрасывается)
Опять проверяем равно ли значение единице, и снова вызываем наш метод (т.к. 12 не равно 1) уже со значением 6. Таким образом мы приходим в вызову нашего метода с параметром 1
pow(3/2)+1;
И теперь мы попадаем в блок if и получаем 1.
Возвращаемся на строчку return pow(x / 2) + 1, получается что вот эта часть кода pow(x / 2) нам вернула значение 1, осталось сделать + 1.
Итого: pow(x / 2) + 1 = 2.
Вот что получается:
return pow(25/2) + 1; //второй вызов метода с параметрам 12
pow(12/2) + 1; //третий вызов метода с параметрам 6
pow(6/2) + 1; //четвертый вызов метода с параметрам 3
pow(3/2) + 1; //пятый вызов метода с параметрам 1
Теперь идем в обратном порядке:
Результат 5-го вызова метода равен 2, этот результат мы возвращаем в 4-ый вызов метода и вычисляем уже его результат, получается 3.
Возвращаем результат в 3-ий вызов метода и вычисляем его результат, получается 4.
И на конец возвращаем результат во 2-ой вызов метода, вычисляем его результат и получаем значение 5.
Теперь срабатывает return и возвращается значение 5 (конечный результат) тому кто вызвал этот метод.