КОДЕКС

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

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

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

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

Я начал свое объяснение ему с небольшой теории:

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

Рекурсивная функция должна иметь условие завершения.

Любой алгоритм рекурсии может быть реализован итеративно и наоборот.

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

public int Fib(int n)
{
   if (n == 0 || n == 1) return n;
   else return Fib(n - 1) + Fib(n - 2);
}
for (int i = 0; i < 100; i++)
{
    Console.WriteLine(Fib(i));
}

Я много раз вызывал метод Фибоначчи с разными входными данными. Я показал, как меняется переменная n. Но я довольно быстро понял, что пример Фибоначчи непрост для новичка, потому что моя реализация содержала два вызова методов.

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

public int Sum(int n)
{
    if (n == 1) return 1;
    else return n + Sum(n - 1);
}

Мы продолжили отладку кода. Я прокомментировал процесс как мог. Я начал думать, что сейчас все станет лучше, но когда я попросил студента переписать этот пример кода для вычисления факториала n вместо суммы, он понятия не имел, как это сделать.

Потом у нас был такой диалог:

  • Я: Что именно вам непонятно?
  • Он: Я не понимаю поток выполнения, который я вижу в отладчике. Почему отладчик прыгает между открытой круглой скобкой и строкой «else return» n раз, а затем перескакивает между строка «else return» и закрывающая скобка n раз?
  • Я: Но вы уже знаете, что метод может вызывать другой метод? Например, метод Main может вызывать метод PrintMessage.
  • Он: Конечно! Я это знаю.
  • Я: Рекурсия также включает вызов одного метода из другого. Единственная разница в том, что вызывается копия (!) Исходного метода. Вы можете заменить любой алгоритм рекурсии набором идентичных методов с разными именами, например:
public int Sum_Orininal(int n)
{
    if (n == 1) return 1;
    else return n + Sum_Copy1(n - 1);
}
public int Sum_Copy1(int n)
{
    if (n == 1) return 1;
    else return n + Sum_Copy2(n - 1);
}
public int Sum_Copy2(int n)
{
    return 1;
}
  • Я: этот громоздкий код эквивалентен рекурсивному коду, но он может вычислять только сумму от 1 до 3. Чтобы вычислить сумму от 1 до 4, вы должны скопировать и вставить метод или использовать единственный рекурсивный метод, который может корректно работать на любом входе. Думайте о рекурсии как о потрясающей оптимизации этого дублированного кода.

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

Затем я дал ему следующее практическое задание. Я попросил визуализировать вызовы рекурсии. И вот что у меня получилось через 5–10 минут:

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

Через некоторое время он поделился со мной своей статистикой - было решено более 17 рекурсивных задач.