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

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

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

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

например, в чем разница между следующими двумя методы:

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

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

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

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

9 115
recursion

9 ответов:

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

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

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

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

и

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

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

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

111

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

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

48

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

17

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

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

13

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

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

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

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

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

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

9

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

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

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

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

6

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

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

6

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

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

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

5

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

рекурсия в функции

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

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

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

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

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

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

в нижней строке

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

3