Funciones Recursivas

Clase 34 de 51 • Fundamentos de JavaScript 2017

Resumen

Las funciones recursivas son funciones que se llaman a si mismas, si, el resultado de la función es el llamado de la misma función.

Este comportamiento es muy importarte para solucionar cosas como series o algoritmos que tomen en cuenta valores pasados.

La recursividad se compone de 2 partes indispensables:

A) Un caso base
B) El llamado de la misma función dentro de la función

Sin un caso base, la función se va a llamar infinitamente. Esto quedará mas claro con el ejemplo de serie de fibonacci.

Daniel Hidalgo

student•

Esta clase si está super entendible.
¡¡¡por favor corrijan y mejoren los 4 videos anteriores!!!

Diego Forero

Team Platzi•

Cuéntanos que problemas observaste para poder revisar y arreglar.

Daniel Hidalgo

student•

básicamente, no explican a detalle la construcción de todo el código de los callbacks a un server externo.

Roberto Prince

student•

La reursividad es divertida, pero no es muy buena para la velocidad de tus programas actualmente en javascript, aunque el estandar ES2015, incluye algo que e llama “Optimizacion de llamada en cola” aun no la implementa nadie masque el mas nuevo explorador Safari, cuando ya se implemente esto seria igual de rapido que un ciclo for

function  repetir(veces, cllb) { 
  if(veces <= 0) return; 
   cllb(); 
   return repetir(--veces, cllb) }

repetir(2, ()=> console.log("hello"))

Usuario anónimo

user•

Buenas noches alguien me podria ayudar. Lo que pasa es que no se si me quedo claro el “return” que contiene la operacion fibonacci, que es “(num - 1) + fibonacci(num - 2)”, Esos -1 y - 2 son los que restan la posicion del “num”, me explico si estamos en la posicion “fibonacci(6)” lo que hace el return de la operacion es que resta la posicion “6” en uno y queda “5” y el cinco tiene valor “3” y la otra funcion es la misma posicion “6” menos dos 2 posciones y queda en “4” y su valor es “2” y se suman los valores “3” y “2” para que la posicion “6” tenga como valor “5”, por lo tanto quiero saber si entendi bien o esta incorrecto.

MUCHAS GRACIAS.

Diego Forero

Team Platzi•

Entendiste la idea, recuerda que por ser una función recursiva se llama a si misma nuevamente para ir calculando los valores hasta llegar a los dos casos base.

Usuario anónimo

user•

Muchas Gracias.

David Carrero Sepulveda

student•

Los valores base de la serie fibonaci son fibonaci(0) = 0 y fibonaci (1) = 1. Este seria el código corregido.

function fibonacci(num){
	if (num == 0) return 0
	if (num == 1) return 1
	return fibonacci(num - 1) + fibonacci(num - 2)
}

fibonacci(1)//1
fibonacci(2)//1
fibonacci(3)//2
fibonacci(4)//3
fibonacci(5)//5
fibonacci(6)//8
fibonacci(7)//13

Andrés Madrigal

student•

Que interesante, muy buena observación

Sebastian Díaz

student•

Me costó un momento comprender la idea, si lo analizas a profundidad al ejecutarse se genera una especie de bucle o árbol hasta que el numero se “descomponga” en unos y dos (ya que solo si el numero es 1 o 2, se corta la ejecución y deja de “re-ejecutarse” la función fibonacci), y luego sumarse todos para dar el resultado final. Los invito a que intenten ejecutar el algoritmo ustedes mismos a mano, con papel y lápiz para que entiendan de lo que hablo.

Alexis Antonio Moraga Gallardo

student•

me podrías explicar como ejecutarlo a lápiz y papel, le doy vueltas, pero no logro comprender como funciona realmente.
Saludos

José Briceño

student•

alexis, se refiere a algo como esto.
El numero de arriba es el numero base, y se descompone hasta llegar a los casos base (el uno y el cero), y esos se suman para dar el resultado. (El resultado es 5 y no 3 porque tome en cuenta al cero como el numero cero de la lista y no como el primer numero de la lista).

Julio J Yépez

student•

Mi versión de fibonacci:

const fibonacci = n => n == 1 ? 0 : n == 2 ? 1 : fibonacci( n-1 ) + fibonacci( n-2 )

console.log( fibonacci(9) )
21

José Granado

student•

Este está más general que el mio, Gracias! FelicidadeS!

Daniel Romero

student•

fibonacci(100) === petada de navegador.

Jose Enrique Marquez

student•

con el algoritmo que acabo de agregar corriges ese error un
fibonacci(100) se repetiría solo 195 veces haciendo el algoritmo mas eficiente sin patear al navegador.

Andrés Madrigal

student•

con el algoritmo de la clase llego a fibonacci(38) en mi computadora antes de que se congele el navegador jaja

Iván Toro

student•

Una función recursiva es una función que se llama así misma, es necesario que la función tenga al menos dos elementos:

El caso base.
El caso recursivo.

Es posible tener varios casos base y varios casos recursivos, pero es necesario tener al menos uno de cada uno.
El lógica se basa en problemas que se resuelven conociendo el estado de una solución mas básica, como lo es la sucesión de Fibonacci.
El caso base sirve para parar la recursion y retornar un valor y el caso recursivo sirve para obtener el valor de un estado mas básico del problema, por eso es importante que la entrada del caso recursivo siempre sufra un cambio con el fin de llegar al caso base, en este ejemplo se le resta 1 y 2.

Noe Mikhael Huaccharaque Ruiz

student•

Entendi Asi:

fibonacci(3) = ?
fibonacci(3 -1) + fibonacci(3 -2)
fibonacci(2) + fibonacci(1)
         1         +         0       =    1
fibonacci(3) = 1

Wladimir Rocha

student•

Cuestión de gustos, yo usualmente uso esa manera pero con PNPM

Francisco Benitez

student•

Lo maravilloso es que a simple vista no se ve que haya un acumulador, y que lo que yo le paso no es el numero en sí sino el numero de orden en la secuencia, y sin embargo al finalizar obtengo un numero mayor al que pasé (sin ver el acumulador) y obtengo el numero de la lista (pasando la posicion)

Rodolfo Sebastian Herrera Hernández

student•

var counter = 0;
const ACTION = document.getElementById('action');

function recursividad(){

    counter++;

    if(counter < 10){
        ACTION.textContent = 'Cargando el contador hasta que llegue a 10...';
        console.log('Cargando el contador hasta que este sea 10...');
        recursividad();
    }else if( (counter < 50) ){
        ACTION.textContent = `El contador va en el numero ${counter}.`;
        console.log(`El contador ya va en el numero ${counter}.`)
        recursividad();
    }else{
        ACTION.textContent = `El contador ya supero el numero 50.`;
        console.log(`El contador ya supero el numero 50.`);
    }
}

// Llamamos a la funcion recursiva
recursividad();```

Jose Enrique Marquez

student•

Hola gente me puse a agregarle un poco de clousure a esta funcion recursiva y logre rebajar la cantidad de llamadas a la funcion en si misma aca les dejo el codigo

function fibonacci(num) {
  let data = [0, 0, 1, 1]

  let interna = function (num) {
    if (data.length <= num) {
      let suma = interna(num - 1) + interna(num - 2)
      data[num] = suma
      return data[num]
    } else {
      return data[num]
    }
  }

  return interna(num)
}

console.log(fibonacci(8))

les recomiendo revisar el código ya que así se puede responder de forma mas rápida y efectiva.

Michel Daniel Betancourt Gil

student•

Aquí un fibonacci sin recursion:

const INV_5 = 1 / 2.23606797749979;
const SUM_RAIZ = (1 + 2.23606797749979) / 2;
const MINUS_RAIZ = (1 - 2.23606797749979) / 2;

const fibo = n => INV_5 * (SUM_RAIZ**n - MINUS_RAIZ**n);

Julio J Yépez

student•

Interesante … cómo llegaste a este algoritmo?

Jose Enrique Marquez

student•

Genial esa manera de ejecutar el calculo solo le encontré un error y es que no puedes pasar el numero directo si no que debes restarle uno para que de el resultado correcto
ejemplo:

fibo(4) // El resultado que da es 3 y esto seria el el fibonacci de 5 realmente

Julian Andres Builes Cajiao

student•

Recursividad es una función que se llama así mismas, OJO, hay que tener en cuenta los casos bases, porque si no se hace se nos va a llenar nuestra stack de ejecución.

Nicole Chapaval

Team Platzi•

Hey, hace poco publicamos este tutorial en el blog, que creo que puede aportar aquí también.
Recursividad con el ejemplo de las Torres de Hánoi

Andrés Madrigal

student•

let fibonacci = n => n == 0 ? 0 : n == 1 ? 1 : fibonacci( n-1 ) + fibonacci( n-2 )
Esta es la función con mejor performance que encontre

Emanuel Pontoni

student•

Una fórmula no recursiva para la sucesión de Fibonacci:

const sr5 = Math.sqrt(5);

function Fibonacci(n){
  return 1/sr5 * ((1+sr5)/2)**n-1/sr5 * ((1-sr5)/2)**n
}
//Imprimimos los 10 primeros términos...
for (let i=0; i<10; i++)
  console.log(Fibonacci(i))

Michael Brandon Serrato Guerrero

student•

Aquí la versión en Arrow Function:

const fib = (x) => x > 2 ? fib(x - 1) + fib(x - 2) : (x == 2 ? 1 : 0);

Alexis Antonio Moraga Gallardo

student•

Alguien me podría explicar exactamente que pasa en la linea

  return fibonachi(num -1) + fibonachi(num -2)

si le envió como parámetro el numero 6

se esta sumando los números y retorna un llamado a la función con el numero 9,

o se hacen dos llamados diferentes a la misma función, uno con el 5 y otro con el 4?

Estoy tratando de comprender, si el numero que enviamos como parámetro corresponde al indice y los valores sumados son los correspondientes al indice esta bien, es decir 6 - 1 es 5, y el indice 5 guarda el valor 3. luego 5 - 2 es 4 y el indice 4 guarda el valor 2. con lo cual 3 + 2 es 5 y esta bien.

Pero en que momento la función calcula la serie. Como la función sabe que tiene que restarle un numero al incite y sumar el valor que debería tener ese indice

alguien me podría explicar como desarrollar el algoritmo a lápiz y papel para comprender mejor esto.

De ante mano muchas gracias

Andrés Madrigal

student•

Lo sumas y restas así como lo explicaste, yo veo que lo entendiste bastante bien

Felipe de Jesus Ramirez Rodriguez

student•

const fibonacci = (num)=> (num == 1) ? 0 : (num == 2) ? 1 : fibonacci(num - 1) + fibonacci(num - 2)

Victor Lozada

student•

dejo otro ejemplo de recursividad, en este caso para obtener el factorial de algun numero:

const factorial = n =>{
    if(n == 1 ) return 1
    return factorial(n - 1) * n
}

Funciones Recursivas

Estamos renovando el Curso de Fundamentos de Javascript

¿Dónde aprender JS actualizado?

Bases del lenguaje

Bienvenido al curso

Calcula el área de un triángulo. Creando funciones

¿Quiénes pueden pasar a ver una película? Ejercicio con condicionales, expresiones y booleanos

Inventar un idioma manipulando strings

¿Cuántos kms corre una persona en promedio? Entendiendo el ciclo for

¿Quién gana en una pelea: Gokú o Superman? Resolviendo este problema con ciclos while

¿Cuánto tiempo pasó desde tu fecha de nacimiento?

Objetos en JavaScript

Calcular la distancia entre dos puntos - Objetos en JavaScript

Agrega métodos para mover los puntos - Objetos Avanzado en JavaScript

Definiendo la clase Punto - Prototipos en JavaScript

Definiendo la clase Punto - Object.create en JavaScript

Definiendo la clase Punto - Class en JavaScript

Conocimientos intermedios

Entiende el scope de las variables

Operaciones con arrays

Entiende los closures de JavaScript

Estructura del lenguaje

¿Quién es this?

This, _this y los arrow functions

La función bind

call y apply

ECMAScript 5, 2015, 2016, Babel y otros cuentos

ECMAScript: El estándar en el que se basa JavaScript

Babel al rescate: logrando la compatibilidad buscada

Distintas formas de escribir módulos en JavaScript

Procesos asíncronos

No generes un cuello de botella en el EventLoop

Los callbacks de JavaScript

Callback a un servidor externo

Promesas

Async-await

Implementación de set timeout en JavaScript

Implementación de set interval en JavaScript

Cancelando el Timeout y el Timeinterval

Qué son y cómo se implementan el callbacks en JavaScript

Eliminando el callback hell usando promesas en JavaScript

Estructuras de datos y funciones avanzadas

Funciones Recursivas

Memoizacion

Iteradores en JavaScript

Generadores en JavaScript

Estructuras de Datos Inmutables en JavaScript

Creando un paquete para NPM

Requisitos Técnicos

Creando nuestro paquete

Escribiendo el código de nuestro paquete

Testeando el paquete

Publicando el paquete en NPM

Juego de HTML

¿Qué vamos a construir?

Inicializando el juego

A una ronda le sigue otra ronda

Añadir una librería

Cierre del Curso

Desafíos

Crear un modulo para convertir medidas de peso

Crear un juego en HTML, tic tac toe

Crear un tutorial