Вказівники на функції
Для оголошення вказівників на функцію використовують таку синтаксичну конструкцію:
тип ( * ім’я_вказівника ) ( список_параметрів_функції )
Операція ( ) – «функція», має вищий пріоритет, ніж операція * - «вказівник». Без дужок навколо * ім’я вказівника оголошення буде прототипом функції, яка використовує відповідні параметри і повертає значення, яке є вказівником. У списку параметрів вказують тільки типи без імен.
Для присвоєння вказівнику адреси певної функції можна використовувати її ім’я або вираз & ім’я функції. Коли вказівник отримав адресу функції, його можна застосовувати для звертання до цієї функції таким чином:
( * вказівник_на_функцію ) ( параметри_функції )
Наприклад:
#include <iostream>
using namespace std;
void print_hello( void ) {
cout << "Hello from print_hello" << endl;
}
int plus_one( int a ) {
return a + 1;
}
int main() {
// вказівник на функцію print_hello
void ( * p1 )( void );
print_hello( );
p1 = print_hello;
( *p1 )();
// вказівник на функцію plus_one
int ( * p2 )( int );
cout << plus_one( 1 ) << endl;
p2 = & plus_one;
cout << ( *p2 )( 2 ) << endl;
}
Створимо функцію, яка буде обчислювати значення визначеного інтеграла методом прямокутників. В функцію будемо передавати інтервал інтегрування, кількість частин, на які розбивається інтервал інтегрування, і вказівник на функцію, інтеграл якої необхідно знайти.
#include <iostream>
using namespace std;
double simpson( double ( * f )( double ), double a, double b, int n ) {
double s = 0, h = ( b - a ) / n, x;
for ( x = a + 0.5 * h; x < b; x += h )
s += ( *f )( x );
return s * h;
}
double f1( double x ) {
return sin( x ) + cos( x );
}
int main() {
cout << simpson( sin, 0, 1, 100) << endl;
cout << simpson( f1, 0, 1, 100) << endl;
double ( * p )( double );
p = f1;
cout << simpson( p, 0, 1, 100) << endl;
}
Рекурсивні функції
Рекурсивними називають функції, які в процесі виконання звертаються самі до себе. Рекурсія може бути безпосередньою (пряма рекурсія) – коли з тіла функції викликається та сама функція, або посередньою (непряма рекурсія) – коли функція викликає інші функції, які безпосередньо або через треті функції звертаються до даної функції.
Здебільшого рекурсивні функції є лаконічними в записі і дають змогу наочно та стисло відобразити алгоритм розв’язання задачі. З іншого боку, рекурсивні звертання часто не легкі для сприйняття, аналізу та контролю. Вони можуть вимагати значних обсягів оперативної пам'яті і призводити до часових затримок в процесі виконання програми.
За способом реалізації рекурсивні виклики рекурсивні виклики функцій нічим не відрізняються від звичайних викликів: кожен раз створюється новий набір формальних параметрів і внутрішніх змінних програми, код функції виконується від самого початку. Результат виконання функції повертається в точку її виклику.
Розглянемо програму для знаходження факторіала:
#include <iostream>
using namespace std;
long fact1( int k ) {
if( k < 0 ) return 0;
if( k == 0 ) return 1;
return k * fact1( k - 1 );
}
long fact2( int k ) {
if ( k < 0 ) return 0;
int f = 1;
while ( k ) f *= k--;
return f;
}
int main( ) {
cout << fact1( 5 ) << endl;
cout << fact2( 5 ) << endl;
}
Рекурсивними викликами можна замінити циклічні процеси. В наступній програмі рекурсивні функції використовуються для виводу на екран елементів масиву. Перша функція виводить елементи масиву від першого до останнього, друга – від останнього до першого.
#include <iostream>
using namespace std;
void print1( int a[ ], int n ) {
if ( n == 0 ) return;
cout << *a << endl;
print1( a + 1, n - 1 );
}
void print2( int a[ ], int n ) {
if ( n > 1 ) print2( a + 1, n - 1 );
cout << *a << endl;
}
int main( ) {
const int N = 5;
int ar[ N ] = { 1, 2, 3, 4, 5 };
print1( ar, N );
print2( ar, N );
}
Ці функції демонструють важливі властивості рекурсивних функцій: оператори, записані перед рекурсивним викликом, виконуються в тому ж порядку, в якому відбуваються виклики функцій; оператори, розташовані після рекурсивного виклику, виконуються в зворотному порядку відносно рекурсивних викликів даної функції.
Розглянемо функції, призначені для знаходження чисел Фібоначчі.
#include <iostream>
using namespace std;
long knownf[ 47 ];
void init_fibo( ) {
int i;
knownf[ 0 ]=0;
knownf[ 1 ]=1;
for( i = 2; i < 47; i++ )
knownf[ i ] = -1;
} //---------------------------------------------------------------
long fib1( long n ) {
switch ( n ) {
case 0 : return 0; break;
case 1 : return 1; break;
default: return fib1( n – 1 ) + fib1( n – 2 );
}
} //---------------------------------------------------------------
long fib2( long n ){
int i;
if ( knownf[ n ] != -1 )
return knownf[ n ];
else {
knownf[ n ] = fib2( n – 1 )+fib2( n – 2 );
return knownf[ n ];
}
} //---------------------------------------------------------------
void main( ) {
init_fibo( );
cout << fib1( 40 ) << endl;
cout << fib2( 40 ) << endl;
}
При виклику функції fib1(12) буде виконуватись оператор return fib1(11) + fib1(10). Схематичноце можна представити так:
Рис. 11.1. Схема рекурсивних викликів для знаходження 12го числа Фібоначчі
Недоліком цієї функції є те, що знаходження більшості чисел Фібоначчі буде виконуватися декілька разів при кожному виклику функції. Цього можна позбутися, якщо зберігати знайдені числа Фібоначчі в окремому масиві, як це зроблено в функції fib2.