Борьба с построением интуиции для рекурсии - PullRequest
Новая
       13

Борьба с построением интуиции для рекурсии

0 голосов
/ 28 апреля 2020

Хотя я изучил и смог понять некоторые программы в рекурсии, я все еще не в состоянии интуитивно получить решение с помощью рекурсии, как я легко использую Итерацию. Есть ли какой-нибудь курс или трек, чтобы построить интуицию для рекурсии? Как овладеть концепцией рекурсии?

1 Ответ

0 голосов
/ 29 апреля 2020

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

Рекурсия - это способ разбить, казалось бы, сложные проблемы на более мелкие части. Рассмотрим тривиальный пример факториальной функции. 

def factorial(n):
    if n < 2:
        return 1
    return n * factorial(n - 1)

Например, для вычисления factorial(100) все, что вам нужно, это вычислить factorial(99) и умножить 100. Это следует из знакомого определения факториала.

Вот несколько советов по созданию рекурсивного решения:

  • Предположим, вы знаете результат, возвращаемый непосредственно предшествующим рекурсивным вызовом (например, при вычислении factorial(100), предположим, вы уже знать значение factorial(99). Как вы go оттуда?)
  • Рассмотрите базовый случай (т. е. когда рекурсия остановится?)

первый пункт может показаться довольно абстрактным, но все это означает следующее: большая часть работы уже выполнена. Как вы go оттуда, чтобы выполнить задачу? В случае факториала factorial(99) составляли эту большую часть работы. Во многих случаях вы обнаружите, что выявление этой части работы просто равнозначно проверке аргумента функции (например, n в факториале) и предположению, что у вас уже есть ответ на func(n - 1).

Вот еще один пример для конкретности. Допустим, мы хотим перевернуть строку без использования встроенных функций. При использовании рекурсии мы могли бы предположить, что string[:-1], или подстрока до самого последнего символа, уже была обращена. Затем все, что нужно, это поместить последний оставшийся символ впереди. Используя это вдохновение, мы можем прийти к следующему рекурсивному решению: 

def my_reverse(string):
    if not string: # base case: empty string
        return string # return empty string, nothing to reverse
    return string[-1] + my_reverse(string[:-1])

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

...