Блог

Главная - Вопросы по программированию - Полная разбивка рекурсии Java

Полная разбивка рекурсии Java

#java #recursion

#java #рекурсия

Вопрос:

    ArithmSumRec(n)
1. If n = 1
1.1 return 1
2. Else
2.1 return ArithmSumRec(n-1)   n

Итак, например, мы хотим вычислить, когда n = 5. это будет выглядеть примерно так.

 Executing ArithmSumRec(5) ⇒ 5 calls to ArithmSumRec(...)
ArithmSumRec(5)
ArithmSumRec(4)
ArithmSumRec(3)
ArithmSumRec(2)
ArithmSumRec(1)
return 1 // base case
return 1   2 (= 3)
return 3   3 (= 6)
return 6   4 (= 10)
return 10   5 (= 15)

Но мой вопрос в том, когда метод возвращает первый раз, когда он:

 return  ArithmSumRec(5-1)   5;
  1. Но что происходит с тем 5, который находится за скобками. Почему метод не возвращает 9 (поскольку (5-1) 5 = 9?), а вместо этого возвращает 4? И к чему это n приводит?

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

Комментарии:

1. Подождите, о чем вы спрашиваете? Рекурсия — это вызов метода внутри метода до тех пор, пока не будет удовлетворен параметр ‘stop’

2. Возможно, также опубликуйте функцию ArithmSumRec() целиком.

3. Выражения вычисляются «от начала до конца», более или менее. ArithmSumRec(5-1) 5 точно так же, как ArithmSumRec(4) 5 . Фактически, байт-код, который генерирует javac, будет одинаковым в обоих случаях; javac встроит постоянное выражение 5-1 в just 4 .

4. @DarmaniLink: Да, я знаю, что такое рекурсивный метод, вопрос в том, как он работает для той простой задачи, которую я опубликовал. Что происходит, когда вы создаете рекурсивный метод для вычисления суммы всех целых чисел из 1-5.

5. @yshavit: Но что происходит с 5? Когда код возвращает (n-1) n, почему метод вызывает его самостоятельно только с суммой n-1, а не с общей суммой (n-1) n?

Ответ №1:

Таков порядок операций. Вызов функции имеет приоритет над сложением. Таким образом, когда вы вызываете

 func(5-1)   5

… первая операция равна 5-1, что дает 4. Теперь система времени выполнения выполняет вызов func(4). После этого, наконец, добавляется 5.

Сравните вашу ситуацию с другим вызовом функции:

 sqrt(5-1)   5

Это эквивалентно использованию знака квадратного корня над «5-1″ с помощью » 5″ после всего этого. Это упрощает до sqrt (4) 5 или 7. Она не оценивается как 9 (следуя вашему исходному утверждению в том виде, в каком оно написано), и при этом она не оценивается как 3 (из sqrt (5-1 5)).

Помогает ли это?

Комментарии:

1. Вау, да. Итак, поскольку функция имеет приоритет на (5-1) 5, это будет продолжаться до конца, а ЗАТЕМ встроенное ожидание запуска — это n чисел? Точно так же, как (5*2)(5*1) 3, 3 ожидает вычисления первых двух круглых скобок?

2. Точно! Фактически, именно так я учу этому своих студентов. Все, что указано в круглых скобках, стоит на первом месте — и вызов функции включает круглые скобки, поэтому вам нужно завершить как вычисление (часть 5-1 ), так и вызов функции. Тогда вы можете сделать это последним 5

3. Не знаю, как вас отблагодарить. Действительно оцените это! Приветствия

4. Всегда пожалуйста. Пожалуйста, не забудьте проголосовать за полезные комментарии и ответы (что я уже сделал) и выбрать избранное, чтобы Stack Overflow мог должным образом заархивировать вопрос.

Ответ №2:

Рекурсивные вызовы ничего не возвращают, пока вы не остановите рекурсию. Если бы не было 

 if (n==1) return 1;

программа зависала бы там.

Но когда вы нажимаете return 1, тогда все вычисления понятны, и вы действительно можете вернуть число:

 5   4   3   2   1 = 15