• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

ВКАЗІВНИКИ НА ФУНКЦІЇ В АЛГОРИТМІЧНІЙ МОВІ С

Лекція № 6

РЕКУРСИВНІ ФУНКЦІЇ,

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

- при кожному виклику такої функції в неї повинні передаватися модифіковані дані;

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

після завершення кожного виклику рекурсивної функції в точку повернення повинен передаватися деякий результат для подальшого використання.

/* Приклад: використання рекурсивної функції. Припустимо, що задано два числа a і b. Необхідно більше із цих чисел розділити на менше. */

#include <stdio.h>

void main (void)

{

float a, b;

float recurs (float, float) ;

printf”Введіть значення a і b \n");

scanf(“%f %f”,&a, &b); // Ввід значень

printf(" a=%f b =%f", a, b);

printf(" Результат ділення: " , recurs (a, b));

// Тіло функції

float recurs (float a, float b) // Рекурсивна функція

if(a<b) return recurs(b,a); // Якщо а < b, то параметри

/ / міняються

// місцями (рекурсивний виклик)

else return a/b; // Вихід з рекурсії

}

У функцію recurs передаються значення двох дійсних чисел. Припустимо спочатку, що умова а < b не виконується. У цьому випадку при першому ж звертанні до recurs має місце нерекурсивний вихід. Нехай тепер умова а < b виконується. Тоді функція recurs звертається до самої себе, однак параметри а і b у виклику міняються місцями, тобто параметру а у функції передається більше значення (b), а параметру b - менше значення (a). Після чого відбувається вихід з рекурсії і в main буде переданий результат.

Рекурсія нерідко входить у визначення математичних алгоритмів.

// Приклад: обчислення факторіала за допомогою рекурсії:

//

#jinclude <stdio.h>

void main (void)

long fact (int); // Прототип функції

int n;

printf("Введіть n \n");

scanf(“%d”, &n); // Ввід значення

printf(" Факторіал %d = %d \n", n, fact (n));

}

long fact (int n) /* Рекурсивна функція */

{

return (n) ? (long) n * fact(n-1):1;

}

Розглянемо процес виконання цієї програми. Функція main викликає функцію fact і передає параметр n Якщо n == 0, то повернеться значення 1. Інакше функція fact(n) повинна викликати fact( n-l). Так буде тривати до виклику fact(0), що поверне значення 1 у точку виклику fact(l).

Для розуміння механізму виконання рекурсивної функції запишемо її в такий спосіб:

long fact ( int n )

{

if (n) return (long) n * fact ( n-1); // IP*

else return 1;

}

Слово else можна й опустити.

Розглянемо стан стека у випадку обчислення 3!

Головний модуль (main) запише в стек число 3 і адресу повернення (позначимо його IP main) для продовження виконання програми, тобто повернення в точку виклику - у функцію printf("Факторіал n %d = %d \n”, n, fact(n)); - для виводу результату.

При кожному наступному виклику функції (long) n * fact ( n-1) обчислення даного виразу залишається незавершеним, у стек послідовно записуються число n (2, 1, 0) і адреса повернення на завершення обчислення зазначеного виразу. Це буде та ж сама адреса, позначимо її умовно IP* і далі (дивися зображення стану стека) зазначено, яке n було на вході у функцію при збереженні даного IP*.

Функція main також може бути рекурсивною в Turbo C, тобто розширення файлу з вихідною програмою повинне бути '.с', а не '.срр'. Наприклад: L10_041.С.

Приклад: не оголошуючи масиву, ввести групу даних, вивести їхню загальну кількість, порядкові номери i значення чисел у зворотному порядку. Ознака кінця вводу чисел - 0.

//

# include <iostream.h>

void main (void)

{

static int n; int m, l=0; // Можна static n=0;

static int k;

/* Дані із класом зберігання static зберігаються в пам'яті на весь час виконання програми */

cout << "Число- ? " << endl;

cin >> m;

if ( m ) { n++; l++;

cout << " Виклик : n=” << n << " l= " << l << endl;

main ( );

/* Запис main без дужок не забезпечує рекурсивного виклику, але й не дає помилки компіляції*/

k++;

cout<<"Вихід: номер=" << k << " число=" << m << " 1= " << l << " n= " << n;

}

Результат роботи програми:

число-? 4 виклик: n=0,l=1

число-? 3 виклик: n=1, l=1

число-? 2 виклик: n=2,1=1

число-? 1 виклик: n=3,1=1

число-? 0 виклик: n=4,1=1

вихід: номер=1 число=0 l=0 n=4

вихід: номер=2 число=1 l=1 n=4

вихід: номер=3 число=2 1=1 n=4

вихід: номер=4 число=3 1=1 n=4

вихід: номер=5 число=4 1=1 n=4.

Наступний характерний приклад рекурсивної функції - це швидке сортування (сортування Хоара). Для заданого масиву вибирається один елемент, що розбиває інші елементи на дві підмножини - те, що менше, і те, що не менше його. Та ж процедура рекурсивно застосовується й до двох отриманих підмножин. Якщо в підмножині залишається менш двох елементів, то рекурсія завершується.

/*qsort сортує v[left] . , ,v[right] по зростанню*/

void qsort(int v[], int left, int right)

{

int i, last;

void swap (int v[],int i, int j);

if (left>=right) /* Нічого не робиться, якщо */

return; /*в масиві менше двох елементів */

swap (v, left, (left+right) /2) ; /* елемент, що ділить, */

last=left; /* Переноситься в v[0] */

for (i = left+1; i <= right; i++) /* Ділення на частини */

if (v[i] < v[left]>

swap(v, ++last, i) ;

swap (v, left, last) ; /* Заміняємо елемент, що ділить, */

qsort(v,left, last-l) ;

qsort (v, last+1, right) ;

}

void swap (int v[] , int i, int j )

// swap міняє місцями v[i] і v[j]

{

int temp;

temp=v [ i ] ;

v[j]=temp;

}

Рекурсивна програма не забезпечує ні ощадливої витрати пам'яті, ні швидкодії, але в порівнянні з деякими нерекурсивними часто коротше, а також легше для розуміння. Такі програми зручні для обробки структур даних типу дерев.

Читайте також:

1. Адвокатура в Україні: основні завдання і функції
2. Алгоритм знаходження ДДНФ (ДКНФ) для даної булевої функції
3. Але відмінні від значення функції в точці або значення не існує, то точка називається точкою усувного розриву функції .
4. Аналіз коефіцієнтів цільової функції
5. АРХІВНІ ДОВІДНИКИ В СИСТЕМІ НДА: ФУНКЦІЇ ТА СТРУКТУРА
6. Асимптоти графіка функції
7. Базальні ядра, їх функції, симптоми ураження
8. Базові функції, логічні функції
9. Банки як провідні суб’єкти фінансового посередництва. Функції банків.
10. Банківська система та її основні функції
11. Банківська система та її структура. Функції Центрального банку.
12. Банківська система: сутність, принципи побудови та функції. особливості побудови банківської системи в Україн

Переглядів: 2002