Cooking lambda functions in C ++ - Part 2 - Recursive lambda functions using the example of factorial calculation

factorial, lambda, C++, лямбда функция, факториал

In the previous article , we got acquainted with the structure of lambda functions, and now we'll play with lambdas, calculate the factorial, and consider how the lambda function can be applied for this.

Let's consider for the beginning the usual variant of factorial calculation, and also we will specify that such a recursive function.

Recursive function

A recursive function is that function that calls itself. This means that inside the function there is a call to itself, and infinite recursion can occur if the function code does not have the conditions for exiting recursion.

Here is an example of such an infinite recursive function, the program with which it terminates crash due to overflow of the call stack.

#include <iostream>

using namespace std;

void infiniteRecursiveFunction()
{
    cout << "Hello World!" << endl;
    infiniteRecursiveFunction();
}

int main()
{
    infiniteRecursiveFunction();
    return 0;
}

To prevent this from happening, you need to add an exit condition from the recursive function, for example, the achievement of a recursive call count of 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;
}

Now the recursive function will be completed correctly, thanks to the counter, the call stack will not overflow and the program will end without errors.

Factorial

And now let's define what factorial is.

The factorial is the product of natural numbers from 1 to the number itself (including a given number).
The factorial is denoted by the exclamation mark "!".

Examples:

  • 4! = 1 · 2 · 3 · 4 = 24
  • 5! = 1 · 2 · 3 · 4 · 5 = 120

Now write a function for calculating the factorial

long double fact(int N)
{
    if(N < 0) // if the user entered a negative number
    {
        return 0; // return zero
    }
    else if (N == 0) // if the user entered zero,
    {
        return 1; // return the factorial from zero, which is 1
    }
    else // in all other cases
    {
        return N * fact(N - 1); // we perform recursive function calls
    }
}

In this case, the function is written so that the factorial calculation is performed from the largest number and ends with zero. Then the correct exit from the recursion will be performed and the function will return the value of the factorial.

As a result, the code for calculating the factorial will look like this

#include <iostream>

using namespace std;

long double fact(int N)
{
    if(N < 0) // if the user entered a negative number
    {
        return 0; // return zero
    }
    else if (N == 0) // if the user entered zero,
    {
        return 1; // return the factorial from zero, which is 1
    }
    else // in all other cases
    {
        return N * fact(N - 1); // we perform recursive function calls
    }
}

int main()
{
    int N {0};
    cout << "Input number for factorial" << endl;
    cin >> N;
    cout << "Factorial for number " << N << " = " << fact(N) << endl; // fact(N) - function for calculating the factorial.
    return 0;
}

The use of recursive lambda functions

And now we apply the recursive lambda function to calculate the factorial.

In modern C ++ standards, there are two options for writing recursive functions:

  • Using std::function
  • Without using std::function

Using std::function

In this case, for the application of lambda recursion, the function should know about its own structure to be able to capture itself by reference, but the lambda function is an anonymous declaration of an object that somehow needs to be made explicit. In this we will help std::function , which will help determine the signature of the lambda function.

#include <iostream>
#include <functional>   // We connect the library to use std::function

using namespace std;

int main()
{
    int N {0};

    // Signature declaration via std::function -> std::function<int(int)>
    // Function signature int (int)
    // [&fact] - Capture the lambda itself
    std::function<int(int)> fact = [&fact](int N)
    {
        if(N < 0) // if the user entered a negative number
        {
            return 0; // return zero
        }
        else if (N == 0) // if the user entered zero,
        {
            return 1; // return the factorial from zero, which is 1
        }
        else // in all other cases
        {
            return N * fact(N - 1); // we perform recursive function calls
        }
    };

    cout << "Input number for factorial" << endl;
    cin >> N;
    cout << "Factorial for number " << N << " = " << fact(N) << endl; // fact(N) - function for calculating the factorial.
    return 0;
}

The limitation of recursive lambdas is that we can not capture the lambda function until its signature is known. That is, auto can not be used immediately, because auto makes the output of the lambda structure at compile time and if the lambda object was not formed, then we can not capture the lambda, and since it captures itself, but has not yet been compiled, structure does not know anything, and therefore can not capture itself.

Then, std::function comes to the rescue, which allows you to predefine the signature of the lambda function, initialize it with a lambda function, and be used as an invisible link to the same lambda function.

Without using std::function

But this does not mean that you can not do without the explicit use of std::function for recursive functions. In the standard C++14 , it became possible to define the arguments of lambda functions as auto, due to what the lambda function can be passed as an argument to itself by reference. The same recursive lambda function will be obtained, but using only C++ programming language tools.

#include <iostream>

using namespace std;

int main()
{
    int N {0};

    // Lambda declaration via auto
    // Lambda signature int (auto&, int)
    // auto& self - in this argument will be passed to the lambda function to perform itself
    auto fact = [](auto& self, int N)
    {
        if(N < 0) // if the user entered a negative number
        {
            return 0; // return zero
        }
        else if (N == 0) // if the user entered zero,
        {
            return 1; // return the factorial from zero, which is 1
        }
        else // in all other cases
        {
            // We call a lambda passing as an argument lambda on the link further in itself
            return N * self(self, N - 1); // we perform recursive function calls
        }
    };

    cout << "Input number for factorial" << endl;
    cin >> N;
    // When you first call a lambda, you also need to pass the lambda to itself as an argument
    // fact(fact, N)
    cout << "Factorial for number " << N << " = " << fact(fact, N) << endl; // fact(N) - function for calculating the factorial.
    return 0;
}

Conclusion

To the question of the expediency of applying recursive lambda functions.

It makes no sense to declare a function or method in a class if this function is used in one single place in the code. This will at least complicate the interface of the class, if we write new methods for each sneeze. It is much better to declare a lambda within another method, where it must be executed. This applies to all lambda functions, both conventional and recursive.

Declare and immediately execute the lambda function is no longer possible. When the lambda function is declared and immediately called, then the return value is the result of executing the lambda function, and not the lambda object's function, which means that it will not be possible to capture the lambda object of the function, so both of the above ways of writing recursive lambda functions are not suitable.

We recommend hosting TIMEWEB
We recommend hosting TIMEWEB
Stable hosting, on which the social network EVILEG is located. For projects on Django we recommend VDS hosting.
Support the author Donate

Comments

Only authorized users can post comments.
Please, Log in or Sign up
Looking for a Job?
25,000.00 руб. - 30,000.00 руб.
Разработчик Qt/C++
Barnaul, Altai Krai, Russia

For registered users on the site there is a minimum amount of advertising

JuA
Sept. 17, 2019, 7:51 a.m.
Julija Aleksandrova

C++ - Test 001. The first program and data types

  • Result:33points,
  • Rating points-10
JuA
Sept. 17, 2019, 7:36 a.m.
Julija Aleksandrova

C ++ - Test 004. Pointers, Arrays and Loops

  • Result:10points,
  • Rating points-10
VD
Sept. 16, 2019, 10:47 a.m.
Viktor Dzen'kiv

C++ - Test 002. Constants

  • Result:75points,
  • Rating points2
Last comments
Sept. 17, 2019, 5:07 a.m.
Misha Lebedev

Кстати интересные темы нашёл тут https://emacsway.github.io/ru/django-framework/#django-models Может что полезного тоже Евгений найдёте
Sept. 17, 2019, 3:50 a.m.
Misha Lebedev

Доброго времени суток. Спасибо за хороший ответ, У меня ситуация така что в галлереи будет несколько миллионов фотографий с фильтрами и тегами , и я опасаюсь за производительност . Это ос…
Sept. 17, 2019, 2:23 a.m.
Evgenij Legotskoj

Добрый день. Да, я тоже читал ту статью в своё время и согласен с тем, что внешние ключи гораздо лучше, чем GenericForeignKey. Выборки в ряде случае работают быстрее. Но лично мне про…
Sept. 14, 2019, 4:08 p.m.
Misha Lebedev

Приветствую вас Евгений , давно наблюда за развитием вашего замечательного портала, много полезно тут нашел , переодически зачитываюсь. Теперь по сушеству, делаю портал и там идеально ложи…
Sept. 10, 2019, 3:38 p.m.
Evgenij Legotskoj

function view для модели Article и LikeDislike.LIKE будет выглядеть так def like(request, pk): obj = Article.objects.get(pk=pk) try: likedislike = LikeDislike.objects.get(cont…
Now discuss on the forum
p
Sept. 17, 2019, 4:02 a.m.
pstMem

Да, действительно нужно дебажить, по другому не словить исключение. Уже решил проблему, был выход за предел массива, не правильные входные данные, так что всегда проверяйте размер массива.
Sept. 17, 2019, 2:39 a.m.
Evgenij Legotskoj

Добрый день! На удалённом сервере вряд ли. Этот класс из core модуля, а удалённый сервер - это ещё и network модуль нужно подтягивать. Тут на удалэнном сервере нужно делать программу…
Sept. 17, 2019, 2:30 a.m.
Evgenij Legotskoj

Добрый день! Попробуйте toHex() А также создние QString с помощью from методов. Может быть QString::fromLatin1(). В документации на QString почти два десятка методов from, один из них…
m
Sept. 16, 2019, 12:54 p.m.
mihamuz

Однозначно PostgreSql не ниже 10 ки.
R
Sept. 16, 2019, 6:09 a.m.
RED_Spider

прочитайте https://doc.qt.io/archives/qt-5.11/osx-deployment.html QMAKE_POST_LINK += "~/Qt/5.12.0/clang_64/bin/macdeployqt $${TARGET}.app $$escape_expand( \\n\\t )"
EVILEG
About
Services
© EVILEG 2015-2019
Recommend hosting TIMEWEB