Является ли рекурсия функцией сама по себе?

... или это просто практика?

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

Я спрашиваю здесь, потому что подозреваю, что у кого-то есть окончательный ответ.

Например, в чем разница между двумя способами:

public static void a() {
    return a();
    }

public static void b() {
    return a();
    }

Помимо « aпродолжается вечно» (в реальной программе он используется правильно, чтобы снова запрашивать пользователя при вводе неверных данных), есть ли какое-либо фундаментальное различие между aиb ? Чем по-другому они обрабатываются для неоптимизированного компилятора?

В конечном итоге все сводится к тому, научились ли мы, учась return a()от bэтого, return a()от чего a. А мы?

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

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

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

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

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

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

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

читабельность

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

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();
}

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

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

против

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

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

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

Чтобы ответить на буквальный вопрос, а не на мета-вопрос: рекурсия - это особенность в том смысле, что не все компиляторы и / или языки обязательно допускают это. На практике это ожидается от всех (обычных) современных компиляторов - и, конечно, от всех компиляторов 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-х, я думаю) без поддержки рекурсии, проблема была немного более тонкой, чем это: адрес возврата будет храниться в стеке, как и в современных компиляторах, но локальные переменные не были «т. (Теоретически это должно означать, что рекурсия была возможна для функций без нестатических локальных переменных, но я не помню, поддерживал ли это компилятор явно или нет. По какой-то причине ему могли потребоваться неявные локальные переменные.)

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

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

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

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

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

Из того, что я могу вывести из вашего вопроса, использование рекурсивной функции для запроса ввода в случае сбоя ввода не является хорошей практикой, поскольку каждый вызов рекурсивных функций попадает в стек. Поскольку эта рекурсия управляется пользовательским вводом, можно иметь бесконечную рекурсивную функцию, что приводит к 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);
}

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

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

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

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

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

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

• Поддержка первоклассных функций делает возможной рекурсию при минимальных предположениях; см. в качестве примера написание циклов в 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]
  

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

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

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

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

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

Для этого нужно иметь нерекурсивный цикл.

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

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

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

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

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

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

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

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

Суть

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