Dardo – Recursividad

La recursividad en cualquier lenguaje de programación significa que una función se llama a sí misma. Se utiliza para resolver grandes problemas complejos dividiéndolos en subproblemas más pequeños. Dart también implementa la recursividad de manera similar.

En una función recursiva, la función se llama a sí misma repetidamente hasta que se alcanza una condición base. La función tiene básicamente dos partes.

• Recursivo: La parte recursiva se llama una y otra vez con un subproblema más pequeño.
• Base: La condición base se comprueba cada vez que se realiza una llamada de función. Si la función está en una condición base, se utiliza para proporcionar una solución.

La recursividad usa una pila para almacenar los valores/resultados de los subproblemas para luego devolverlos al problema principal. 

Para una revisión detallada de la recursividad, visite: https://www.geeksforgeeks.org/recursion/

Sintaxis:

void gfgRec()
{
    // Base code....

    gfgRec();

    // Some code...
}


void main()
{
    gfgRec();
}

Ejemplo:

Usaremos un programa para el enésimo número de Fibonacci para demostrar la recursividad en el dardo:

int Fib(int n){
  if(n<=1) //Base Condition
    return n;
  return Fib(n-1)+Fib(n-2);
}
  
  
void main() {
  print(Fib(6));
}

Producción:

8

Explicación:

De la figura podemos ver que la llamada a la función con n = 6 como parámetro, a su vez, se llama a sí misma con valores menores 5 y 4. Ellos mismos llaman a la función con valores menores hasta llegar a la condición base. Cuando se cumple la condición base, la función comienza a devolver los valores. Entonces, el resultado final es 8, que es la suma de la llamada a 5 y 4.

En el caso de la recursividad, el problema debe reducirse con cada nueva llamada de función, ya que el problema debe terminarse para devolver un resultado. Esta condición se denomina condición de Terminación en Recursión. En caso de que el problema no termine, puede conducir a un bucle infinito y, como podemos ver, estas llamadas de función usan memoria de pila para almacenar los valores temporales, pueden usar mucha memoria. Si la condición base no está definida o no se puede alcanzar, la función puede provocar un desbordamiento de la pila.

Algunas ventajas y desventajas de usar la recursividad

Ventajas de usar Recursión:

• La solución del problema usando recursividad es muy concisa y corta.
• Se usan fácilmente con problemas relacionados con árboles y gráficos.
• Reduce la complejidad temporal de los problemas.
• Reduce las llamadas a funciones innecesarias.

Desventajas de usar Recursión:

• El problema ocupa mucho espacio.
• La lógica puede ser compleja de entender.
• Cuando está atascado, es difícil de depurar.

Ahora usaremos otro ejemplo para comprender mejor su implementación en dart. 

Ejemplo:

Estaremos escribiendo un programa para encontrar el factorial de un número usando la recursividad.

int Fact(int n){
  if(n<=1) //Base Condition
    return 1;
  return n*Fact(n-1);
}
  
  
void main() {
  print(Fact(8));
}

Producción:

40320

Explicación:

De la figura, podemos inferir que la función Fact se llama a sí misma hasta que se alcanza la condición base, es decir, devolvimos la función con una multiplicación del valor ‘n’ con el valor de una función con valor ‘n-1’ hasta el valor de n se vuelve igual a 1. Por último, devolvemos el valor de la función deseada.