recursividad – Part 3

¿Qué es la recursividad?  
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 resuelve un problema particular llamando a una copia de sí misma y resolviendo subproblemas más pequeños de los problemas originales. Se pueden generar muchas más llamadas recursivas cuando sea necesario. Es esencial saber que debemos proporcionar un caso determinado para terminar este proceso de recursión. Entonces podemos decir que cada vez que la función se llama a sí misma con una versión más simple del problema original.

Necesidad de recursividad

La recursividad es una técnica asombrosa con la ayuda de la cual podemos reducir la longitud de nuestro código y hacerlo más fácil de leer y escribir. Tiene ciertas ventajas sobre la técnica de iteración que se discutirá más adelante. Una tarea que se puede definir con su subtarea similar, la recursividad es una de las mejores soluciones para ello. Por ejemplo; El Factorial de un número.

Propiedades de la recursividad:

• Realizar las mismas operaciones varias veces con diferentes entradas.
• En cada paso, intentamos entradas más pequeñas para hacer el problema más pequeño.
• Se necesita una condición base para detener la recursividad, de lo contrario, se producirá un bucle infinito.

Una interpretación matemática

Consideremos un problema que tiene un programador para determinar la suma de los primeros n números naturales, hay varias formas de hacerlo, pero el enfoque más simple es simplemente agregar los números comenzando desde 1 hasta n. Así que la función simplemente se ve así,

enfoque (1) – Simplemente agregando uno por uno

f(n) = 1 + 2 + 3 +……..+ n

pero hay otro enfoque matemático para representar esto,

enfoque (2) – suma recursiva 

f(n) = 1 n=1

f(n) = n + f(n-1) n>1

Hay una diferencia simple entre el enfoque (1) y el enfoque (2) y es que en el enfoque (2) la función » f() » en sí misma se llama dentro de la función, por lo que este fenómeno se llama recursión, y la función que contiene La recursión se llama función recursiva, al final, esta es una gran herramienta en la mano de los programadores para codificar algunos problemas de una manera mucho más fácil y eficiente.

¿Cómo se almacenan las funciones recursivas en la memoria?

La recursividad usa más memoria, porque la función recursiva agrega a la pila con cada llamada recursiva y mantiene los valores allí hasta que finaliza la llamada. La función recursiva utiliza la estructura LIFO (ÚLTIMO LLENADO, PRIMERO EN SALIDA) al igual que la estructura de datos de la pila. https://www.geeksforgeeks.org/stack-data-structure/
 

¿Cuál es la condición base en la recursividad?  
En el programa recursivo, se proporciona la solución al caso base y la solución al problema más grande se expresa en términos de problemas más pequeños. 
 

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

En el ejemplo anterior, se define el caso base para n < = 1 y el valor más grande de un número se puede resolver convirtiéndolo en uno más pequeño hasta alcanzar el caso base.

¿Cómo se resuelve un problema particular usando la recursividad?  
La idea es representar un problema en términos de uno o más problemas más pequeños y agregar una o más condiciones base que detengan la recursividad. Por ejemplo, calculamos el factorial n si conocemos el factorial de (n-1). El caso base para el factorial sería n = 0. Devolvemos 1 cuando n = 0. 

¿Por qué se produce un error de desbordamiento de pila en la recursividad?  
Si el caso base no se alcanza o no se define, entonces puede surgir el problema de desbordamiento de pila. Tomemos un ejemplo para entender esto.

int fact(int n)
{
    // wrong base case (it may cause
    // stack overflow).
    if (n == 100) 
        return 1;

    else
        return n*fact(n-1);
}

Si se llama fact(10), llamará fact(9), fact(8), fact(7), y así sucesivamente, pero el número nunca llegará a 100. Por lo tanto, no se alcanza el caso base. Si estas funciones agotan la memoria en la pila, se producirá un error de desbordamiento de pila. 

¿Cuál es la diferencia entre recursividad directa e indirecta?  
Una función fun se llama recursiva directa si llama a la misma función fun. Una función fun se llama recursiva indirecta si llama a otra función, digamos fun_new y fun_new llama a fun directa o indirectamente. La diferencia entre recursividad directa e indirecta se ilustra en la Tabla 1. 

// An example of direct recursion
void directRecFun()
{
    // Some code....

    directRecFun();

    // Some code...
}

// An example of indirect recursion
void indirectRecFun1()
{
    // Some code...

    indirectRecFun2();

    // Some code...
}
void indirectRecFun2()
{
    // Some code...

    indirectRecFun1();

    // Some code...
}

¿Cuál es la diferencia entre recursión con cola y sin cola?  
Una función recursiva es recursiva de cola cuando una llamada recursiva es lo último que ejecuta la función. Consulte el artículo de recursión de cola para obtener más detalles. 

¿Cómo se asigna la memoria a diferentes llamadas de función en recursividad?  
Cuando se llama a cualquier función desde main(), la memoria se le asigna en la pila. Una función recursiva se llama a sí misma, la memoria para una función llamada se asigna encima de la memoria asignada a la función que llama y se crea una copia diferente de las variables locales para cada función llamada. Cuando se alcanza el caso base, la función devuelve su valor a la función que la llama y la memoria se desasigna y el proceso continúa.
Tomemos el ejemplo de cómo funciona la recursión tomando una función simple. 

// A C++ program to demonstrate working of
// recursion
#include <bits/stdc++.h>
using namespace std;
 
void printFun(int test)
{
    if (test < 1)
        return;
    else {
        cout << test << " ";
        printFun(test - 1); // statement 2
        cout << test << " ";
        return;
    }
}
 
// Driver Code
int main()
{
    int test = 3;
    printFun(test);
}

// A Java program to demonstrate working of
// recursion
class GFG {
    static void printFun(int test)
    {
        if (test < 1)
            return;
        else {
            System.out.printf("%d ", test);
            printFun(test - 1); // statement 2
            System.out.printf("%d ", test);
            return;
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int test = 3;
        printFun(test);
    }
}
 
// This code is contributed by
// Smitha Dinesh Semwal

# A Python 3 program to
# demonstrate working of
# recursion
 
 
def printFun(test):
 
    if (test < 1):
        return
    else:
 
        print(test, end=" ")
        printFun(test-1)  # statement 2
        print(test, end=" ")
        return
 
# Driver Code
test = 3
printFun(test)
 
# This code is contributed by
# Smitha Dinesh Semwal

// A C# program to demonstrate
// working of recursion
using System;
 
class GFG {
 
    // function to demonstrate
    // working of recursion
    static void printFun(int test)
    {
        if (test < 1)
            return;
        else {
            Console.Write(test + " ");
 
            // statement 2
            printFun(test - 1);
 
            Console.Write(test + " ");
            return;
        }
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int test = 3;
        printFun(test);
    }
}
 
// This code is contributed by Anshul Aggarwal.

<?php
// PHP program to demonstrate
// working of recursion
 
// function to demonstrate
// working of recursion
function printFun($test)
{
    if ($test < 1)
        return;
    else
    {
        echo("$test ");
         
        // statement 2
        printFun($test-1);
         
        echo("$test ");
        return;
    }
}
 
// Driver Code
$test = 3;
printFun($test);
 
// This code is contributed by
// Smitha Dinesh Semwal.
?>

<script>
 
// JavaScript program to demonstrate working of
// recursion
 
function printFun(test)
    {
        if (test < 1)
            return;
        else {
            document.write(test + " ");
            printFun(test - 1); // statement 2
            document.write(test + " ");
            return;
        }
    }
 
// Driver code
    let test = 3;
    printFun(test);
 
</script>

Producción : 

3 2 1 1 2 3

Cuando se llama a printFun(3) desde main(), la memoria se asigna a printFun(3) y una prueba de variable local se inicializa a 3 y las declaraciones 1 a 4 se colocan en la pila como se muestra en el diagrama a continuación. Primero imprime ‘3’. En la declaración 2, se llama a printFun(2 ) y se asigna memoria a printFun(2) y una prueba de variable local se inicializa a 2 y las declaraciones 1 a 4 se colocan en la pila. De manera similar, printFun(2) llama a printFun(1) y printFun(1) llama a printFun(0) . printFun(0) va a la sentencia if y vuelve a printFun(1) . Las sentencias restantes de printFun(1)se ejecutan y vuelve a printFun(2) y así sucesivamente. En la salida, se imprimen los valores de 3 a 1 y luego se imprimen de 1 a 3. La pila de memoria se muestra en el siguiente diagrama.

Recursión VS Iteración

Ahora, analicemos algunos problemas prácticos que se pueden resolver mediante el uso de la recursividad y comprendamos su funcionamiento básico. Para una comprensión básica, lea los siguientes artículos. 
Comprensión básica de recursividad.
Problema 1: Escriba un programa y una relación de recurrencia para encontrar la serie de Fibonacci de n donde n>2. 
Ecuación matemática:  

n if n == 0, n == 1;      
fib(n) = fib(n-1) + fib(n-2) otherwise;

Relación de recurrencia: 

T(n) = T(n-1) + T(n-2) + O(1)

Programa recursivo: 

Input: n = 5 
Output:
Fibonacci series of 5 numbers is : 0 1 1 2 3

Implementación: 

// C++ code to implement Fibonacci series
#include <bits/stdc++.h>
using namespace std;
 
// Function for fibonacci
 
int fib(int n)
{
    // Stop condition
    if (n == 0)
        return 0;
 
    // Stop condition
    if (n == 1 || n == 2)
        return 1;
 
    // Recursion function
    else
        return (fib(n - 1) + fib(n - 2));
}
 
// Driver Code
int main()
{
    // Initialize variable n.
    int n = 5;
    cout<<"Fibonacci series of 5 numbers is: ";
 
    // for loop to print the fibonacci series.
    for (int i = 0; i < n; i++)
    {
        cout<<fib(i)<<" ";
    }
    return 0;
}

// C code to implement Fibonacci series
#include <stdio.h>
 
// Function for fibonacci
int fib(int n)
{
    // Stop condition
    if (n == 0)
        return 0;
 
    // Stop condition
    if (n == 1 || n == 2)
        return 1;
 
    // Recursion function
    else
        return (fib(n - 1) + fib(n - 2));
}
 
// Driver Code
int main()
{
    // Initialize variable n.
    int n = 5;
    printf("Fibonacci series "
           "of %d numbers is: ",
           n);
 
    // for loop to print the fibonacci series.
    for (int i = 0; i < n; i++) {
        printf("%d ", fib(i));
    }
    return 0;
}

// Java code to implement Fibonacci series
import java.util.*;
 
class GFG
{
 
// Function for fibonacci
static int fib(int n)
{
    // Stop condition
    if (n == 0)
        return 0;
 
    // Stop condition
    if (n == 1 || n == 2)
        return 1;
 
    // Recursion function
    else
        return (fib(n - 1) + fib(n - 2));
}
 
// Driver Code
public static void main(String []args)
{
   
    // Initialize variable n.
    int n = 5;
    System.out.print("Fibonacci series of 5 numbers is: ");
 
    // for loop to print the fibonacci series.
    for (int i = 0; i < n; i++)
    {
        System.out.print(fib(i)+" ");
    }
}
}
 
// This code is contributed by rutvik_56.

# Python code to implement Fibonacci series
 
# Function for fibonacci
def fib(n):
 
    # Stop condition
    if (n == 0):
        return 0
 
    # Stop condition
    if (n == 1 or n == 2):
        return 1
 
    # Recursion function
    else:
        return (fib(n - 1) + fib(n - 2))
 
 
# Driver Code
 
# Initialize variable n.
n = 5;
print("Fibonacci series of 5 numbers is :",end=" ")
 
# for loop to print the fibonacci series.
for i in range(0,n):
    print(fib(i),end=" ")

using System;
 
public class GFG
{
 
  // Function for fibonacci
  static int fib(int n)
  {
 
    // Stop condition
    if (n == 0)
      return 0;
 
    // Stop condition
    if (n == 1 || n == 2)
      return 1;
 
    // Recursion function
    else
      return (fib(n - 1) + fib(n - 2));
  }
 
  // Driver Code
  static public void Main ()
  {
 
    // Initialize variable n.
    int n = 5;
    Console.Write("Fibonacci series of 5 numbers is: ");
 
    // for loop to print the fibonacci series.
    for (int i = 0; i < n; i++)
    {
      Console.Write(fib(i) + " ");
    }
  }
}
 
// This code is contributed by avanitrachhadiya2155

<script>
// JavaScript code to implement Fibonacci series
 
// Function for fibonacci
function fib(n)
{
   // Stop condition
   if(n == 0)
     return 0;
    
   // Stop condition
   if(n == 1 || n == 2)
      return 1;
   // Recursion function
   else
      return fib(n-1) + fib(n-2);
}
 
// Initialize variable n.
let n = 5;
 
document.write("Fibonacci series of 5 numbers is: ");
 
// for loop to print the fibonacci series.
for(let i = 0; i < n; i++)
{
    document.write(fib(i) + " ");
}
 
</script>

Fibonacci series of 5 numbers is: 0 1 1 2 3 

Complejidad del tiempo: O(2 ⁿ )

Espacio Auxiliar: O(n)

Aquí está el árbol recursivo para la entrada 5 que muestra una imagen clara de cómo un problema grande puede resolverse en problemas más pequeños. 
fib(n) es una función de Fibonacci. La complejidad temporal del programa dado puede depender de la llamada a la función. 

fib(n) -> nivel CBT (UB) -> 2^n-1 Nodes -> 2^n llamada de función -> 2^n*O(1) -> T(n) = O(2^n)  

Para el mejor caso. 

T(n) =   θ(2^n\2)

Laboral: 

Problema 2: Escriba un programa y una relación de recurrencia para encontrar el factorial de n donde n>2. 
Ecuación matemática: 

1 if n == 0 or n == 1;      
f(n) = n*f(n-1) if n> 1;

Relación de recurrencia: 

T(n) = 1 for n = 0
T(n) = 1 + T(n-1) for n > 0

Programa Recursivo:  
Entrada: n = 5 
Salida: 
factorial de 5 es: 120
Implementación: 

// C++ code to implement factorial
#include <bits/stdc++.h>
using namespace std;
 
// Factorial function
int f(int n)
{
    // Stop condition
    if (n == 0 || n == 1)
        return 1;
 
    // Recursive condition
    else
        return n * f(n - 1);
}
 
// Driver code
int main()
{
    int n = 5;
    cout<<"factorial of "<<n<<" is: "<<f(n);
    return 0;
}

// C code to implement factorial
#include <stdio.h>
 
// Factorial function
int f(int n)
{
    // Stop condition
    if (n == 0 || n == 1)
        return 1;
 
    // Recursive condition
    else
        return n * f(n - 1);
}
 
// Driver code
int main()
{
    int n = 5;
    printf("factorial of %d is: %d", n, f(n));
    return 0;
}

// Java code to implement factorial
public class GFG
{
 
  // Factorial function
  static int f(int n)
  {
 
    // Stop condition
    if (n == 0 || n == 1)
      return 1;
 
    // Recursive condition
    else
      return n * f(n - 1);
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int n = 5;
    System.out.println("factorial of " + n + " is: " + f(n));
  }
}
 
// This code is contributed by divyesh072019.

# Python3 code to implement factorial
 
# Factorial function
def f(n):
 
    # Stop condition
    if (n == 0 or n == 1):
        return 1;
 
    # Recursive condition
    else:
        return n * f(n - 1);
 
 
# Driver code
if __name__=='__main__':
 
    n = 5;
    print("factorial of",n,"is:",f(n))
     
    # This code is contributed by pratham76.

// C# code to implement factorial
using System;
class GFG {
 
  // Factorial function
  static int f(int n)
  {
    // Stop condition
    if (n == 0 || n == 1)
      return 1;
 
    // Recursive condition
    else
      return n * f(n - 1);
  }
 
  // Driver code
  static void Main()
  {
    int n = 5;
    Console.WriteLine("factorial of " + n + " is: " + f(n));
  }
}
 
// This code is contributed by divyeshrabadiya07.

<script>
// JavaScript code to implement factorial
 
// Factorial function
function f(n)
{
   // Stop condition
   if(n == 0 || n == 1)
     return 1;
      
   // Recursive condition
   else
      return n*f(n-1);
}
 
// Initialize variable n.
let n = 5;
document.write("factorial of "+ n +" is: " + f(n));
 
// This code is contributed by probinsah.
</script>

factorial of 5 is: 120

Complejidad temporal: O(2 ⁿ ).

Espacio Auxiliar: O(n)

Laboral: 
 

Diagrama de la función de recursividad factorial para la entrada del usuario 5.

¿Cuáles son las desventajas de la programación recursiva sobre la programación iterativa?  
Tenga en cuenta que tanto los programas recursivos como los iterativos tienen el mismo poder de resolución de problemas, es decir, todos los programas recursivos se pueden escribir de forma iterativa y viceversa. El programa recursivo tiene mayores requisitos de espacio que el programa iterativo ya que todas las funciones permanecerán en la pila hasta que se alcance el caso base. También tiene mayores requisitos de tiempo debido a las llamadas a funciones y la sobrecarga de retorno.

Además, debido a la menor longitud del código, los códigos son difíciles de entender y, por lo tanto, se debe tener mucho cuidado al escribir el código. La computadora puede quedarse sin memoria si las llamadas recursivas no se verifican correctamente.

¿Cuáles son las ventajas de la programación recursiva sobre la programación iterativa?  
La recursión proporciona una forma limpia y sencilla de escribir código. Algunos problemas son inherentemente recursivos como recorridos de árboles, Torre de Hanoi , etc. Para tales problemas, se prefiere escribir código recursivo. Podemos escribir dichos códigos también iterativamente con la ayuda de una estructura de datos de pila. Por ejemplo, consulte Recorrido de árbol en orden sin recursividad , Torre iterativa de Hanoi .

Resumen de recursividad:

• Hay dos tipos de casos en recursividad, es decir, caso recursivo y caso base.
• El caso base se usa para terminar la función recursiva cuando el caso resulta ser verdadero.
• Cada llamada recursiva hace una nueva copia de ese método en la memoria de la pila.
• La recursividad infinita puede llevar a quedarse sin memoria de pila.
• Ejemplos de algoritmos recursivos: Merge Sort, Quick Sort, Tower of Hanoi, Fibonacci Series, Factorial Problem, etc.

Problemas de práctica basados ​​en resultados para principiantes:  
Preguntas de práctica para recursividad | Juego 1  
Preguntas de práctica para recursividad | Juego de 2  
preguntas de práctica para recursividad | Juego de 3  
preguntas de práctica para recursividad | Juego de 4  
preguntas de práctica para recursividad | Conjunto de 5  
preguntas de práctica para la recursividad | Juego de 6  
preguntas de práctica para recursividad | Juego 7
Cuestionario sobre recursividad  
Práctica de codificación sobre recursividad:  
todos los artículos sobre 
recursividad Problemas de práctica recursiva con soluciones
Este artículo es una contribución de Sonal Tuteja . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.orgo envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.