Expresiones lambda recursivas en C++

Una expresión lambda recursiva es el proceso en el que una función se llama a sí misma directa o indirectamente se llama recursividad y la función correspondiente se llama función recursiva . Usando un algoritmo recursivo, ciertos problemas se pueden resolver con bastante facilidad. Ejemplos de tales problemas son Towers of Hanoi (TOH) , Inorder/Preorder/Postorder Tree Traversals , DFS of Graph , etc.

Una función recursiva es solo un tipo de estructura de bucle. La diferencia es que mantiene una pila de memoria por sí solo. Obviamente, debe tener una condición de interrupción como for y while loop . Por lo tanto, la función recursiva tiene la siguiente estructura:

function name(arguments)
{
    a base case (a breaking condition)   
    recursive code (the actual logic)
}

int fact(int n)
{
    // Base Case
    if (n < = 1)
        return 1;
    else    
        return n * fact(n - 1);    
}

C++ 11 introdujo expresiones lambda para permitirnos escribir una función en línea que se puede usar para fragmentos cortos de código que no se van a reutilizar y que no vale la pena nombrar. En su forma más simple, la expresión lambda se puede definir de la siguiente manera:

[ capture clause ] (parameters) -> return-type  
{   
   definition of method   
} 

Programa 1:

A continuación se muestra el programa para las expresiones lambda en el método sort() en C++:

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Driver code
int main()
{
    int arr[] = { 5, 2, 1, 4, 3 };
    sort(arr, arr + 5, [](int& a,
                          int& b) {
        // Instant lambda function
        return a > b;
    });
 
    for (int i = 0; i < 5; i++)
        cout << arr[i] << " ";
    return 0;
}

5 4 3 2 1 

Complejidad de tiempo: O(nlogn)

Espacio Auxiliar: O(1)

Explicación: Aquí, se usa la función lambda instantánea, que no se puede usar en otro método de clasificación , es decir, se debe volver a escribir el mismo código. Esta expresión lambda existe solo durante la ejecución del método sort(). Pero también es posible almacenar la expresión lambda en una variable (es mejor llamarla función), como se muestra a continuación. Al almacenarlo, se puede usar más y, por supuesto, también realizar recursividad.  

Programa 2:

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Stored lambda expression
auto cmp = [](int& a, int& b) {
    return a > b;
};
 
// Driver code
int main()
{
    int arr[] = { 5, 2, 3, 1, 4 };
    sort(arr, arr + 5, cmp);
 
    for (int i = 0; i < 5; i++)
        cout << arr[i] << " ";
 
    return 0;
}

5 4 3 2 1 

Complejidad de tiempo: O(nlogn)

Espacio Auxiliar: O(1)

Explicación: aquí, auto cmp es la función lambda almacenada que se puede usar en tantos métodos de clasificación.

Recursión usando Lambda: analicemos el concepto de recursión y las expresiones lambda juntas considerando la función recursiva a continuación:

Programa 3:

// C++ program to implement
// the above approach
#include <iostream>
using namespace std;
 
// Recursive function to print
// the digits of a number
void printReverse(int n)
{
    if (n == 0)
        return;
    cout << n % 10 << " ";
    printReverse(n / 10);
}
 
// Driver code
int main()
{
    int n = 12345;
    printReverse(n);
    return 0;
}

5 4 3 2 1 

Complejidad de tiempo: O (logn)

Espacio auxiliar: O (logn)

Explicación: Arriba está la función que imprime los dígitos de un número en orden inverso, usando recursividad. Lo mismo se puede hacer usando la expresión lambda.

Programa 4:

A continuación se muestra el programa C++ para implementar el código anterior mediante expresiones lambda: 

// C++ program to implement
// the above approach
#include <iostream>
using namespace std;
 
// Driver code
int main()
{
    int n = 12345;
 
    // Recursive lambda function to
    // print the digits of a number
    auto printReverse = [&]() {
        if (n == 0)
            return;
        cout << n % 10;
        n = n / 10;
        printReverse();
 
        // As it is a part of main body,
        // semicolon is must
    };
 
    printReverse();
    return 0;
}

Producción: 

Vaya, la función, definida usando el tipo de retorno automático, debe deducirse primero (el compilador debe poder determinar si el tipo de retorno automático se puede convertir en nulo o int o en algo más) 

Explicación: Aquí, cómo la función va a reconocer la variable n, incluso si no se pasa como argumento. Una lambda con una cláusula de captura vacía [ ] puede acceder solo a aquellas variables que son locales para ella. Aquí, se utiliza el cierre de captura [&], que permite que la función acceda a la variable n (se cambia el valor real de la variable n). Hay dos formas de resolver el error anterior:

1. Al pasar la función en sí, al argumento de la función:

A continuación se muestra el programa C++ para implementar el concepto anterior:

Programa 5: 

// C++ program to implement
// the above approach
#include <iostream>
using namespace std;
 
// Driver code
int main()
{
    int n = 12345;
 
    // Function itself as a parameter
    auto printReverse = [&](auto&& printReverse) {
        if (n == 0)
            return;
        cout << n % 10 << " ";
        n = n / 10;
        printReverse(printReverse);
    };
 
    // Function as an argument
    printReverse(printReverse);
    return 0;
}

5 4 3 2 1 

Complejidad de tiempo: O (logn)

Espacio auxiliar: O (logn)

2. Al declarar primero la función:

Declarar una función significa declarar su nombre y tipo de parámetros para informar a un compilador que hay una función llamada xyz, que escribirá su cuerpo más tarde.

Programa 6:

A continuación se muestra el programa C++ para implementar el concepto anterior: 

// C++ program to implement
// the above approach
#include <iostream>
using namespace std;
 
// Declaring of a function
void declaringFunction(string s);
 
// Driver code
int main()
{
    declaringFunction("Hello I am learning how to declare a function");
    return 0;
}
 
// Body of a function
void declaringFunction(string s)
{
    cout << s;
}

Hello I am learning how to declare a function

Complejidad del tiempo: O(1)

Espacio Auxiliar: O(1)

Programa 7:

Dado que es una función lambda, debe haber alguna forma única de declarar la función. A continuación se muestra el programa C++ para el mismo: 

// C++ program to implement
// the above approach
#include <functional>
#include <iostream>
using namespace std;
 
// Driver code
int main()
{
    int n = 12345;
 
    // Function < return type (parameter
    // types) > functionName
 
    // Don't forget to include functional
    // header
 
    // Declaration
    function<void()> printReverse;
 
    printReverse = [&]() {
        if (n == 0)
            return;
 
        // Defination
        cout << n % 10 << " ";
        n /= 10;
        printReverse();
    };
 
    printReverse();
}

5 4 3 2 1 

Complejidad de tiempo: O (logn)

Espacio auxiliar: O (logn)

Explicación: En el código anterior, primero, se declara la función printReverse, luego hemos definido su cuerpo. En lugar de eso, podemos declarar directamente la función y su cuerpo, lo que se conoce como definir una función. A continuación se muestra el programa C++ para implementar el enfoque anterior:

Programa 8:

// C++ program to implement
// the above approach
#include <functional>
#include <iostream>
using namespace std;
 
// Driver code
int main()
{
    int n = 12345;
 
    // Function < return type (parameter
    // types) > functionName
    function<void()> printReverse = [&]() {
        if (n == 0)
            return;
 
        // Declaration + Body
        cout << n % 10 << " ";
        n /= 10;
        printReverse();
    };
 
    printReverse();
}

5 4 3 2 1 

Complejidad de tiempo: O (logn)

Espacio auxiliar: O (logn)

Ejemplos:  a continuación se muestran algunos ejemplos de funciones recursivas que utilizan expresiones lambda.

Programa 9: 

// C++ program to implement
// the above approach
#include <iostream>
using namespace std;
 
// Driver code
int main()
{
    int n = 6;
 
    // Recursive Lambda function to
    // find the factorial of a number
    auto factorial = [&](auto&& factorial) {
        if (n == 1)
            return n;
        return n-- * factorial(factorial);
    };
 
    auto factorial2 = [](int n, auto&& factorial2) {
        if (n == 1)
            return n;
        return n * factorial2(n - 1, factorial2);
    };
 
    // Given n = 6
    cout << factorial(factorial) << endl;
 
    // Given n = 5
    cout << factorial2(5, factorial2);
}

720
120

Complejidad del tiempo: O(2 ⁿ )

Espacio Auxiliar: O(n)

Explicación: En la función factorial, se accede directamente a n usando la cláusula de captura [&]. En la función factorial2, n se pasa como argumento. Por lo tanto, no hay necesidad de la cláusula [&].

Programa 10:

// C++ program to implement
// the above approach
#include <iostream>
using namespace std;
 
// Driver code
int main()
{
    // Sorted array
    int arr[] = { 1, 2, 5, 7, 10, 12, 15 };
    int size = 7;
 
    // Item to be searched
    int key = 10;
 
    auto binarySearch = [&](int startIndex,
                            int endIndex,
                            auto&& binarySearch) {
        if (startIndex > endIndex)
            return -1;
        int midIndex = (startIndex + endIndex) / 2;
        if (arr[midIndex] == key)
            return midIndex;
        if (arr[midIndex] > key)
            return binarySearch(startIndex,
                                midIndex - 1,
                                binarySearch);
        if (arr[midIndex] < key)
            return binarySearch(midIndex + 1,
                                endIndex,
                                binarySearch);
        // Not found
        return -1;
    };
 
    int index = binarySearch(0, size - 1,
                             binarySearch);
    if (index == -1)
        cout << "Not found";
    else
        cout << "Found on index " << index;
 
    return 0;
}

Found on index 4

Complejidad de tiempo: O (logn)

Espacio Auxiliar: O(1)