31º agosto 2020

Recursión y pila

Volvamos a las funciones y estudiémoslas más en profundidad.

Nuestro primer tema será la recursividad.

Si no eres nuevo en la programación, probablemente te resulte familiar y podrías saltarte este capítulo.

La recursión es un patrón de programación que es útil en situaciones en las que una tarea puede dividirse naturalmente en varias tareas del mismo tipo, pero más simples. O cuando una tarea se puede simplificar en una acción fácil más una variante más simple de la misma tarea. O, como veremos pronto, tratar con ciertas estructuras de datos.

Cuando una función resuelve una tarea, en el proceso puede llamar a muchas otras funciones. Un caso parcial de esto es cuando una función se llama a sí misma. Eso se llama recursividad.

Dos formas de pensar

Para comenzar con algo simple, escribamos una función pow(x, n) que eleve x a una potencia natural den. En otras palabras, multiplica x por sí mismo n veces.

pow(2, 2) = 4
pow(2, 3) = 8
pow(2, 4) = 16

Hay dos formas de implementarlo.

  1. Pensamiento iterativo: el bucle for:

    function pow(x, n) {
      let result = 1;
    
      // multiplicar el resultado por x n veces en el ciclo
      for (let i = 0; i < n; i++) {
        result *= x;
      }
    
      return result;
    }
    
    alert( pow(2, 3) ); // 8
  2. Pensamiento recursivo: simplifica la tarea y se llama a sí mismo:

    function pow(x, n) {
      if (n == 1) {
        return x;
      } else {
        return x * pow(x, n - 1);
      }
    }
    
    alert( pow(2, 3) ); // 8

Note cómo la variante recursiva es fundamentalmente diferente.

Cuando se llama a pow(x, n), la ejecución se divide en dos ramas:

              if n==1  = x
             /
pow(x, n) =
             \
              else     = x * pow(x, n - 1)
  1. Si n == 1, entonces todo es trivial. Se llama la base de la recursividad, porque produce inmediatamente el resultado obvio: pow (x, 1) es igual a x.
  2. De lo contrario, podemos representar pow (x, n) como x * pow (x, n - 1). En matemáticas, uno escribiría xn = x * x n-1. Esto se llama un paso recursivo: transformamos la tarea en una acción más simple (multiplicación por x) y una llamada más simple de la misma tarea (pow con menor n). Los siguientes pasos lo simplifican más y más hasta que n llegue a1.

También podemos decir que pow * recursivamente se llama a sí mismo * hasta quen == 1.

Por ejemplo, para calcular pow (2, 4) la variante recursiva realiza estos pasos:

  1. pow(2, 4) = 2 * pow(2, 3)
  2. pow(2, 3) = 2 * pow(2, 2)
  3. pow(2, 2) = 2 * pow(2, 1)
  4. pow(2, 1) = 2

Por lo tanto, la recursión reduce una llamada de función a una más simple y luego – a una más simple, y así sucesivamente, hasta que el resultado se vuelve obvio.

La recursión suele ser más corta

Una solución recursiva suele ser más corta que una iterativa.

Aquí podemos reescribir lo mismo usando el operador condicional ? En lugar de if para hacer que pow (x, n)sea más conciso y aún bastante legible:

función pow (x, n) {
   volver (n == 1)? x: (x * pow (x, n - 1));
}

El número máximo de llamadas anidadas (incluida la primera) se llama profundidad de recursión. En nuestro caso, será exactamente n.

La profundidad máxima de recursión está limitada por el motor de JavaScript. Podemos confiar en que sea 10000, algunos motores permiten más, pero 100000 probablemente esté fuera del límite para la mayoría de ellos. Hay optimizaciones automáticas que ayudan a aliviar esto (“optimizaciones de llamadas de cola”), pero aún no son compatibles en todas partes y funcionan solo en casos simples.

Eso limita la aplicación de la recursividad, pero sigue siendo muy amplia. Hay muchas tareas donde la forma recursiva de pensar proporciona un código más simple, más fácil de mantener.

El contexto de ejecución y pila

Ahora examinemos cómo funcionan las llamadas recursivas. Para eso observaremos lo que sucede debajo del sombrero en las funciones.

La información sobre el proceso de ejecución de una función en ejecución se almacena en su contexto de ejecución.

El contexto de ejecución es una estructura de datos interna que contiene detalles sobre la ejecución de una función: dónde está el flujo de control ahora, las variables actuales, el valor de this (no lo usamos aquí) y algunos otros detalles internos.

Una llamada de función tiene exactamente un contexto de ejecución asociado.

Cuando una función realiza una llamada anidada, sucede lo siguiente:

  • La función actual está en pausa.
  • El contexto de ejecución asociado con él se recuerda en una estructura de datos especial llamada pila de contexto de ejecución.
  • La llamada anidada se ejecuta.
  • Una vez que finaliza, el antiguo contexto de ejecución se recupera de la pila y la función externa se reanuda desde donde se detuvo.

Veamos qué sucede durante la llamada de pow (2, 3).

pow (2, 3)

Al comienzo de la llamada pow (2, 3) el contexto de ejecución almacenará variables: x = 2, n = 3, el flujo de ejecución está en la línea 1 de la función.

Podemos esbozarlo como:

  • Context: { x: 2, n: 3, at line 1 } pow(2, 3)

Ahí es cuando la función comienza a ejecutarse. La condición n == 1 es falsa, por lo que el flujo continúa en la segunda rama deif:

function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

alert( pow(2, 3) );

Las variables son las mismas, pero la línea cambia, por lo que el contexto es ahora:

  • Context: { x: 2, n: 3, at line 5 } pow(2, 3)

Para calcular x * pow (x, n - 1), necesitamos hacer una sub-llamada de pow con nuevos argumentospow (2, 2).

pow (2, 2)

Para hacer una llamada anidada, JavaScript recuerda el contexto de ejecución actual en la pila de contexto de ejecución.

Aquí llamamos a la misma función pow, pero no importa en absoluto. El proceso es el mismo para todas las funciones:

  1. El contexto actual se “recuerda” en la parte superior de la pila.
  2. El nuevo contexto se crea para la subllamada.
  3. Cuando finaliza la subllamada – el contexto anterior se extrae de la pila y su ejecución continúa.

Aquí está la pila de contexto cuando ingresamos la subllamada pow (2, 2):

  • Context: { x: 2, n: 2, at line 1 } pow(2, 2)
  • Context: { x: 2, n: 3, at line 5 } pow(2, 3)

El nuevo contexto de ejecución actual está en la parte superior (y en negrita), y los contextos recordados anteriores están debajo.

Cuando terminamos la subllamada – es fácil reanudar el contexto anterior, ya que mantiene ambas variables y el lugar exacto del código donde se detuvo. Aquí en la imagen usamos la palabra “línea”, pero por supuesto es más precisa.

Por favor tome nota:

En la figura usamos la palabra línea “line” porque en nuestro ejemplo hay solo una subllamada en línea, pero generalmente una simple línea de código puede contener múltiples subllamadas, como pow(…) + pow(…) + otraCosa(…).

Entonces sería más preciso decir que la ejecución se reanuda “inmediatamente después de la subllamada”.

pow(2, 1)

El proceso se repite: se realiza una nueva subllamada en la línea 5, ahora con argumentosx = 2, n = 1.

Se crea un nuevo contexto de ejecución, el anterior se coloca en la parte superior de la pila:

  • Context: { x: 2, n: 1, at line 1 } pow(2, 1)
  • Context: { x: 2, n: 2, at line 5 } pow(2, 2)
  • Context: { x: 2, n: 3, at line 5 } pow(2, 3)

Hay 2 contextos antiguos ahora y 1 actualmente en ejecución para pow (2, 1).

La salida

Durante la ejecución de pow (2, 1), a diferencia de antes, la condición n == 1 es verdadera, por lo que la primera rama de if funciona:

function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

No hay más llamadas anidadas, por lo que la función finaliza y devuelve 2.

Cuando finaliza la función, su contexto de ejecución ya no es necesario, por lo que se elimina de la memoria. El anterior se restaura desde la parte superior de la pila:

  • Context: { x: 2, n: 2, at line 5 } pow(2, 2)
  • Context: { x: 2, n: 3, at line 5 } pow(2, 3)

Se reanuda la ejecución de pow (2, 2). Tiene el resultado de la subllamada pow (2, 1), por lo que también puede finalizar la evaluación de x * pow (x, n - 1), devolviendo 4.

Luego se restaura el contexto anterior:

  • Context: { x: 2, n: 3, at line 5 } pow(2, 3)

Cuando termina, tenemos un resultado de pow (2, 3) = 8.

La profundidad de recursión en este caso fue: 3.

Como podemos ver en las ilustraciones anteriores, la profundidad de recursión es igual al número máximo de contexto en la pila.

Tenga en cuenta los requisitos de memoria. Los contextos toman memoria. En nuestro caso, elevar a la potencia de n realmente requiere la memoria para n contextos, para todos los valores más bajos de n.

Un algoritmo basado en bucles ahorra más memoria:

function pow(x, n) {
  let result = 1;

  for (let i = 0; i < n; i++) {
    result *= x;
  }

  return result;
}

El iterativo pow utiliza un contexto único que cambia i y result en el proceso. Sus requisitos de memoria son pequeños, fijos y no dependen de n.

Cualquier recursión puede reescribirse como un bucle. La variante de bucle generalmente se puede hacer más efectiva.

… Pero a veces la reescritura no es trivial, especialmente cuando la función utiliza sub-llamadas recursivas diferentes según las condiciones y combina sus resultados o cuando la ramificación es más compleja. Y la optimización puede ser innecesaria y no merece la pena el esfuerzo.

La recursión puede dar un código más corto, más fácil de entender y mantener. No se requieren optimizaciones en todos los lugares, principalmente necesitamos un buen código, por eso se usa.

Recorridos recursivos

Otra gran aplicación de la recursión es un recorrido recursivo.

Imagina que tenemos una empresa. La estructura del personal se puede presentar como un objeto:

let company = {
  sales: [{
    name: 'John',
    salary: 1000
  }, {
    name: 'Alice',
    salary: 1600
  }],

  development: {
    sites: [{
      name: 'Peter',
      salary: 2000
    }, {
      name: 'Alex',
      salary: 1800
    }],

    internals: [{
      name: 'Jack',
      salary: 1300
    }]
  }
};

En otras palabras, una empresa tiene departamentos.

  • Un departamento puede tener una gran variedad de personal. Por ejemplo, el departamento de ventas sales tiene 2 empleados: John y Alice.

  • O un departamento puede dividirse en subdepartamentos, como development tiene dos ramas: sites e internals. Cada uno de ellos tiene su propio personal.

  • También es posible que cuando un subdepartamento crece, se divida en subdepartamentos (o equipos).

    Por ejemplo, el departamento sites en el futuro puede dividirse en equipos para siteA y siteB. Y ellos, potencialmente, pueden dividirse aún más. Eso no está en la imagen, solo algo a tener en cuenta.

Ahora digamos que queremos una función para obtener la suma de todos los salarios. ¿Cómo podemos hacer eso?

Un enfoque iterativo no es fácil, porque la estructura no es simple. La primera idea puede ser hacer un bucle for sobre company con un sub-bucle anidado sobre departamentos de primer nivel. Pero luego necesitamos más sub-bucles anidados para iterar sobre el personal en los departamentos de segundo nivel como sites. …¿Y luego otro sub-bucle dentro de los de los departamentos de tercer nivel que podrían aparecer en el futuro? ¿Deberíamos parar en el nivel 3 o hacer 4 niveles de bucles? Si ponemos 3-4 bucles anidados en el código para atravesar un solo objeto, se vuelve bastante feo.

Probemos la recursividad.

Como podemos ver, cuando nuestra función hace que un departamento sume, hay dos casos posibles:

  1. O bien es un departamento “simple” con una array de personas – entonces podemos sumar los salarios en un bucle simple.
  2. O es un objeto con subdepartamentos N, entonces podemos hacer llamadas recursivas N para obtener la suma de cada uno de los subdepartamentos y combinar los resultados.

El primer caso es la base de la recursividad, el caso trivial, cuando obtenemos un “array”

El segundo caso, cuando obtenemos un objeto, es el paso recursivo. Una tarea compleja se divide en subtareas para departamentos más pequeños. A su vez, pueden dividirse nuevamente, pero tarde o temprano la división terminará en (1).

El algoritmo es probablemente aún más fácil de leer desde el código:

let company = { // el mismo objeto, comprimido por brevedad
  sales: [{name: 'John', salary: 1000}, {name: 'Alice', salary: 600 }],
  development: {
    sites: [{name: 'Peter', salary: 2000}, {name: 'Alex', salary: 1800 }],
    internals: [{name: 'Jack', salary: 1300}]
  }
};

// La función para hacer el trabajo
function sumSalaries(department) {
  if (Array.isArray(department)) { // caso (1)
    return department.reduce((prev, current) => prev + current.salary, 0); // suma del Array
  } else { // caso (2)
    let sum = 0;
    for (let subdep of Object.values(department)) {
      sum += sumSalaries(subdep); // llama recursivamente a subdepartamentos, suma los resultados
    }
    return sum;
  }
}

alert(sumSalaries(company)); // 7700

El código es corto y fácil de entender (¿Quizás?). Ese es el poder de la recursividad. También funciona para cualquier nivel de anidamiento de subdepartamentos.

Aquí está el diagrama de llamadas:

Podemos ver fácilmente el principio: para un objeto {...} se realizan subllamadas, mientras que los Arrays [...] son las “hojas” del árbol recursivo, dan un resultado inmediato.

Tenga en cuenta que el código utiliza funciones inteligentes que hemos cubierto antes:

  • Método arr.reduce explicado en el capítulo Métodos con arrays para obtener la suma del Array.
  • Bucle for (val of Object.values (obj)) para iterar sobre los valores del objeto: Object.values devuelve una matriz de ellos.

Estructuras recursivas

Una estructura de datos recursiva (definida recursivamente) es una estructura que se replica en partes.

Lo acabamos de ver en el ejemplo de la estructura de la empresa anterior.

Una empresa departamento es:

  • O una gran variedad de personas.
  • O un objeto con departamentos.

Para los desarrolladores web hay ejemplos mucho más conocidos: documentos HTML y XML.

En el documento HTML, una etiqueta HTML puede contener una lista de:

  • Piezas de texto.
  • Comentarios HTML.
  • Otras etiquetas HTML (que a su vez pueden contener textos/comentarios, otras etiquetas, etc…).

Esa es una vez más una definición recursiva.

Para una mejor comprensión, cubriremos una estructura recursiva más llamada “Lista enlazada” que podría ser una mejor alternativa para las matrices en algunos casos.

Lista enlazada

Imagina que queremos almacenar una lista ordenada de objetos.

La elección natural sería una matriz:

let arr = [obj1, obj2, obj3];

…Pero hay un problema con los Arrays. Las operaciones “eliminar elemento” e “insertar elemento” son costosas. Por ejemplo, la operación arr.unshift(obj) debe renumerar todos los elementos para dejar espacio para un nuevo obj, y si la matriz es grande, lleva tiempo. Lo mismo con arr.shift ().

Las únicas modificaciones estructurales que no requieren renumeración masiva son aquellas que operan con el final del Array: arr.push/pop. Por lo tanto, una matriz puede ser bastante lenta para grandes colas si tenemos que trabajar con el principio.

Alternativamente, si realmente necesitamos una inserción/eliminación rápida, podemos elegir otra estructura de datos llamada lista enlazada.

El elemento de lista enlazada se define de forma recursiva como un objeto con:

  • value.
  • propiedad next que hace referencia al siguiente elemento de lista enlazado o null si ese es el final.

Por ejemplo:

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

Representación gráfica de la lista:

Un código alternativo para la creación:

let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };
list.next.next.next.next = null;

Aquí podemos ver aún más claramente que hay varios objetos, cada uno tiene el value y el next apuntando al vecino. La variable list es el primer objeto en la cadena, por lo que siguiendo los punterosnext de ella podemos alcanzar cualquier elemento.

La lista se puede dividir fácilmente en varias partes y luego volver a unir:

let secondList = list.next.next;
list.next.next = null;

Para unir:

list.next.next = secondList;

Y seguramente podemos insertar o eliminar elementos en cualquier lugar.

Por ejemplo, para anteponer un nuevo valor, necesitamos actualizar el encabezado de la lista:

let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };

// anteponer el nuevo valor a la lista
list = { value: "new item", next: list };

Para eliminar un valor del medio, cambie el next del anterior:

list.next = list.next.next;

Hicimos que list.next salte sobre 1 al valor 2. El valor 1 ahora está excluido de la cadena. Si no se almacena en ningún otro lugar, se eliminará automáticamente de la memoria.

A diferencia de los Arrays, no hay renumeración en masa, podemos reorganizar fácilmente los elementos.

Naturalmente, las listas no siempre son mejores que los Arrays. De lo contrario, todos usarían solo listas.

El principal inconveniente es que no podemos acceder fácilmente a un elemento por su número. En un Array eso es fácil: arr[n] es una referencia directa. Pero en la lista tenemos que comenzar desde el primer elemento e ir siguiente N veces para obtener el enésimo elemento.

… Pero no siempre necesitamos tales operaciones. Por ejemplo, cuando necesitamos una cola o incluso un deque – la estructura ordenada que debe permitir agregar/eliminar elementos muy rápidamente desde ambos extremos.

Las “listas” pueden ser mejoradas:

  • Podemos agregar la propiedad prev (previo) junto a next (siguiente) para referenciar el elemento previo para mover hacia atrás fácilmente.
  • Podemos también agregar una variable llamada tail (cola) referenciando el último elemento de la lista (y actualizarla cuando se agregan/remueven elementos del final).
  • …La estructura de datos puede variar de acuerdo a nuestras necesidades.

Resumen

Glosario:

  • Recursion es concepto de programación que significa una función “auto-llamada”. Dichas funciones se pueden utilizar para resolver ciertas tareas de manera elegante.

    Cuando una función se llama a sí misma, eso se llama paso de recursión. La base de la recursividad son los argumentos de la función que hacen que la tarea sea tan simple que la función no realiza más llamadas.

  • Una estructura de datos definida recursivamente es una estructura de datos que se puede definir utilizandose a sí misma.

    Por ejemplo, la lista enlazada se puede definir como una estructura de datos que consiste en un objeto que hace referencia a una lista (o nulo).

    list = { value, next -> list }

    Los árboles como el árbol de elementos HTML o el árbol de departamento de este capítulo también son naturalmente recursivos: se ramifican y cada rama puede tener otras ramas.

    Las funciones recursivas se pueden usar para recorrerlas como hemos visto en el ejemplo sumSalary.

Cualquier función recursiva puede reescribirse en una iterativa. Y eso a veces es necesario para optimizar las cosas. Pero para muchas tareas, una solución recursiva es lo suficientemente rápida y fácil de escribir y mantener.

Tareas

importancia: 5

Write a function sumTo(n) that calculates the sum of numbers 1 + 2 + ... + n.

For instance:

sumTo(1) = 1
sumTo(2) = 2 + 1 = 3
sumTo(3) = 3 + 2 + 1 = 6
sumTo(4) = 4 + 3 + 2 + 1 = 10
...
sumTo(100) = 100 + 99 + ... + 2 + 1 = 5050

Make 3 solution variants:

  1. Using a for loop.
  2. Using a recursion, cause sumTo(n) = n + sumTo(n-1) for n > 1.
  3. Using the arithmetic progression formula.

An example of the result:

function sumTo(n) { /*... your code ... */ }

alert( sumTo(100) ); // 5050

P.S. Which solution variant is the fastest? The slowest? Why?

P.P.S. Can we use recursion to count sumTo(100000)?

The solution using a loop:

function sumTo(n) {
  let sum = 0;
  for (let i = 1; i <= n; i++) {
    sum += i;
  }
  return sum;
}

alert( sumTo(100) );

The solution using recursion:

function sumTo(n) {
  if (n == 1) return 1;
  return n + sumTo(n - 1);
}

alert( sumTo(100) );

The solution using the formula: sumTo(n) = n*(n+1)/2:

function sumTo(n) {
  return n * (n + 1) / 2;
}

alert( sumTo(100) );

P.S. Naturally, the formula is the fastest solution. It uses only 3 operations for any number n. The math helps!

The loop variant is the second in terms of speed. In both the recursive and the loop variant we sum the same numbers. But the recursion involves nested calls and execution stack management. That also takes resources, so it’s slower.

P.P.S. Some engines support the “tail call” optimization: if a recursive call is the very last one in the function (like in sumTo above), then the outer function will not need to resume the execution, so the engine doesn’t need to remember its execution context. That removes the burden on memory, so counting sumTo(100000) becomes possible. But if the JavaScript engine does not support tail call optimization (most of them don’t), there will be an error: maximum stack size exceeded, because there’s usually a limitation on the total stack size.

importancia: 4

The factorial of a natural number is a number multiplied by "number minus one", then by "number minus two", and so on till 1. The factorial of n is denoted as n!

We can write a definition of factorial like this:

n! = n * (n - 1) * (n - 2) * ...*1

Values of factorials for different n:

1! = 1
2! = 2 * 1 = 2
3! = 3 * 2 * 1 = 6
4! = 4 * 3 * 2 * 1 = 24
5! = 5 * 4 * 3 * 2 * 1 = 120

The task is to write a function factorial(n) that calculates n! using recursive calls.

alert( factorial(5) ); // 120

P.S. Hint: n! can be written as n * (n-1)! For instance: 3! = 3*2! = 3*2*1! = 6

By definition, a factorial is n! can be written as n * (n-1)!.

In other words, the result of factorial(n) can be calculated as n multiplied by the result of factorial(n-1). And the call for n-1 can recursively descend lower, and lower, till 1.

function factorial(n) {
  return (n != 1) ? n * factorial(n - 1) : 1;
}

alert( factorial(5) ); // 120

The basis of recursion is the value 1. We can also make 0 the basis here, doesn’t matter much, but gives one more recursive step:

function factorial(n) {
  return n ? n * factorial(n - 1) : 1;
}

alert( factorial(5) ); // 120
importancia: 5

The sequence of Fibonacci numbers has the formula Fn = Fn-1 + Fn-2. In other words, the next number is a sum of the two preceding ones.

First two numbers are 1, then 2(1+1), then 3(1+2), 5(2+3) and so on: 1, 1, 2, 3, 5, 8, 13, 21....

Fibonacci numbers are related to the Golden ratio and many natural phenomena around us.

Write a function fib(n) that returns the n-th Fibonacci number.

An example of work:

function fib(n) { /* your code */ }

alert(fib(3)); // 2
alert(fib(7)); // 13
alert(fib(77)); // 5527939700884757

P.S. The function should be fast. The call to fib(77) should take no more than a fraction of a second.

The first solution we could try here is the recursive one.

Fibonacci numbers are recursive by definition:

function fib(n) {
  return n <= 1 ? n : fib(n - 1) + fib(n - 2);
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
// fib(77); // will be extremely slow!

…But for big values of n it’s very slow. For instance, fib(77) may hang up the engine for some time eating all CPU resources.

That’s because the function makes too many subcalls. The same values are re-evaluated again and again.

For instance, let’s see a piece of calculations for fib(5):

...
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
...

Here we can see that the value of fib(3) is needed for both fib(5) and fib(4). So fib(3) will be called and evaluated two times completely independently.

Here’s the full recursion tree:

We can clearly notice that fib(3) is evaluated two times and fib(2) is evaluated three times. The total amount of computations grows much faster than n, making it enormous even for n=77.

We can optimize that by remembering already-evaluated values: if a value of say fib(3) is calculated once, then we can just reuse it in future computations.

Another variant would be to give up recursion and use a totally different loop-based algorithm.

Instead of going from n down to lower values, we can make a loop that starts from 1 and 2, then gets fib(3) as their sum, then fib(4) as the sum of two previous values, then fib(5) and goes up and up, till it gets to the needed value. On each step we only need to remember two previous values.

Here are the steps of the new algorithm in details.

The start:

// a = fib(1), b = fib(2), these values are by definition 1
let a = 1, b = 1;

// get c = fib(3) as their sum
let c = a + b;

/* we now have fib(1), fib(2), fib(3)
a  b  c
1, 1, 2
*/

Now we want to get fib(4) = fib(2) + fib(3).

Let’s shift the variables: a,b will get fib(2),fib(3), and c will get their sum:

a = b; // now a = fib(2)
b = c; // now b = fib(3)
c = a + b; // c = fib(4)

/* now we have the sequence:
   a  b  c
1, 1, 2, 3
*/

The next step gives another sequence number:

a = b; // now a = fib(3)
b = c; // now b = fib(4)
c = a + b; // c = fib(5)

/* now the sequence is (one more number):
      a  b  c
1, 1, 2, 3, 5
*/

…And so on until we get the needed value. That’s much faster than recursion and involves no duplicate computations.

The full code:

function fib(n) {
  let a = 1;
  let b = 1;
  for (let i = 3; i <= n; i++) {
    let c = a + b;
    a = b;
    b = c;
  }
  return b;
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
alert( fib(77) ); // 5527939700884757

The loop starts with i=3, because the first and the second sequence values are hard-coded into variables a=1, b=1.

The approach is called dynamic programming bottom-up.

importancia: 5

Let’s say we have a single-linked list (as described in the chapter Recursión y pila):

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

Write a function printList(list) that outputs list items one-by-one.

Make two variants of the solution: using a loop and using recursion.

What’s better: with recursion or without it?

Loop-based solution

The loop-based variant of the solution:

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

function printList(list) {
  let tmp = list;

  while (tmp) {
    alert(tmp.value);
    tmp = tmp.next;
  }

}

printList(list);

Please note that we use a temporary variable tmp to walk over the list. Technically, we could use a function parameter list instead:

function printList(list) {

  while(list) {
    alert(list.value);
    list = list.next;
  }

}

…But that would be unwise. In the future we may need to extend a function, do something else with the list. If we change list, then we lose such ability.

Talking about good variable names, list here is the list itself. The first element of it. And it should remain like that. That’s clear and reliable.

From the other side, the role of tmp is exclusively a list traversal, like i in the for loop.

Recursive solution

The recursive variant of printList(list) follows a simple logic: to output a list we should output the current element list, then do the same for list.next:

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

function printList(list) {

  alert(list.value); // output the current item

  if (list.next) {
    printList(list.next); // do the same for the rest of the list
  }

}

printList(list);

Now what’s better?

Technically, the loop is more effective. These two variants do the same, but the loop does not spend resources for nested function calls.

From the other side, the recursive variant is shorter and sometimes easier to understand.

importancia: 5

Output a single-linked list from the previous task Output a single-linked list in the reverse order.

Make two solutions: using a loop and using a recursion.

Using a recursion

The recursive logic is a little bit tricky here.

We need to first output the rest of the list and then output the current one:

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

function printReverseList(list) {

  if (list.next) {
    printReverseList(list.next);
  }

  alert(list.value);
}

printReverseList(list);

Using a loop

The loop variant is also a little bit more complicated then the direct output.

There is no way to get the last value in our list. We also can’t “go back”.

So what we can do is to first go through the items in the direct order and remember them in an array, and then output what we remembered in the reverse order:

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

function printReverseList(list) {
  let arr = [];
  let tmp = list;

  while (tmp) {
    arr.push(tmp.value);
    tmp = tmp.next;
  }

  for (let i = arr.length - 1; i >= 0; i--) {
    alert( arr[i] );
  }
}

printReverseList(list);

Please note that the recursive solution actually does exactly the same: it follows the list, remembers the items in the chain of nested calls (in the execution context stack), and then outputs them.

Mapa del Tutorial

Comentarios

lea esto antes de comentar…
  • Si tiene sugerencias sobre qué mejorar, por favor enviar una propuesta de GitHub o una solicitud de extracción en lugar de comentar.
  • Si no puede entender algo en el artículo, por favor explique.
  • Para insertar algunas palabras de código, use la etiqueta <code>, para varias líneas – envolverlas en la etiqueta <pre>, para más de 10 líneas – utilice una entorno controlado (sandbox) (plnkr, jsbin, codepen…)