Что такое рекурсия

Рекур­сия — важ­ный эле­мент в мате­ма­ти­ке и про­грам­ми­ро­ва­нии. С её помо­щью мож­но упа­ко­вы­вать боль­шие и слож­ные кон­струк­ции в малень­кие и про­стые, а потом раз­во­ра­чи­вать обрат­но, когда нуж­но. Давай­те выяс­ним, как она устро­е­на.

Дом, который построил Джек

Что­бы было понят­нее, что такое рекур­сия, возь­мём сти­хо­тво­ре­ние Саму­и­ла Мар­ша­ка «Дом, кото­рый постро­ил Джек»:

Вот дом,
Кото­рый постро­ил Джек.
А это пше­ни­ца,
Кото­рая в тём­ном чулане хра­нит­ся
В доме,
Кото­рый постро­ил Джек.
А это весё­лая птица-синица,
Кото­рая часто вору­ет пше­ни­цу,
Кото­рая в тём­ном чулане хра­нит­ся
В доме,
Кото­рый постро­ил Джек.
Вот кот,
Кото­рый пуга­ет и ловит сини­цу,
Кото­рая часто вору­ет пше­ни­цу,
Кото­рая в тём­ном чулане хра­нит­ся
В доме,
Кото­рый постро­ил Джек.
Вот пёс без хво­ста,
Кото­рый за шиво­рот треп­лет кота,
Кото­рый пуга­ет и ловит сини­цу,
Кото­рая часто вору­ет пше­ни­цу,
Кото­рая в тём­ном чулане хра­нит­ся
В доме,
Кото­рый постро­ил Джек. …

Смот­ри­те, что в нём инте­рес­но­го: каж­дая часть сти­хо­тво­ре­ния состо­ит из ново­го нача­ла и точ­но­го повто­ре­ния того, что уже было до это­го. Сна­ча­ла у нас был толь­ко дом, кото­рый постро­ил Джек — это нуле­вой уро­вень рекур­сии, или вло­жен­но­сти.

Нуле­вой уро­вень:

Вот дом,
Кото­рый постро­ил Джек.

Обо­зна­чим его за [0] и даль­ше будем уве­ли­чи­вать это чис­ло для каж­до­го уров­ня. Сле­ди­те за уров­ня­ми.

Пер­вый уро­вень:

А это пше­ни­ца,
Кото­рая в тём­ном чулане хра­нит­ся [0]

Что­бы полу­чить пол­но­цен­ное про­дол­же­ние, нам нуж­но взять преды­ду­щий уро­вень и под­ста­вить его сюда:

А это пше­ни­ца,
Кото­рая в тём­ном чулане хра­нит­ся
В доме,
Кото­рый постро­ил Джек.

Вто­рой уро­вень:

А это весё­лая птица-синица,
Кото­рая часто вору­ет пше­ни­цу,
[1]

Если мы будем раз­во­ра­чи­вать стих, то на пер­вом про­хо­де полу­чим такое:

А это весё­лая птица-синица,
Кото­рая часто вору­ет пше­ни­цу,
Кото­рая в тём­ном чулане хра­нит­ся
[0]

А на вто­ром у нас уже появит­ся пол­но­цен­ный стих:

А это весё­лая птица-синица,
Кото­рая часто вору­ет пше­ни­цу,
Кото­рая в тём­ном чулане хра­нит­ся
В доме,
Кото­рый постро­ил Джек.

👉 Общее пра­ви­ло такое: когда есть рекур­сия, её после­до­ва­тель­но раз­во­ра­чи­ва­ют на каж­дом шаге, пока не дой­дут до нуле­во­го уров­ня. Как толь­ко дошли — всё гото­во, рекур­сия сде­ла­ла своё дело. До это­го момен­та она вызы­ва­ет сама себя с новы­ми пара­мет­ра­ми.

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

Допу­стим, нам нуж­но посчи­тать сум­му всех чисел от 1 до какого-то чис­ла. Мож­но это сде­лать в цик­ле, а мож­но сде­лать уни­вер­саль­ную функ­цию с рекур­си­ей. Ей будет доста­точ­но ука­зать на вхо­де чис­ло, до кото­ро­го нуж­но всё посчи­тать, а она сама сде­ла­ет всё осталь­ное.

Сна­ча­ла запи­шем это на JavaScript, а потом раз­бе­рём­ся с тем, как рабо­та­ет эта магия:

function rec(x) {
  if (x == 1) { return (1) }
  else {
    return x + rec(x - 1);
  }
}
rec(10);

Пер­вая строч­ка — объ­яв­ле­ние функ­ции function rec(x). Здесь всё как обыч­но — ука­зы­ва­ем назва­ние и гово­рим, что на вход будет посту­пать какая-то пере­мен­ная, с кото­рой мож­но рабо­тать.

Затем мы орга­ни­зу­ем нуле­вой уро­вень — тот, где рекур­сия начи­на­ет­ся: if (x == 1) {return(1)}. Он гово­рит нам: если на вход посту­пит еди­ни­ца, то воз­вра­ща­ем еди­ни­цу. Это логич­но — сум­ма всех чисел от 1 до 1 рав­на еди­ни­це. Это как дом, кото­рый постро­ил Джек — всё в ито­ге све­дёт­ся к это­му.

А даль­ше идёт самое инте­рес­ное — если мы не дошли до еди­ни­цы, то мы берём зна­че­ние x и скла­ды­ва­ем его с резуль­та­том этой же функ­ции, но от преды­ду­ще­го зна­че­ния. Если мы, напри­мер, счи­та­ем rec(10), то эта коман­да сде­ла­ет так:

  1. Про­ве­рит, дошли ли до еди­ни­цы.
  2. Если не дошли — сло­жит 10 и зна­че­ние rec(9).
  3. Для это­го она про­ве­рит, дошли ли до еди­ни­цы.
  4. Если не дошли — сло­жит 9 и зна­че­ние rec(8).
  5. Для это­го она про­ве­рит…
  6. Ура, мы дошли до еди­ни­цы и воз­вра­ща­ем еди­ни­цу обрат­но.
  7. К это­му момен­ту рекур­сия уже дошла до коман­ды 2 + rec(1). Она полу­ча­ет в ответ еди­ни­цу, скла­ды­ва­ет 2 и 1 и воз­вра­ща­ет резуль­тат на уро­вень выше.
  8. На уровне выше была коман­да 3 + rec(2). Она полу­ча­ет в ответ 3, скла­ды­ва­ет 3 и 3 и воз­вра­ща­ет резуль­тат на уро­вень выше.
  9. На послед­нем уровне была коман­да 10 + rec(9). Она полу­ча­ет от преды­ду­ще­го уров­ня резуль­тат 45, скла­ды­ва­ет 10 и 45 и полу­ча­ет резуль­тат 55.
  10. Ура, рекур­сия закон­чи­лась.

Попро­буй­те сами вста­вить код в кон­соль и посмот­ри­те на резуль­тат.

Особенности рекурсии

Так как рекур­сия — это про­грам­ма, кото­рая вызы­ва­ет саму себя, то при непра­виль­ном под­хо­де рекур­сия может исполь­зо­вать очень мно­го памя­ти и машин­ных ресур­сов. Чем глуб­же уро­вень рекур­сии — тем боль­ше ресур­сов ей нуж­но.

Ино­гда про­грам­мист увле­ка­ет­ся рекур­си­ей и забы­ва­ет про­пи­сать выход из неё. В резуль­та­те рекур­сия бес­ко­неч­но углуб­ля­ет­ся саму в себя, заби­ра­ет в себя все ресур­сы и про­грам­ма пада­ет. Гово­рят, что так обра­зу­ют­ся чёр­ные дыры, в кото­рых всё исче­за­ет.

Быва­ют момен­ты, когда рекур­сия — это един­ствен­ный спо­соб выпол­нить нуж­ную зада­чу. Напри­мер, при пар­син­ге HTML-кода или для постро­е­ния дере­ва зави­си­мо­стей.

Что дальше

Теперь, когда мы доста­точ­но зна­ем про рекур­сию, то смо­жем сде­лать инте­рес­ный новый про­ект. Напри­мер, что­бы наша про­грам­ма сама реша­ла судо­ку любой сте­пе­ни слож­но­сти или рисо­ва­ла класс­ные лаби­рин­ты.

Текст:
Миха­ил Поля­нин
Редак­тор:
Миха­ил Поля­нин
Кор­рек­тор:
Ири­на Михе­е­ва
Иллю­стра­ция:
Даня Бер­ков­ский
Вёрст­ка:
Мария Дро­но­ва
Сде­лать так, что­бы все узна­ли об этой ста­тье:
Вита­лий Вебер
Джек, кото­рый постро­ил дом:
Павел Федо­ров