Является ли рекурсия особенностью сама по себе?

Ответ 1

Чтобы ответить на ваш конкретный вопрос: Нет, с точки зрения изучения языка рекурсия не является особенностью. Если ваш профессор действительно состыковал вас за использование "функции", которую он еще не преподавал, это было неправильно.

Чтение между строками, одна из возможностей заключается в том, что с помощью рекурсии вы избегали использования функции, которая должна была стать результатом обучения для его курса. Например, возможно, вы вообще не использовали итерацию, или, возможно, вы использовали только циклы for вместо использования как for, так и while. Как правило, назначение предназначено для проверки вашей способности делать определенные вещи, и если вы избегаете их выполнения, ваш профессор просто не сможет предоставить вам отмеченные для этой функции отметки. Однако, если это действительно было причиной ваших потерянных оценок, профессор должен считать это своим опытом обучения самостоятельно, если демонстрация определенных результатов обучения является одним из критериев задания, которые должны быть четко объяснены студентам.

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

Переполнение стека

Более очевидным является то, что вы рискуете получить ошибку. Реально, метод, который вы написали, вряд ли фактически приведет к одному, поскольку пользователю придется многократно вводить неверный ввод, чтобы фактически вызвать переполнение стека.

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

Это часть более общего принципа в разработке программного обеспечения, называемом абстракцией. По сути, когда вы вызываете DoThing(), все, что вам нужно позаботиться, это то, что Thing сделано. Вам не нужно беспокоиться о деталях реализации того, как это делается. Но жадное использование стека нарушает этот принцип, потому что каждый бит кода должен беспокоиться о том, сколько стека он может с уверенностью предположить, что он остался ему по коду в другом месте в цепочке вызовов.

читаемость

Другая причина - читаемость. Идеал, к которому должен стремиться код, - быть человеком, читаемым документом, где каждая строка описывает просто то, что он делает. Возьмите эти два подхода:

private int getInput() {
    int input;
    do {
        input = promptForInput();
    } while (!inputIsValid(input))
    return input;
}

против

private int getInput() {
    int input = promptForInput();
    if(inputIsValid(input)) {
        return input;
    }
    return getInput();
}

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

Я буду запрашивать ввод до тех пор, пока вход не будет действителен, а затем вернет его

против

Я буду запрашивать ввод, тогда, если вход будет действительным, я верну его, иначе я получу вход и верну его результат

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

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

Ответ 2

Чтобы ответить на личный вопрос, а не на мета-вопрос: рекурсия - это функция, в том смысле, что не все ее компиляторы и/или языки обязательно разрешают. На практике это ожидается от всех (обычных) современных компиляторов - и, конечно же, всех компиляторов Java! - но это не повсеместно.

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

Для такого компилятора, когда вы вызываете такую ​​функцию

a();

он реализован как

move the address of label 1 to variable return_from_a
jump to label function_a
label 1

и определение a(),

function a()
{
   var1 = 5;
   return;
}

реализуется как

label function_a
move 5 to variable var1
jump to the address stored in variable return_from_a

Надеюсь, проблема, когда вы пытаетесь вызвать a() рекурсивно в таком компиляторе, очевидна; компилятор больше не знает, как вернуться из внешнего вызова, потому что адрес возврата был перезаписан.

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

Ищем вперед, я могу представить себе специализированные сценарии - сильно параллельные системы, возможно, когда не нужно предоставлять стек для каждого потока, может быть выгодным, и поэтому рекурсия разрешена только в том случае, если компилятор может реорганизовать его в цикл. (Конечно, примитивные компиляторы, о которых я говорил выше, не были способны выполнять сложные задачи, такие как рефакторинг кода.)

Ответ 3

Учитель хочет знать, учились ли вы или нет. Очевидно, вы не решили проблему так, как он учил вас (хороший путь, итерация), и, таким образом, считает, что вы этого не сделали. Я все для творческих решений, но в этом случае я должен согласиться с вашим учителем по другой причине:
Если пользователь вводит недопустимый ввод слишком много раз (т.е. Сохраняя ввод нажатым), у вас будет переполнение стека исключение, и ваше решение выйдет из строя. Кроме того, итеративное решение более эффективно и проще в обслуживании. Я думаю, что причина, по которой ваш учитель должен был дать вам.

Ответ 4

Вычитание очков, потому что "мы не рассматривали рекурсию в классе", ужасно. Если вы узнали, как вызвать функцию A, которая вызывает функцию B, которая вызывает функцию C, которая возвращает обратно в B, которая возвращается обратно в A, которая возвращается обратно вызывающему, и учитель явно не сказал вам, что это должны быть разные функции (которые будет иметь место в старых версиях FORTRAN, например), нет никаких оснований полагать, что A, B и C не могут быть одной и той же функцией.

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

Ответ 5

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

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

Нет никакой разницы между этими двумя примерами, которые вы упомянули в своем вопросе, в смысле того, что они делают (но отличаются друг от друга). В обоих случаях в стек загружается адрес возврата и вся информация об методе. В рекурсивном случае обратный адрес - это просто строка сразу после вызова метода (конечно, это не то, что вы видите в самом коде, а скорее в коде, который создал компилятор). В Java, C и Python рекурсия довольно дорога по сравнению с итерацией (в общем), потому что для этого требуется выделение нового стекового кадра. Не говоря уже о том, что вы можете получить исключение, если вход недействителен слишком много раз.

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

ИМХО, я думаю, профессор прав, вычитая вам очки. Вы могли бы легко принять часть проверки другим способом и использовать его следующим образом:

public bool foo() 
{
  validInput = GetInput();
  while(!validInput)
  {
    MessageBox.Show("Wrong Input, please try again!");
    validInput = GetInput();
  }
  return hasWon(x, y, piece);
}

Если то, что вы сделали, действительно может быть разрешено таким образом, то то, что вы сделали, было плохой практикой, и его следует избегать.

Ответ 6

Возможно, ваш профессор еще не научил этому, но похоже, что вы готовы изучить преимущества и недостатки рекурсии.

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

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

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

Ответ 7

Что касается конкретного вопроса, это рекурсия, я склонен сказать "да", но после повторной интерпретации вопроса. Существуют общие варианты выбора языков и компиляторов, которые делают рекурсию возможной, а существующие языки Turing существуют которые вообще не позволяют рекурсию. Другими словами, рекурсия - это способность, которая разрешена определенными вариантами в дизайне языка/компилятора.

• Поддержка первоклассных функций позволяет рекурсию при очень минимальных предположениях; см. пишущие петли в Unlambda для примера, или это тупое выражение Python, не содержащее самореференций, циклов или назначений:

  >>> map((lambda x: lambda f: x(lambda g: f(lambda v: g(g)(v))))(
  ...   lambda c: c(c))(lambda R: lambda n: 1 if n < 2 else n * R(n - 1)),
  ...   xrange(10))
  [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
  

• Языки/компиляторы, которые используют late binding, или которые определяют форвардные декларации, сделать рекурсию возможной. Например, хотя Python позволяет использовать приведенный ниже код, выбор дизайна (поздняя привязка), а не требование для Turing-complete. Взаимно рекурсивные функции часто зависят от поддержки форвардных объявлений.

  factorial = lambda n: 1 if n < 2 else n * factorial(n-1)
  

• Статически типизированные языки, которые позволяют рекурсивно определенные типы способствуют рекурсии. См. Эту реализацию Y Combinator в Go. Без рекурсивно-определенных типов все же можно было бы использовать рекурсию в Go, но я считаю, что Y Combinator было бы невозможно.

Ответ 8

Из того, что я могу вывести из вашего вопроса, использование рекурсивной функции для запроса ввода в случае сбоя ввода не является хорошей практикой. Почему?

Потому что каждый вызов рекурсивных функций попадает в стек. Поскольку эта рекурсия управляется пользовательским вводом, возможно иметь бесконечную рекурсивную функцию и, таким образом, вывести /fooobar.com/...:-p

Наличие нерекурсивного цикла для этого - путь.

Ответ 9

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

Рекурсия как функция

В простом выражении Java поддерживает его неявно, поскольку он позволяет использовать метод (который является в основном специальной функцией) для "знания" самого себя и других методов, составляющих класс, к которому он принадлежит. Рассмотрим язык, где это не так: вы могли бы написать тело этого метода a, но вы не смогли бы включить в него вызов a. Единственным решением было бы использовать итерацию для получения того же результата. На таком языке вам нужно будет провести различие между функциями, осознающими их собственное существование (используя специальный токен синтаксиса), и тем, кто этого не делает! Фактически, вся группа языков делает это различие (см. Lisp и ML, например). Интересно, что Perl даже разрешает анонимные функции (так называемые lambdas) называть себя рекурсивно (опять же, с выделенным синтаксисом).

нет рекурсии?

Для языков, которые даже не поддерживают возможность рекурсии, часто существует другое решение в виде Комбинатор с фиксированной точкой, но он по-прежнему требует, чтобы язык поддерживал функции как так называемые объекты первого класса (т.е. объекты, которые можно манипулировать внутри самого языка).

Рекурсия как практика

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

• Синтаксис по-прежнему не очень рекурсивный.
• компиляторы не смогут обнаружить эту практику и оптимизировать ее

Нижняя строка

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