Рэкурсіі - гэта што? Рэкурсія у праграмаванні (прыклады)

Рэкурсіі з'яўляюцца цікавымі падзеямі самі па сабе, але ў праграмаванні яны прадстаўляюць асаблівую важнасць у асобных выпадках. Упершыню сутыкаючыся з імі, даволі значная колькасць людзей маюць праблемы з іх разуменнем. Гэта звязана з велізарным полем патэнцыйнага ўжывання самога тэрміна ў залежнасці ад кантэксту, у якім «Рэкурсія» выкарыстоўваецца. Але можна спадзявацца, што гэты артыкул дапаможа пазбегнуць магчымага непаразуменні або неразумення.

Што такое "Рэкурсія" наогул?

Слова "Рэкурсія" мае цэлы спектр значэнняў, якія залежаць ад вобласці, у якой яно ўжываецца. Ўніверсальны абазначэнне з'яўляецца такім: рэкурсіі - гэта вызначэння, выявы, апісанні аб'ектаў або працэсаў у саміх аб'ектах. Магчымыя яны толькі ў тых выпадках, калі аб'ект з'яўляецца часткай самога сябе. Па-свойму вызначаюць рэкурсіі матэматыка, фізіка, праграмаванне і шэраг іншых навуковых дысцыплін. Практычнае прымяненне яна знайшла ў працы інфармацыйных сістэм і фізічных эксперыментах.

Што маюць на ўвазе пад рэкурсіі ў праграмаванні?

Рэкурсіўная сітуацыямі, або рэкурсіі ў праграмаванні, называюць моманты, калі працэдура або функцыя праграмы выклікае саму сябе. Як бы дзіўна для тых, хто пачаў вывучаць праграмаванне, гэта ні гучала, тут няма нічога дзіўнага. Варта запомніць, што рэкурсіі - гэта не складана, і ў асобных выпадках яны замяняюць цыклы. Калі кампутара правільна задаць выклік працэдуры або функцыі, ён проста пачне яе выконваць.

Рэкурсія можа быць канчатковай або бясконцай. Для таго каб першая спыніла сама сябе выклікаць, у ёй жа павінны быць умовы спынення. Гэта можа быць памяншэнне значэння зменнай і пры дасягненні пэўнага значэння прыпынак выкліку і завяршэнне праграмы / пераход да наступнага коду, у залежнасці ад патрэбаў дасягнуць пэўных мэтаў. Пад бясконцай рэкурсіі маюць на ўвазе, што яна будзе выклікацца, пакуль будзе працаваць кампутар ці праграма, у якой яна працуе.

Магчымая таксама арганізацыя складанай рэкурсіі з дапамогай двух функцый. Дапусцім, ёсць А і Б. Функцыя А мае ў сваім кодзе выклік Б, а Б, у сваю чаргу, паказвае кампутара на неабходнасць выканаць А. Складаныя рэкурсіі - гэта выхад з цэлага шэрагу складаных лагічных сітуацый для кампутарнай логікі.

Калі хто чытае гэтыя радкі вывучаў праграмныя цыклы, то ён, напэўна, ужо заўважыў падабенства паміж імі і рэкурсіі. У цэлым яны сапраўды могуць выконваць падобныя або ідэнтычныя задання. З дапамогай рэкурсіі зручна рабіць імітацыю працы цыклу. Асабліва гэта карысна там, дзе самі цыклы выкарыстоўваць не вельмі зручна. Схема праграмнай рэалізацыі не моцна адрозніваецца ў розных высокаўзроўневых моў праграмавання. Але ўсё ж Рэкурсія ў "Паскалю" і Рэкурсія ў З або іншай мове мае свае асаблівасці. Можа яна быць паспяхова рэалізавана і ў нізкаўзроўневых мовах накшталт "асэмблер", але гэта з'яўляецца больш праблематычным і затратным па часе.

дрэвы рэкурсіі

Што такое "дрэва" ў праграмаванні? Гэта канчатковае мноства, якое складаецца як мінімум з аднаго вузла, які:

1. Мае пачатковы спецыяльны вузел, які называюць коранем усяго дрэва.
2. Астатнія вузлы знаходзяцца ў колькасці, выдатным ад нуля, парамі неперасякальных падмноства, пры гэтым яны таксама з'яўляюцца дрэвам. Усе такія формы арганізацыі называюць поддерево галоўнага дрэва.

Іншымі словамі: дрэвы ўтрымліваюць поддерево, якія ўтрымліваюць яшчэ дрэвы, але ў меншай колькасці, чым папярэдняе дрэва. Так працягваецца да таго часу, пакуль у адным з вузлоў не застанецца магчымасці прасоўвацца далей, і гэта будзе пазначаць канец рэкурсіі. Ёсць яшчэ адзін нюанс наконт схематычнага малюнка: звычайныя дрэвы растуць знізу ўверх, а ў праграмаванні яны малююцца наадварот. Вузлы, якія не маюць працягу, называюцца канчатковымі кропкамі. Для зручнасці абазначэння і для зручнасці выкарыстоўваецца генеалагічная тэрміналогія (продкі, дзеці).

Навошта яна ўжываецца ў праграмаванні?

Сваё ўжыванне Рэкурсія у праграмаванні знайшла ў рашэнні цэлага шэрагу складаных задач. Калі неабходна зрабіць толькі адзін выклік, то больш лёгкім з'яўляецца прымяненне інтэграцыйнага цыклу, але пры двух і больш паўторах, каб пазбегнуць пабудовы ланцужкі і зрабіць іх выкананне ў выглядзе дрэва, і ўжываюцца рэкурсіўныя сітуацыі. Для шырокага класа задач арганізацыя вылічальнага працэсу такім спосабам з'яўляецца найбольш аптымальнай з пункту гледжання спажывання рэсурсаў. Так, Рэкурсія ў "Паскалю" ці іншым любым высокаўзроўневай мове праграмавання ўяўляе сабой выклік функцыі або працэдуры да выканання ўмоў, незалежна ад колькасці знешніх выклікаў. Іншымі словамі, у праграме можа быць толькі адзін зварот да падпраграмы, але адбывацца яно будзе да пэўнага загадзя моманту. У пэўным сэнсе гэта аналаг цыклу са сваёй спецыфікай выкарыстання.

Адрозненні рэкурсіі ў розных мовах праграмавання

Нягледзячы на агульную схему рэалізацыі і канкрэтнае прымяненне ў кожным асобным выпадку, Рэкурсія у праграмаванні мае свае асаблівасці. Гэта можа прывесці да складанасці падчас пошуку неабходнага матэрыялу. Але заўсёды варта памятаць: калі мова праграмавання выклікае функцыі або працэдуры, значыць, і выклік рэкурсіі - справа здзейснае. Але найбольш значныя яе адрозненні выяўляюцца пры выкарыстанні нізкіх і высокіх моў праграмавання. Асабліва гэта тычыцца магчымасцяў праграмнай рэалізацыі. Выкананне ў канчатковым выніку залежыць ад таго, якая задача пастаўлена, у адпаведнасці з ёй і пішацца Рэкурсія. Функцыі і працэдуры выкарыстоўваюцца розныя, але іх мэта заўсёды адна - прымусіць выклікаць саміх сябе.

Рэкурсія - гэта лёгка. Як проста запомніць змест артыкула?

Для пачаткоўцаў зразумець яе, можа быць, спачатку складана, таму патрэбныя прыклады рэкурсіі ці хаця б адзін. Таму варта прывесці невялікі прыклад з бытавым жыцці, які дапаможа зразумець саму сутнасць гэтага механізму дасягнення мэтаў у праграмаванні. Вазьміце два ці больш люстэркаў, пастаўце іх так, каб у адным адлюстроўваліся ўсе астатнія. Можна ўбачыць, што люстэрка адлюстроўваюць сябе шматкроць, ствараючы эфект бясконцасці. Вось рэкурсіі - гэта, вобразна кажучы, адлюстравання (іх будзе мноства). Як бачыце, зразумець нескладана, было б жаданне. А вывучаючы матэрыялы па праграмаванні, далей можна зразумець, што Рэкурсія - гэта яшчэ і вельмі лёгка выканальная задача.