1. Приклад побудови рекурсивної функції. Відомо, що операцію множення на ненегативне ціле можна подати як рекурсивну операцію додавання. Написати рекурсивну функцію, що реалізує таке множення.
Подамо операцію множення у загальному вигляді через операцію додавання:
, (2.1)
або у рекурсивному вигляді:
(2.2)
Другий рядок у формулі (2.2) є умовою завершення рекурсії. Його відсутність може привести до того, що поступове зменшення множника n забезпечує перехід його значень до негативної області, а це, у свою чергу, може викликати зациклювання алгоритму та переповнення стеку.
Формула (2.2) є підґрунтям для написання рекурсивної функції. Як параметри функції виступатимуть значення k та n. Тип функції визначається типом множника k, оскільки, виходячи з умов задачі, n є цілим. Використаємо більш загальний випадок, коли k має тип float. Тоді визначення рекурсивної функції має вигляд:
float dobutok(int n, float k)
{ if (n>0) //умова продовження рекурсії
return dobutok(n-1,k)+k; //визначеннярекурсивної суми
else //умова припинення рекурсії
return 0;
}
Визначення рекурсивної суми проводять у два етапи: спочатку виконують виклик рекурсивної функції dobutok() з параметром n, який зменшено на одиницю, після цього визначають рекурсивну суму як результат додавання до значення, отриманого у результаті рекурсивного виклику, значення параметра k .
2. Приклад побудови головної функції та виклику рекурсивної.
#include<iostream.h>
float dobutok(int n, float k);
void main()
{ float k;
int n;
cout<<”\nВведіть значення n та k”;
cin>>n>>k;
cout<<”\nЗначення n*k= ”<<dobutok(n,k); //виклик рекурсивної функції
}
Заголовок рекурсивної функції, який наведено у другому рядку програми, дозволяє компілятору визначити тип функції та список параметрів, але не саму функцію. За правилами мови C/C++ заголовок функції необхідно навести до її використання, що у даному випадку виконано. Опис самої функції, який наведено у попередньому пункті, можна навести після головної функції або в окремому файлі за умов його коректного підключення.
Зміст|вміст,утримання| звіту щодо лабораторної роботи №2
1. Титульна сторінка |аркуш|: назва дисципліни; номер і найменування роботи; прізвище, ім'я, по батькові студента; дата виконання.
2. Постановлення завдання|задачі|.
3. Пояснення можливості використання рекурсії у поставленому завданні. Визначення основних змінних і функцій з|із| коментарями.
4. Реалізація функцій.
5. Лістинг основної програми, де має бути вказано, в якому місці та яку функцію викликають|спричиняють|.
