Простая рекурсия?

Question

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

"Определите процедуру плюс, которая принимает два неотрицательных целых числа и возвращает их сумму. Единственные процедуры (кроме рекурсивных вызовов плюса), которые вы можете использоватьявляются: ноль ?, sub1 и add1.

Я знаю, что это встроенные функции в схеме, поэтому я знаю, что их можно решить, я просто не понимаю, как. Рекурсия такая хитрая!

Любая помощь будет принята с благодарностью! =] Спасибо

Я работаю в схеме Petite Chez (с редактором SWL)

Answer 1

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

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

Итак. считать вас числами как два ведра. У каждого из них есть 10 камней. Вы хотите «сложить» эти два ведра вместе. Вам разрешается перемещать только один камень за раз (то есть вы не можете взять горсть или опрокинуть одно ведро в другое).

Допустим, вы хотите переместить все из левого ведра в правое ведро, по одному камню за раз. Что ты собираешься делать?

Сначала вы должны взять 1 камень из левого ведра, т. Е. Вы используете sub1 для удаления одного камня из ведра. Затем вы добавляете тот же камень в правое ведро, то есть вы add1 в правое ведро.

Теперь вы можете сделать это в цикле, но вы не знаете, сколько камней будет в любом данном решении. Что вы действительно хотите сделать, так это сказать: «Возьмите один камень из левого ведра, положите его в правое ведро и повторяйте, пока в левом ведре не останется камней». Этот случай отсутствия камней в левом ведре называется «Базовый случай». Это тот момент, когда вы говорите «ОК», я закончил.

Примером такой ситуации может служить псевдокод (используя ваш плюс, add1, sub1 и ноль):

plus(leftBucket, rightBucket)
{
  if(leftBucket == zero) // check if the left bucket is empty yet
  {
    // the left bucket is empty, we've moved all the stones
    return rightBucket; // the right bucket must be full
  }
  else 
  {
    // we still have stones in the left bucket, remove 1, 
    // put it in the right bucket, repeat.
    return plus(sub1(leftBucket), add1(rightBucket)); 
  }
}

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

Answer 2

Рекурсия - это просто функция, которая вызывает сама себя. Наиболее распространенные, легко понятные примеры рекурсии - это обход структуры данных, которая выглядит как дерево.

Как бы вы посетили каждую ветку дерева? Вы начинаете со ствола и вызываете визит (ветку), передавая ствол дерева в качестве первой ветки. Visit () вызывает себя для каждой ветви каждой ветви и т. Д.

public void visit(Branch branch)
{
    // do something with this branch here

    // visit the branches of this branch
    foreach(var subbranch in branch.branches)
    {
        visit(subbranch)
    }
}

Answer 3

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

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

---

Хорошо, у нас есть базовый случай: когда одно из чисел равно нулю.

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

Итак, мы знаем, что (+ n 0) равно n.Итак, теперь для нашего рекурсивного шага мы хотим взять произвольный вызов (+ x y) и превратить его в вызов, который на ближе к нашему идеальному (+ n 0).Таким образом, мы добились некоторого прогресса и в конечном итоге решим нашу проблему.

Так как мы собираемся это сделать?

---

(+ x y), конечно, эквивалентно (+ (add1 x) (sub1 y)) - что приближает нас к нашему базовому случаю (zero? y).

Это дает нам окончательное решение:

(define (+ x y)
  (if (zero? y)
    (x)
    (+ (add1 x) (sub1 y))
))

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

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