О рекурсии для новичков в Java

Question

Итак, у меня есть этот код, который был именно так, как я решил упражнение, которое было предоставлено мне, которое состояло в создании рекурсивной функции, которая получила число, а затем дала вам сумму 1, все числа между ними и ваш номер. Я знаю, что я сделал это звучит странно, но вот пример:

Если я вставил цифру 5, то возвращаемое значение должно было бы быть 15, потому что: 1 + 2 + 3 + 4 + 5 = 15.

С технической точки зрения, мой код работает очень хорошо, но я все еще не понимаю, почему Eclipse заставило меня написать два возвращения, это все, что я хотел бы знать.

Есть ли способ, которым я мог только написать «возврат» один раз?

Answer 1

Конечно, вы можете написать его с помощью только одного возврата:

public static int addNumbers(int value) { 
    if (value > 1) { 
     value += addNumbers(value - 1); 
    } 
    return value; 
} 

Как вы можете видеть, это делается при наличии какой-либо переменной сохраняют бегущего результат, пока вы не дойдете до конца. В этом случае я смог сделать это на месте в value, в других случаях вам может понадобиться создать локальную переменную, но идея сохранения промежуточного результата где-нибудь, пока вы не дойдете до точки возврата, является общей.

Answer 2

Должно быть два возвращения. Ваш первый возврат говорит

if at 1: stop recurstion 

и второй один говорит

continue recursion by returning my value plus computing the value less than me 

Вы могли бы объединить их с помощью тройного:

return value == 1 ? value : value + addNumbers(value - 1) 

Но это не читаемыми.

Рекурсивные Funtions как

• последовательности Fibbonacci в
• Фракталы
• Etc.

Используйте себя несколько раз, потому что они содержат себя.

Answer 3

Из википедии на рекурсии:

В математике и информатике, класс объектов или методов демонстрируют рекурсивное поведение, когда они могут быть определены двумя свойствами:

1. Простой базовый регистр (или случаи) - сценарий прекращения, который не использует рекурсию для получения ответа

2. Набор правил, которые уменьшают все остальные ca SES в стороне базового случая

Есть два возвращения, потому что вы должны обрабатывать два случая выше. В вашем примере:

Базовый корпус value == 1.

Корпус для уменьшения всех остальных корпусов к корпусу основания составляет value + addNumbers(value-1);.

Источник: https://en.wikipedia.org/wiki/Recursion#Formal_definitions

Конечно, есть и другие способы, чтобы написать это, в том числе того, которые не требуют несколько возвращения, но в целом несколько возвращений является ясным и нормальным способом выразить рекурсию из-за путями рекурсии естественно попадает в несколько случаев.

Answer 4

Рекурсивные функции всегда имеют как минимум 2 пути, нормальные, которые будут рекурсивно, и возвращаемые пути «end» (обычно константа).

Вы можете, однако, сделать что-то вроде этого:

public static int addNumbers(int value) { 
    if (value != 1) 
     value = value + addNumbers(value-1); 
    return value; 
} 

Но я не могу сказать, что я думаю, что это гораздо лучше (Некоторые люди, как раздражен на изменение параметров, как они делают в нескольких возвратов). Конечно, вы могли бы создать новую переменную и установить ее на одно значение или другое, но тогда кто-то расстроится, потому что вы использовали слишком много строк кода и ненужную переменную. Добро пожаловать в программирование :) Ваш исходный код, вероятно, так хорош, как вы, вероятно, получите.

Что касается того, почему «Eclipse» сделал это с вами, это на самом деле Java - Java лучше, чем большинство языков, при условии, что вы не сделали что-то явно неправильное как можно скорее (в этом случае, пока вы печатаете ожидающих вас для компиляции). Он обнаружил, что одна ветка вашего if вернула значение, а другая - нет, что явно неверно.

Java также очень ярок, заставляя вас использовать инструкцию «return», где другой язык может позволить вам уйти с меньшим количеством. В Groovy Вы бы соблазн устранить возвращение и написать что-то вроде:

def addNumbers(value){value + (value-1?0:addNumbers(value-1))} 

просто для удовольствия, но я, конечно, не назвал бы более удобным для чтения! Java просто показывает, что лучше заставить вас быть явным в большинстве случаев.

Answer 5

Как роботов Азимова, все рекурсивные алгоритмы должны подчиняться три важных закона:

1. Рекурсивный алгоритм должен иметь базовый случай.
2. Рекурсивный алгоритм должен изменить свое состояние и перейти к базовому регистру.
3. Рекурсивный алгоритм должен называть себя рекурсивно.

Ваш if (value == 1) return value; оператор возврата является базовый случай. Именно тогда прекращается рекурсия (вызов себя). Когда происходит вызов функции, компилятор подталкивает текущее состояние в стек, а затем выполняет вызов. Таким образом, когда этот вызов возвращает некоторое значение, он вытягивает значение из стека, вычисляет и возвращает результат на верхний уровень. Вот почему для другого оператора возврата.

Придумайте это как разбивая вашу проблему:

addNumbers(3) = 3 + addNumbers(2) (this is returned by second one) 
         -> 2 + addNumbers(1) (this is returned by second one) 
           -> 1 (this is returned by base case) 

Answer 6

Не стесняйтесь, поправьте меня, если я ошибаюсь, но я не думаю, что есть способ, чтобы устранить одну из этих возвращений, если вы не решите поставить переменную вне метода или изменить метод на рекурсивный.

В java метод, возвращающий значение, ДОЛЖЕН вернуть значение в какой-то момент, независимо от того, какой код внутри него делает. Причина, по которой eclipse требует, чтобы вы добавили второй возврат, потому что первый возврат выполняется только в том случае, если оператор if равен true. Если у вас не было второго возврата, и если оператор if не стал истинным, java не сможет оставить этот метод и не имеет понятия, что делать, таким образом, eclipse потребует от вас добавления возврата утверждение после этого оператора if.

Эти типы ошибок называются проверенными ошибками или ошибками компиляции. Это означает, что eclipse буквально не может преобразовать ваш код в исполняемый файл, потому что он не знает, как; есть синтаксическая ошибка, или вам не хватает возврата и т. д.