Deprecated: mysql_connect(): The mysql extension is deprecated and will be removed in the future: use mysqli or PDO instead in /home/studb20/public_html/index.php on line 4
 1.16.5 Рекурсивні функції - Програмування С, С++теорія та практика (частина 1) - Studbook
ГоловнаЗворотній зв'язок

Категорії

загрузка...

Програмування С, С++теорія та практика (частина 1)

1.16.5 Рекурсивні функції

Рекурсія - це спосіб організації обчислювального процесу, при якому функція в ході виконання операторів звертається сама до себе.

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

Прямою (безпосередньою) рекурсією називається рекурсія, при якій всередині тіла деякої функції міститься виклик тієї ж функції.

VОІЙ. £п (іп£ і) {

/* ... */

£п(і) ;

/* ... */

}

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

Рис. 1.21. Непряма рекурсія

 

VОІЙ.

£пА(іп-

і)

 

VОІЙ.

£пВ(іп-

і)

 

VОІЙ.

£пС(іп-

і)

 

VОІЙ.

£пА(іп-

і)

{

/*

... */

 

 

£пВ (і) ;

 

 

/*

... */

 

 

}

 

 

 

VОІЙ.

£пВ(іп-

і)

{

/*

... */

 

 

£пС(і);

 

 

/*

... */

 

 

}

 

 

 

VОІЙ.

£пС(іп-

і)

{

/*

... */

 

 

£пА(і) ;

 

 

/*

... */

 

 

}

 

Якщо функція викликає сама себе, то в стеку створюється копія значень її параметрів, як і при виклику звичайної функції, після чого управління передається першому оператору функції. При повторному виклику цей процес повторюється.

В якості прикладу розглянемо функцію, що рекурсивно обчислює факторіал. Як відомо, значення факторіала обчислюється за формулою:    ПІ = п • (п -1) • (п - 2) •... • 1 , причому 1! = 1 і 0! = 1 .

Факторіал також можна обчислити за допомогою простого рекурентного співвідношення п! = п • (п -1)!. Для ілюстрації рекурсії скористаємося саме цим співвідношенням.

#іпс1ийе<5-й±о.Ь>

#іпс1ийе<сопіо.Ь> йоиЬІе £ас-(іп- п)

{

і£ (п<=1) ге-игп 1; ге-игп (£ас-(п-1)*п);

}

Vоій. таіп () {

іпї п;

йоиЬ1е Vа1ие;

с1гзсг () ;

ргіпї£("Н=");

зсап£("%й",&п);

Vа1ие=£асї(п);

ргіпї£("%й! = %.50д",п^а1ие);

деїсЬ() ;

}

Роботу рекурсивної функції /асІ() розглянемо на прикладі п=6! За рекурентним співвідношенням :          6! = 5!6 . Таким чином, щоб

обчислити 6! ми спочатку повинні обчислити 5!. Використовуючи співвідношення, маємо, що 5! = 4! 5 , тобто необхідно визначити 4!. Продовжуючи процес, отримаємо :

1)                                         . 6! = 5!6       2). 5! = 4!5 3).    4!     =  3!4     4).       3!            =             2!3          5). 2! = 1!2

6). 1! = 1

В кроках 1-5 завершення обчислення кожний раз відкладається, а шостий крок є ключовим. Отримане значення, яке визначається безпосередньо, а не як факторіал іншого числа. Відповідно, ми можемо повернутися від 6-ого кроку до 1-ого, послідовно використовуючи значення :

6).1!=1     5).2!=2      4). 3!=6        3). 4!=24      2).  5!=120     1). 6!=720

Важливим для розуміння ідеї рекурсії є те, що в рекурсивних функціях можна виділити дві серії кроків.

Перша серія - це кроки рекурсивного занурення функції в саму себе до тих пір, поки вибраний параметр не досягне граничного значення. Ця важлива вимога завжди повинна виконуватися, щоб функція не створила нескінченну послідовність викликів самої себе. Кількість таких кроків називається глибиною рекурсії.

Друга серія - це кроки рекурсивного виходу до тих пір, поки вибраний параметр не досягне початкового значення. Вона, як правило забезпечує отримання проміжних і кінцевих результатів.

 

78