Рекурсивно програмиране

Как да разрешите проблем, като се преструвате, че вече имате

Въпреки че често се въвежда в началото на повечето начинания в програмирането, концепцията за рекурсия може да изглежда странна и потенциално отблъскваща при първата среща с нея. Изглежда почти парадоксално: как можем да намерим решение на проблем, използвайки решението на същия проблем?

За тези, които се опитват да се справят с концепцията за рекурсия, често смятам, че може да е полезно първо да осъзнаят, че рекурсията е нещо повече от програмна практика - това е философия за решаване на проблеми, която е подходяща за проблеми, върху които може да се работи и частично решен, оставяйки останалата част от проблема в същата форма, но по-лесна или по-малка по някакъв начин. Това не се отнася само за функциите в програмирането; можем да рамкираме прости ежедневни проблеми с помощта на рекурсия. Например, вземете ме, пиша тази публикация: да речем, че искам да е дълга около 1000 думи, ако се стремя да напиша 100 думи всеки път, когато я отворя, тогава първия път, когато напиша 100 думи, и си оставя 900 думи остана да пише. Следващия път пиша 100 думи и ми остават само 800. Мога да продължа това, докато не ми останат 0 думи за писане. Всеки път решавам частично проблема, а останалият проблем се намалява.

Кодът за писане на публикацията ми може да изглежда така:

write_words(words_left):
  if words left > 0:
    write_100_words()
    words_left = words_left - 100
    write_words(words_left)

Бих могъл също да приложа този алгоритъм итеративно:

write_words(words_left):
  while words_left > 0:
    write_100_words()
    words_left = words_left - 100

Ако преминете през извикването на функцията write_words(1000) с която и да е реализация, ще откриете, че те имат абсолютно същото поведение. Всъщност, всеки проблем, който можем да решим с помощта на рекурсия, можем да решим и с помощта на итерация (for и while цикли). Така че защо изобщо бихме избрали да използваме рекурсия?

Защо рекурсия?

Вярвате или не, след като се справим с това, някои проблеми са по-лесни за решаване с помощта на рекурсия, отколкото с итерация. Понякога рекурсията е по-ефективна, а понякога е по-четима; понякога рекурсията не е нито по-бърза, нито по-четима, но по-бърза за изпълнение. Има структури от данни, като дървета, които са много подходящи за рекурсивни алгоритми. Има дори някои езици за програмиране без концепция за цикъл - чисто функционални езици като Haskell зависят изцяло от рекурсия за итеративно решаване на проблеми. Въпросът е прост: не е нужно да разбирате рекурсията, за да сте програмист, но трябва да разбирате рекурсията, за да станете добърпрограмист. Всъщност бих стигнал дотам, че да кажа, че разбирането на рекурсията е част от това да си добър решаващ проблеми, като оставим настрана програмирането!

Същността на рекурсията

Като цяло с рекурсията се опитваме да разделим по-сложен проблем на проста стъпка към решението и остатък, който е по-лесна версия на същия проблем. След това можем да повторим този процес, като правим една и съща стъпка към решението всеки път, докато стигнем до версия на нашия проблем с много просто решение (наричано базов случай). Простото решение на нашия основен случай, съчетано със стъпките, които предприехме, за да стигнем до там, след това формира решение на първоначалния ни проблем.

Да предположим, че са ни дадени действителни данни от някакъв тип данни, наречете го dₒ. Идеята с рекурсията е да се преструваме, че вече сме решили проблема или сме изчислили желаната функция f за всички форми на този тип данни, които са по-прости от dₒ според някаква степен > на трудност, която трябва да дефинираме. Тогава, ако можем да намерим начин да изразим f(dₒ) по отношение на едно или повече f(d)s, където всички тези d s са по-малко трудни (имат по-малка степен) от dₒ, тогава намерихме начин да намалим и решим за f(dₒ) . Повтаряме този процес и се надяваме, че в даден момент останалите f(d)sще станат толкова прости, че можем лесно да приложим фиксирано, затворено решение за тях. След това нашето решение на първоначалния проблем ще се разкрие, докато нашите решения на прогресивно по-прости проблеми се събират и каскадно се връщат обратно към върха.

В горния пример за писане на тази публикация, данните са текстът, съдържащ се в този документ, който чака да бъде написан, а степента на трудност е дължината на документа. Това е малко измислен пример, но ако приемем, че вече съм решил проблема f(900)за това как да напиша 900 думи, тогава всичко, което трябва да направя, за да реша f(1000) е да напиша 100 думи и след това да изпълня моето решение за 900 думи, f(900).

По-добър пример се намира при разглеждането на числата на Фибоначи, където първото число на Фибоначи е 0, второтое 1 и nᵗʰ числото на Фибоначи е равно на сумата от предишните две. Да приемем, че имаме функция на Фибоначи, която ни казва nᵗʰ числото на Фибоначи:

fib(n):
  if n == 0:
    return 0
  if n == 1:
    return 1
  else:
    return fib(n-1) + fib(n-2)

Как изглежда изпълнението на тази функция? Да опитаме fib(4) :

Полезна мантра, която да възприемете, когато решавате проблеми рекурсивно, е „фалшифицирайте го, докато не успеете“, тоест преструвайте се, че вече сте решили проблема за по-прост случай, и след това се опитайте да намалите по-големия проблем да използвате решението за този по-прост случай. Ако даден проблем е подходящ за рекурсия, всъщност трябва да има само малък брой прости случаи, които трябва изрично да разрешите, т.е. този метод за редуциране до по-прост проблем може да се използва за решаване на всеки друг случай. Това е илюстрирано в примера на Фибоначи fib, където, за да дефинираме fib(n), ние просто действаме така, сякаш вече сме изчислили fib(n-1) и fib(n-2) и, както се надявахме, това каскадира и намалява проблема до прогресивно по-прости случаи, докато стигнем до fib(0) и fib(1), които са коригирани и лесни решения.

Рекурсивна стратегия

Рекурсията е донякъде нюансирана и наистина зависи от проблема, който се опитвате да разрешите. Има обаче някои общи стъпки, които можем да измислим и които повече или по-малко могат да ни отведат в правилната посока. Тази стратегия се съдържа в три стъпки:

  1. Поръчайте вашите данни
  2. Разрешете малките казуси
  3. Решете големите казуси

Както казах преди, мисля, че може да бъде полезно да пренесем пример, докато учим, но не забравяйте, че рекурсията зависи от проблема и затова се опитайте да се съсредоточите върху общите принципи тук. Ще използваме простия пример за обръщане на низ, т.е. искаме да напишем функцията reverse така, че reverse('Hello world') = 'dlrow olleH'. Бих препоръчал да се върнете и да видите как тези стъпки се прилагат към функцията на Фибоначи и след това да ги вземете и да ги изпробвате на някои други примери (има много упражнения онлайн).

Поръчайте вашите данни

Тази стъпка е абсолютно ключът към започване на рекурсивното решаване на проблем и въпреки това често се пренебрегва или се изпълнява имплицитно. С каквито и данни да работим, независимо дали са числа, низове, списъци, двоични дървета или хора, е необходимо изрично да намерим подходящ ред, който ни дава посока, в която да се движим, за да намалим проблема. Това подреждане зависи изцяло от проблема, но добро начало е да помислите за очевидните подреждания: числата идват със собствено подреждане, низовете и списъците могат да бъдат подредени по дължината им, двоичните дървета могат да бъдат подредени по дълбочина и хората могат да бъдат подредени по безкраен брой разумни начини, напр. ръст, тегло или ранг в организация. Както бе споменато по-горе, този ред трябва да съответства на степента на трудност на проблема, който се опитваме да решим.

След като сме подредили нашите данни, можем да мислим за тях като за нещо, което можем да намалим. Всъщност можем да напишем нашата поръчка като последователност:

0, 1, 2, …, n за цели числа (т.е. за целочислени данни d,градус(d) = d)

[], [■], [■, ■], …, [■, … , ■] за списъци
(забележете len = 0, len = 1, …, len = n, т.е. за данни от списък d,градус(d) = len(d))

Придвижвайки се отдясно наляво, преминаваме през общите („големите“) случаи до основните („малките“) случаи. За нашия reverse пример, ние работим с низ и можем да изберем дължината на низа като подреждане или степен на нашия проблем.

Решете малките казуси

Това обикновено е лесната част. След като имаме правилното подреждане, трябва да разгледаме най-малките елементи в нашето подреждане и да решим как ще се справим с тях. Обикновено има очевидно решение: в случая на reverse(s), след като стигнем до len(s) == 0 и имаме reverse(''), тогава знаем нашия отговор, защото обръщането на празния низ няма да направи нищо, т.е. просто ще върнем празния низ, тъй като нямаме герои, които да се движат. След като сме решили нашите базови случаи и знаем нашия ред, решаването на общия случай е толкова просто, колкото намаляването на проблема по такъв начин, че степента на данните, с които работим, се движи към базовите случаи. Трябва да внимаваме да не пропуснем нито един от малките случаи: причината, поради която се наричат ​​базови случаи, е, че покриват основата на подреждането — при по-сложни проблеми с рекурсията е обичайно да пропускаме базов случай, така че че стъпката на редукция надхвърля разумния край на нашето подреждане и започва да работи с безсмислени данни или води до грешка.

Решете големите казуси

Тук ние боравим с данните правилно в нашата поръчка, тоест данни с висока степен. Обикновено разглеждаме данни с произволна степени се стремим да намерим начин за решаване на проблема, като го редуцираме до израз, съдържащ същия проблем с по-малка степен, напр. в нашия пример на Фибоначи започнахме с произволно n и намалихме fib(n)до fib(n-1) + fib(n-2), което е израз, съдържащ два случая на проблема, с който започнахме, от по-малка степен (n -1и n-2, съответно).

Когато става дума за reverse, можем да разгледаме произволен низ с дължина n и можем да се преструваме, че нашата функция reverse работи на всички низове с дължина, по-малка от n. Как можем да използваме това, за да разрешим проблема за низ с дължина n? Е, можем просто да обърнем низа, съдържащ всичко освен последния знак, и след това да залепим този последен символ отпред. В код:

reverse(string) = reverse(string[-1]) + reverse(string[:-1])

където string[-1] съответства на последния знак, а string[:-1] съответства на низа без последния знак (това са питонизми). Този последен reverse(string[:-1]) член е нашият първоначален проблем, но работещ върху низ с дължина n-1, т.е. изразихме нашия първоначален проблем по отношение на стъпка към решението, комбинирана със същия проблем с намалено степен.

Обединявайки решението на нашата функция reverse, получаваме следното:

reverse(string):
  if len(string) == 0:
    return ''
  else:
    return string[-1] + reverse(string[:-1])

Често има повече от един рекурсивен случай, който трябва да се разглежда, тъй като данните от даден тип данни могат да приемат малко по-различни форми, но това зависи изцяло от проблема. Например, помислете, че ако искаме да изравним списък с елементи, някои от които сами по себе си могат да бъдат списъци, ще трябва да правим разлика между случаите, когато елементът, който изваждаме от списъка, е отделен елемент или подсписък, водещ до поне два рекурсивни случая.

Последни съвети

Единственият истински начин да станете по-добри в рекурсията е практиката. Разгледайте онлайн някои от хилядите проблеми с рекурсията или предизвикайте себе си да измислите задачи, които смятате, че може да са подходящи за рекурсия. След като неизбежно овладеете рекурсията, не забравяйте, че ако установите, че имате затруднения при решаването на проблем рекурсивно, опитайте вместо това итерация. Освен да се научите да бъдете по-добър програмист, рекурсията е метод за решаване на проблеми, за да направите живота си по-лесен. Ако проблемът не е подходящ за рекурсия, той просто не е подходящ за рекурсия; ще развиете усещане за това, докато прекарвате повече време в подход към проблеми, които се поддават на рекурсивен или итеративен подход.

Понякога при по-трудни проблеми с рекурсия, стъпки 2 и 3 в стратегията, която видяхме по-горе, приемат формата на по-цикличен процес на обратна връзка. Ако не можете бързо да намерите цялостно решение на проблема, най-добрият процес е да разрешите рекурсивните/„големите“ случаи, за които можете да се сетите, и да разрешите основните/„малките“ случаи, за които можете да се сетите, и след това вижте как вашият метод работи върху различни части от данни. Това трябва да разкрие всички липсващи базови и рекурсивни случаи или такива, които взаимодействат лошо помежду си и трябва да бъдат преосмислени.

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

Това е финал - благодаря, че прочетохте!

Ако ви хареса това въведение в рекурсията, не се колебайте да се свържете с мен (Том Григ) относно всякакви мисли, запитвания или предложения за бъдещи публикации в блогове!

Сега се връщам към работата по моите публикации в областта на науката за данните, следете!