¿Qué es la recursividad?

La recursividad es un concepto muy utilizado en matemáticas y programación, en la que básicamente dice que para poder definir algo, dentro de la definición tiene que ir ese propio algo.

f(x)=z+f(x)

Vamos a explicarlo que no parece quedar muy claro. Voy a explicarlo con el ejemplo de los número factoriales, es el ejemplo más típico.

Para calcular el factorial de un número se multiplican todos los números comprendidos entre 1 ese número.

Por ejemplo, para calcular el factorial de 6 sería:

6!=1*2*3*4*5*6=720

La operación anterior la podríamos definir con recursividad diciendo:

          6!=5!*6=720 => n!=(n-1)!*n
        

Caso base

El caso base será una instrucción que parará la recursividad, y cuando estamos programando funciones recursivas es importantísimo, ya que si no establecemos el caso base entraremos en un bucle infinito en el que no se deja de llamar a la función recursiva.

En el ejemplo del factorial, tendremos que definir un número en el que para calcular su factorial no tendramos que recurrir al cálculo del factorial, por ejemplo, el factorial de 0 es 1.

Vamos a programar en TypeScript una función recursiva para calcular el factorial de un número n

function goAHead(n:number):number{
  if (n===0) return 1; //Caso base o instrucción de salida
  return n * goAHead(n-1);
}
console.log(goAHead(6)) //[LOG]: 720

Función recursiva para obtener una serie de Fibonacci

Una serie de Fibonacci es una serie de números que comienza con el 0 y con el 1 y se van obteniendo los siguientes números de la serie sumando los dos anteriores, es decir, una serie de Fibonacci sería:

0, 1, 1, 2, 3, 5, 8, 13, 21,...

Para escribir una función recursiva que resuelva una serie de Fibonacci de n valores sería:

function getFibonacci(elements:number, memo:number[]=[0,1]):number[]{
  if (elements<=0) return memo.slice(0,memo.length-2); //Caso base
    memo.push(memo[memo.length-1]+memo[memo.length-2]);
    return getFibonacci(elements-1,memo);
  }        
console.log(getFibonacci(8)) //[LOG]: [0, 1, 1, 2, 3, 5, 8, 13]

No todo va a ser bueno

La recursividad parece la panacea, pero tiene el inconveniente que consume más memoria y capacidad de cómputo que un bucle for.

El ejemplo de la serie de Fibonacci sería muy fácil hacerla con un bucle for y veríamos que es más eficiente. Para pocos elementos quizás no lo apreciaríamos, pero para mucho sí.

Hasta luego 🖖