Рекурсія

Докладніше

Рекурсія - це виклик функції всередині самої себе.

Господині на замітку

Наприклад, у нас є коробка, в якій складені інші коробки. В одній з цих коробок є ключ. Потрібно його знайти.

Можна скористатись таким алгоритмом:

1) Скласти всі коробки в купу

2) Взяти коробку і відкрити її

3) Якщо всередині інша коробка, то покласти її на купу для подальшого пошуку

4) Якщо всередині лежить ключ, то пошук завершено

5) Повторити поки в купі є коробки

Або таким:

1) Переглянути вміст коробки

2) Якщо знайдете коробку, повернутись до кроку 1

3) Якщо всередині лежить ключ, то пошук завершено

Розглянемо випадок, коли у червоній коробці лежать синя (у ній - чорна та фіолетова), жовта (в ній - сіра) та зелена.

За першим алгоритмом, ми відкриваємо червону коробку. Бачимо в ній синю, жовту та зелену, кладемо їх на купу. Тоді відкриваємо синю, бачимо чорну та фіолетову, кладемо їх на купу. Перевіряємо жовту, з неї додаємо на купу сіру. Тоді зелену, чорну, фіолетову та сіру.

З другим алгоритмом, відкривши синю коробку, і побачивши у ній дві, відкриваємо їх. Тоді переходимо до наступної - жовтої, і сірої у ній. А тоді - зелена.

Не можна сказати, що один з цих алгоритмів ефективніший чи кращий (зрештою, все залежить від того, де ж ключ). Але один з них має лаконічніший запис, який може бути зручнішим для пояснення.

Дуже важливо передбачити базовий випадок, інакше отримаємо безконечну рекурсію. Наприклад:

def rec ( n ) :

print ( n )

rec (n-1)

rec (10)

Програма буде друкувати числа від 10 до мінус безконечності, якщо ми не зупинимо програму (комбінація клавіш Ctrl+C).

Важливо вказати базовий випадок, який буде точкою зупинки. Наприклад, друкувати числа лише до нуля.

def rec ( n ) :

print ( n )

if n>0:

rec( n-1 )

else:

return

rec(10)

Три правила рекурсії

1) Рекурсія повинна мати базовий випадок

2) Рекурсія повинна містити зміну стану та можливість переходу до базового випадку

3) Рекурсія повинна викликати саму себе

Page updated

Google Sites

Report abuse