Рекурсія, перевантаження функцій, функція main з параметрами

Оголошення і визначення функцій

Передача параметрів та повернення значень з функцій.

Функції можуть повертати значення. Після звернення до функції вона може виконати деякі дії, а потім як результат своєї роботи послати назад деяке значення. Воно називається повертаним значенням, причому тип цього значення обов'язково має бути оголошений. Таким чином, запис

int myFunction();

оголошує, що функція myFunction повертає цілочисельне значення.

У функцію можна також і посилати деякі значення. Опис посиланих значень називається списком параметрів.

int myFunction(int someValue, float someFloat);

Це оголошення означає, що функція myFunction не лише повертає ціле число, але і набуває два значення як параметри: цілочисельне і речове.

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

int theValueReturned = myFunction(5,6.7);

Тут ціла змінна theValueReturned ініціалізувалася значенням, повертаним функцією myFunction, і що як аргументи цієї функції передаються значення 5 і 6,7. Тип аргументів повинен відповідати оголошеним типам параметрів.

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

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

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

Важливо відмітити, що, коли функція викликає саме себе, виконується нова копія цієї функції. При цьому локальні змінні в другій версії незалежні від локальних змінних в першій і не можуть безпосередньо впливати один одного, принаймні не більше, ніж локальні змінні у функції main() можуть впливати на локальні змінні в будь-якій іншій функції, яку вона викликає, як було показано в лістингу 5.4.

Щоб показати приклад вирішення проблеми за допомогою рекурсії, розглянемо ряд Фібоначчі:

1,1,2,3,5,8,13,21,34...

Кожне число ряду (після другого) є сумою двох чисел, що стоять попереду. Завдання може полягати в тому, щоб, наприклад, визначити 12-й член ряду Фібоначчі.

Один із способів вирішення цієї проблеми лежить в ретельному аналізі цього ряду. Перші два числа дорівнюють 1. Кожне наступне число дорівнює сумі двох попередніх. Таким чином, сімнадцяте число дорівнює сумі шістнадцятого і п'ятнадцятого. У загальному випадку n - e число дорівнює сумі (n - 2) -го і (n - l) -го за умови, якщо n > 2.

Для рекурсивних функцій необхідно задати умову припинення рекурсії. Обов'язково повинно статися щось, здатне змусити програму зупинити рекурсію, або ж вона ніколи не закінчиться. У ряду Фібоначчі умовою останову є вираження n < 3.

При цьому використовується наступний алгоритм:

1. Пропонуємо користувачеві вказати, який член в ряду Фібоначчі слід розрахувати.

2. Викликаємо функцію fib(), передаючи як аргумент порядковий номер члена ряду Фібоначчі, заданий користувачем.

3. У функції fib() виконується аналіз аргументу (n). Якщо n < 3, функція повертає значення 1; інакше функція fib() викликає саме себе (рекурсивно), передаючи як аргумент значення n - 2, потім знову викликає саме себе, передаючи як аргумент значення п- 1, а після цього повертає суму.

Якщо викликати функцію fib(1), вона поверне 1. Якщо викликати функцію fib(2), вона також поверне 1. Якщо викликати функцію fib(3), вона поверне суму значень, повертаних функціями fib(2) і fib(l). Оскільки виклик функції fib(2) повертає значення 1 і виклик функції fib(1) повертає значення 1, то функція fib(3) поверне значення 2.

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

Зробимо ще один крок. Якщо викликати функцію fib(5), вона поверне суму значень, повертаних функціями fib(4) і fib(3). Як ми встановили, функція fib(4) повертає значення 3, а функція fib(3) - значення 2, тому повертана сума дорівнюватиме числу 5.

Описаний метод - не найефективніший спосіб рішення цієї задачі (при виклику функції fib(20) функція fib() викликається 13 529 разів!), проте він працює. Проте будьте обережні. Якщо задати занадто великий номер члена ряду Фібоначчі, вам може не вистачити пам'яті. При кожному виклику функції fib() резервується деяка область пам'яті. При поверненні з функції пам'ять звільняється. Але при рекурсивних викликах резервуються усі нові області пам'яті, а при такому підході системна пам'ять може вичерпатися досить швидко. Реалізація функції fib() показана в лістингу 5.10.

Попередження: При запуску програми, представленої в лістингу 6.10, задавайте невеликі номери членів ряду Фібоначчі (менше 15). Оскільки в цій програмі використовується рекурсія, можливі великі витрати пам'яті.

Лістинг 5.10. Приклад використання рекурсії для знаходження члена ряду Фібоначчі

1: #include <iostream.h>

2:

3: int fib (int n);

4:

5: int main()

6: {

7:

8: int n, answer;

9: cout << "Enter number to find: "; 10: cin >> n;

10:

11: cout << "\n\n";

12:

13: answer = fib(n);

14:

15: cout << answer << " is the " << n << "th Fibonacci number\n"; 17: return 0

16: }

17:

18: int fib (int n)

19: {

20: cout << "Processing fib(" << n << ").. "; 23:

21: if (n < 3)

22: {

23: cout << "Return 1!\n";

24: return (1);

25: }

26: else

27: {

28: cout << "Call fib(" << n - 2 << ") and fib(" << n - 1 << ").\n";

29: return(fib(n - 2) + fib(n - l));

30: }

31: }

Результат:

Enter number lo find: 6

Processing fib(6).. Call fib(4) and fib{S)

Processing fib(4).. Call fit>(2) and fib(3)

Processing fib(2).. Return 1!

Processing fib(3).. Call fib(l) and fiO<2)

Processing fib(D.. Return 1!

Processi ng fib(2).. Return 1!

Processing fib(5).. Call fib(3) and fib{4)

Processing fib(3}.. Call fib(1) and fib(2)

Processing flb(1).. Return 1!

Processi ng fib(2).. Return 1!

Processing fib(4).. Call fib(2) and fib(3)

Processing fib(2).. Return 1!

Processing fib(3).. Call fib(1) and fib(2)

Processing fib(l).. Return 1!

Processing fib(2).. Return 1!

8 is the 6th Fibonacci number

Примечание:Некоторые компілятори зазнають утруднення з використанням операторів у виразах з об'єктом cout. Якщо ви отримаєте попередження в рядку 28, візьмете операцію віднімання в круглих дужок, щоб рядок 28 набрала наступного вигляду:

28: cout << "Call fib(" << (n - 2) << ") and fib(" << n - 1 << ").\n";

Аналіз: В рядку 9 програма пропонує ввести номер шуканого члена ряду і привласнює його змінній n. Потім викликається функція fib() з аргументом n. Виконання програми переходить до функції fib(), де в рядку 20 цей аргумент виводиться на екран.

У рядку 21 перевіряється, чи не менше аргумент числа 3, і, якщо це так, функція fib() повертає значення 1. Інакше виводиться сума значень, повертаних при виклику функції fib() з аргументами n, - 2 і п- 1. Таким чином, цю програму можна представити як циклічний виклик функції fib(), що повторюється до тих пір, поки при черговому виклику цієї функції не буде повернено деяке значення. Єдиними викликами, які негайно повертають значення, є виклики функцій fib(1) і fib(2). Рекурсивне використання функції fib() проілюстроване на мал. 5.4 і 5.5.

У прикладі, зображеному на малюнках, змінна n дорівнює значенню 6, тому з функції main() викликається функція fib(6). Виконання програми переходить в тіло функції fib(), і в рядку 30 значення переданого аргументу порівнюється з числом 3. Оскільки число 6 більше числа 3, функція fib(6) возврашает суму значень, повертаних функціями fib(4) і fib(5),:

38: return(fib(n - 2) + fib(n - 1));

Це означає, що виконується звернення до функцій fib(4) і fib(оскільки змінна n равначислу 6, то fib(n - 2) - це те ж саме, що fib(4), а fib(n - 1) - те ж саме, що fib(5)). Після цього функція fib(6), якій у нинішній момент передано управління програмою, чекає, доки зроблені виклики не повернуть яке-небудь значення. Дочекавшись повернення значень, ця функція поверне результат підсумовування цих двох значень.

Оскільки при виклику функції fib(5) передається аргумент, який не менше числа 3, функція fib() викликатиметься знову, цього разу з аргументами 4 і 3. А функція flb(4) викличе, у свою чергу, функції fib(3) і fib(2).

Результати і проміжні етапи роботи програми, представленої в лістингу 5.10, виводяться на екран. Скомпілюйте, скомпонуйте і виконаєте цю програму, ввівши спочатку число 1, потім 2, 3, і так дістаньтеся до числа 6, уважно спостерігаючи за інформацією, що відображується.

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

У програмуванні на мові C++ рекурсія не частий гість, але в певних випадках вона є потужним і дуже елегантним інструментом.

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

Робота функцій - підводимо завісу таємниці

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

Дата добавления: 2013-12-14