Как легко решать рекурсивные проблемы?
На пути к программированию есть несколько этапов, которые вам нужно преодолеть, чтобы продвинуться вперед. Например, освоение классов, понимание указателей, овладение искусством функционализации кода и т. Д. Одна из самых сложных концепций программирования, которую следует изучить новичкам и освоить для тех, кто уже давно занимается программированием, - это рекурсия.
Когда я впервые начал писать код - почти десять лет назад - я немного боролся с тем, чтобы осмыслить рекурсию. В то время как одни люди могут естественно мыслить рекурсивно, другие - в том числе и я - нет.
Но,
Рекурсивное мышление - это то, чему вы можете научить свой мозг и овладеть им, даже если вы не рождены с этой способностью.
Еще в 2012 году я наткнулся на довольно классную книгу под названием «Думай как программист». Эта книга научила меня развивать мыслительный процесс, который помогал мне решать различные проблемы программирования на протяжении многих лет. Это дало мне основу для правильного мышления, которое программист должен развивать, чтобы преуспеть в своей карьере.
С годами я расширил эти техники, предложенные в книге, чтобы освоиться с различными концепциями программирования.
В этой статье я расскажу вам о различных шагах, которые я использовал для решения любой рекурсивной проблемы. Хотя я буду использовать Python для демонстрации шагов, эти шаги можно применить к любому языку программирования. Их логика не зависит от языка.
Давайте - давайте, давайте, давайте - займемся этим!
Как научить свой разум думать рекурсивно
Чтобы продемонстрировать процесс, возьмем простую задачу. Предположим, нам нужно суммировать цифры любого заданного числа. Например, сумма 123 равна 6, 57190 - 22 и т. Д.
Итак, мне нужно написать код, который решает эту проблему за меня с помощью рекурсии. Прежде чем вы это скажете, я знаю, что есть другие способы решения этой проблемы, которые, возможно, лучше и легче рекурсии. Но для этой статьи давайте рассмотрим рекурсивное решение.
1- Сначала используйте итеративный подход.
Этот шаг относительно прост для большинства людей. У нас есть число, и мы хотим просуммировать его цифры с помощью циклов. По сути, нам нужно знать, как посчитать, сколько цифр в числе, и затем суммировать их одну за другой.
Один из способов сделать это - привести переменную, содержащую число, к str, чтобы упростить итерацию.
num = 123 #The variable containing the number we want to sum its digits num = str(num) #Casting the number to a str s = 0 #Initialize a varible to accumulate the sum #Loop over the digits and add them up for i in range(len(num)): s += int(num[i])
2- Извлеките параметры вашей функции.
Решение проблемы с помощью циклов поможет нам понять ответ и выяснить все его нерекурсивные аспекты. Теперь, когда у нас есть ответ, мы можем проанализировать его и извлечь информацию, которая нам нужна, чтобы двигаться дальше.
На этом этапе нам нужно задать себе вопрос: если бы я написал это в форме функции, какими будут параметры функции?
Ответ на этот вопрос зависит от того, какой язык программирования вы используете. Для Python мы можем сказать, что нам нужен только один параметр, которым является переменная num.
def sumOfDigitsIter(num):
num = str(num)
s = 0
for i in range(len(num)):
s += int(num[i])
return s
3- Вычтите пример минимальной проблемы.
Как только мы получим параметры функции, мы рассмотрим их более подробно. В нашем случае у нас есть только один параметр - num.
Что нам теперь нужно сделать, так это найти экземпляр минимальной проблемы на основе его параметров. Напомним, нашей целью было суммировать цифры данного числа. Самый простой пример этой проблемы - если номер состоит только из одной цифры.
Например, если num = 3, то ответ будет равен самой переменной, так как больше нет цифр для добавления.
4- Добавьте решение к экземпляру минимальной проблемы.
Давайте еще раз посмотрим на функцию, которую мы только что написали:
def sumOfDigitsIter(num):
num = str(num)
s = 0
for i in range(len(num)):
s += int(num[i])
return s
Следуя логике этой функции, если номер параметра состоит только из одной цифры, цикл все равно будет выполняться. Чтобы этого избежать, мы можем добавить условный оператор, который выполняется только в том случае, если количество цифр во входном номере равно единице.
def SumOfDigitsIter(num):
num = str(num)
if len(num) == 1:
return num
else:
s = 0
for i in range(len(num)):
s += int(num[i])
return s
5- Расширьте свою функцию.
Это шаг, на котором происходит рекурсия. До сих пор нас не волновала рекурсия; мы решали проблему логически. Это лучший подход, чтобы начать с рекурсии, подумать об этом логически, а затем преобразовать в рекурсивное решение.
Теперь давайте рассмотрим else раздел нашей функции.
else:
s = 0
for i in range(len(num)):
s += int(num[i])
return s
Вы можете думать о рекурсии как о развертывании проблемного экземпляра и его повторном развертывании. Мы можем взглянуть на эту проблему под другим углом, мы можем сказать, что сумма 123 равна 1 + сумма 23, а сумма 23 равна 2 + сумма 3 - что равно 3.
Таким образом, откат становится суммой 123 = 1 +2 +3 = 6.
Давайте превратим это в код. У нас уже есть последняя написанная часть, которая обрабатывает однозначные числа. Что нам нужно сделать, так это разбить остальные числовые переменные на однозначные числа.
Это рекурсия.
def SumOfDigits2(num): num = str(num) if len(num) == 1: return num else: return num[0] + sumOfDigits(num[1:])
Итак, каждый раз я вызываю одну и ту же функцию, но с меньшим вводом. Как только я дойду до последней цифры, я получу что-то вроде 1 + 2 + 3, что в конечном итоге даст в сумме 6.
И, вуаля, у меня появилась рекурсивная функция.
Другой пример
Давайте рассмотрим другой пример, допустим, мы хотим получить сумму абсолютных различий между двумя списками целых чисел одинаковой длины. Например, если у нас есть [15, -4,56,10, -23] и [14, -9,56,14, -23], то ответ будет 10.
Шаг 1. Решайте петли
assert len(arr1) == len(arr2)
diffSum = 0
for i in range(len(arr1)):
diffSum += abs(arr1[i]-arr2[i])
Шаг 2. Извлеките параметры
список параметров = [arr1, arr2].
Шаг 3. Вычтите минимальный экземпляр
Минимальный случай этой проблемы - когда два списка пусты; в этом случае разницы нет, поэтому ответ будет 0.
Шаг 4. Найдите минимальный экземпляр.
if len(arr1) == 0: return 0
Теперь вы можете спросить, почему вы не сделали так, чтобы len (arr2) == 0 тоже? Оператор assert уже гарантирует, что оба списка имеют одинаковую длину, что означает, что если я хочу проверить, пусты ли они, мне нужно проверить длину только одного из них.
Шаг 5. Рекурсия
Как и в примере с суммой цифр, если я хочу суммировать абсолютную разницу между двумя списками, я могу получить разницу между первыми двумя элементами, а затем вторым, а затем третьим и так далее, пока у меня не закончатся элементы.
def recDiff(arr1,arr2):
assert len(arr1) == len(arr2)
if len(arr1) == 0:
return 0
else:
return abs(arr1[0]-arr2[0]) + recDiff(arr1[1:],arr2[1:])
Выводы
Рекурсия считается одним из передовых методов, которые программист должен пройти на пути к тому, чтобы стать «хорошим программистом». Тем не менее, это может быть довольно сложно поначалу осознать, и многим сложно научиться справляться с этим.
Выполнив пять простых и кратких шагов, вы с легкостью сможете решить любую проблему рекурсии:
- Сначала решите проблему, используя петли.
- Из этого извлеките возможные входные данные, если вы превратите это в функцию.
- Вычтите самый простой вариант проблемы.
- Напишите функцию, которая решает простейший случай этой проблемы.
- Используйте эту функцию, чтобы написать новую рекурсивную функцию.
Хотя я предложил 5 шагов, вам не нужно будет проходить все 5 шагов явно, так как вы станете лучше с точностью. Со временем и практикой вы сможете выполнять некоторые из этих шагов в уме, не записывая их явно.
Я оставлю вас с этим, рекурсивный - одна из сложных концепций программирования, которую нужно освоить. Так что просто придерживайтесь этого, будьте терпеливы и много практикуйтесь; это единственный способ по-настоящему научиться этому.
