У попередній статті ми ознайомилися зі структурою лямбда функцій, а тепер пограємося з лямбдами, обчислимо факторіал, і розглянемо, як для цього можна застосувати лямбда функцію.
Розглянемо спочатку звичайний варіант обчислення факторіалу, а також уточнимо, що таке рекурсивна функція.
Рекурсивна функція
Рекурсивною функцією є та функція, що викликає себе. Це означає, що всередині функції є виклик самої себе і може статися нескінченна рекурсія, якщо в коді функції відсутні умови виходу з рекурсії.
Ось приклад такої нескінченної рекурсивної функції, програма з якою завершується аварійно через переповнення стеку викликів.
#include <iostream>
using namespace std;
void infiniteRecursiveFunction()
{
cout << "Hello World!" << endl;
infiniteRecursiveFunction();
}
int main()
{
infiniteRecursiveFunction();
return 0;
}
Щоб такого не відбувалося, потрібно додати умову виходу з рекурсивної функції, наприклад досягнення лічильника рекурсивних викликів значення 100.
#include <iostream>
using namespace std;
void infiniteRecursiveFunction(int counter = 0)
{
cout << "Hello World!" << endl;
if (counter == 100)
{
return;
}
infiniteRecursiveFunction(counter + 1);
}
int main()
{
infiniteRecursiveFunction();
return 0;
}
Тепер рекурсивна функція буде завершуватися коректно, завдяки лічильнику стек викликів не переповнюватиметься і програма завершиться без помилок.
Факторіал
А тепер визначимося з тим, що таке факторіал.
Факторіал
- це добуток натуральних чисел від 1 до самого числа (включаючи це число).
Позначається факторіал знаком оклику «!».
Приклади:
- 4! = 1 · 2 · 3 · 4 = 24
- 5! = 1 · 2 · 3 · 4 · 5 = 120
Тепер напишемо функцію для обчислення факторіалу
long double fact(int N)
{
if(N < 0) // если пользователь ввел отрицательное число
{
return 0; // возвращаем ноль
}
else if (N == 0) // если пользователь ввел ноль,
{
return 1; // возвращаем факториал от нуля, который равен 1
}
else // во всех остальных случаях
{
return N * fact(N - 1); // выполняем рекурсивный вызовы функции
}
}
В даному випадку функція написана так, щоб обчислення факторіалу виконувалося з найбільшого числа та закінчувалося нулем. Тоді виконуватиметься коректний вихід із рекурсії та функція повертатиме значення факторіалу.
В результаті код програми для обчислення факторіалу виглядатиме так
#include <iostream>
using namespace std;
long double fact(int N)
{
if(N < 0) // если пользователь ввел отрицательное число
{
return 0; // возвращаем ноль
}
else if (N == 0) // если пользователь ввел ноль,
{
return 1; // возвращаем факториал от нуля, который равен 1
}
else // во всех остальных случаях
{
return N * fact(N - 1); // выполняем рекурсивный вызовы функции
}
}
int main()
{
int N {0};
cout << "Input number for factorial" << endl;
cin >> N;
cout << "Factorial for number " << N << " = " << fact(N) << endl; // fact(N) - функция для вычисления факториала.
return 0;
}
Застосування рекурсивної лямбда функції
А тепер застосуємо для обчислення факторіалу рекурсивну лямбду функцію.
У сучасних стандартах C++ є два варіанти запису рекурсивних функцій:
- Із застосуванням std::function
- Без застосування std::function
Із застосуванням std::function
В даному випадку для застосування рекурсії лямбда функція повинна знати про свою власну структуру, щоб бути здатною захопити саму себе за посиланням, але лямбда функція – це анонімне оголошення об'єкта, яке якимось чином потрібно зробити явним. У цьому нам допоможе std::function, який допоможе визначити сигнатуру функції лямбда.
#include <iostream>
#include <functional> // Подключаем библиотеку для использования std::function
using namespace std;
int main()
{
int N {0};
// Объявление сигнатуры через std::function -> std::function<int(int)>
// Сигнатура функции int (int)
// [&fact] - Захват лямбды самой себя
std::function<int(int)> fact = [&fact](int N)
{
if(N < 0) // если пользователь ввел отрицательное число
{
return 0; // возвращаем ноль
}
else if (N == 0) // если пользователь ввел ноль,
{
return 1; // возвращаем факториал от нуля, который равен 1
}
else // во всех остальных случаях
{
return N * fact(N - 1); // выполняем рекурсивный вызовы функции
}
};
cout << "Input number for factorial" << endl;
cin >> N;
cout << "Factorial for number " << N << " = " << fact(N) << endl; // fact(N) - функция для вычисления факториала.
return 0;
}
Обмеження рекурсивних лямбд у тому, що ми можемо захопити лямбда функцію до того часу, поки невідома її сигнатура. Тобто застосувати auto відразу не вийде, оскільки auto робить висновок структури лямбди під час компіляції і якщо об'єкт лямбди не був сформований, то і захопити лямбду ми не можемо, а оскільки вона захоплює саму себе, але за цьому ще була скомпільована, те й структурі нічого не знає, а значить і захопити себе не може.
Тоді і приходить на допомогу std::function, який дозволяє зумовити сигнатуру лямбда функції, ініціалізуватися даною лямбда функцією і використовуватися як захоплююче посилання цієї ж лямбда функцією.
Без застосування std::function
Але це не означає, що зовсім не можна уникнути явного використання std::function для рекурсивних функцій. У стандарті C++14 з'явилася можливість визначати аргументи лямбда функцій як auto, рахунок чого лямбда функцію можна передавати як аргумент самої собі за посиланням. Вийде та сама рекурсивна лямбда функція, але з використанням виключно засобів мови програмування C++.
#include <iostream>
using namespace std;
int main()
{
int N {0};
// Объявление лямбды через auto
// Сигнатура лямбды int (auto&, int)
// auto& self - в данный аргументы будет передаваться лямбды функция для выполнения самой себя
auto fact = [](auto& self, int N)
{
if(N < 0) // если пользователь ввел отрицательное число
{
return 0; // возвращаем ноль
}
else if (N == 0) // если пользователь ввел ноль,
{
return 1; // возвращаем факториал от нуля, который равен 1
}
else // во всех остальных случаях
{
// Вызываем лямбду передавая в качестве аргумента лмябду по ссылке дальше в саму себя
return N * self(self, N - 1); // выполняем рекурсивный вызовы функции
}
};
cout << "Input number for factorial" << endl;
cin >> N;
// При первом вызове лямбды также нужно передать в качестве аргумента лямбду в саму себя
// fact(fact, N)
cout << "Factorial for number " << N << " = " << fact(fact, N) << endl; // fact(N) - функция для вычисления факториала.
return 0;
}
Висновок
До питання доцільності застосування рекурсивних лямбда функцій.
Не має сенсу оголошувати функцію або метод у класі, якщо ця функція використовується в одному місці коду. Це як мінімум ускладнюватиме інтерфейс класу, якщо на кожен чий писатимемо нові методи. Набагато краще оголосити лямбду всередині іншого методу, де вона має виконуватися. Це стосується всіх лямбда функцій як звичайних, так і рекурсивних.
Оголосити та одразу виконати лямбда функцію вже не вийде. Коли лямбда функція оголошується і відразу викликається, то як значення, що повертається, буде результат виконання лямбда функції, а не сам об'єкт лямбда функції, що означає, що захопити об'єкт лямбда функцію не вийде, а значить обидва представлених вище способу написання рекурсивних лямбда функцій не підходять.
