Share
Algunos problemas se resuelven más naturalmente usando la recursión. Por ejemplo, una secuencia como la secuencia de Fibonacci tiene una definición recursiva. Cada número en la secuencia es la suma de los dos números anteriores en la secuencia. Los problemas que requieren que usted construya o atraviese una estructura de datos similar a un árbol también se pueden resolver con recursión. Entrenarte para pensar recursivamente te dará una poderosa habilidad para atacar tales problemas.
En este tutorial, iré paso a paso a través de varias funciones recursivas para ver cómo funcionan y mostrarte las técnicas que puedes usar para definir sistemáticamente las funciones recursivas..
Una función definida recursivamente es una función que se define en términos de una versión más simple de sí misma. Este es un ejemplo simplificado:
función doA (n) … doA (n-1);
Para entender cómo funciona la recursión conceptualmente, veremos un ejemplo que no tiene nada que ver con el código. Imagina que eres responsable de responder llamadas telefónicas en el trabajo. Debido a que esta es una empresa ocupada, su teléfono tiene varias líneas telefónicas para que pueda hacer malabarismos con varias llamadas al mismo tiempo. Cada línea telefónica es un botón en el receptor, y cuando hay una llamada entrante, el botón parpadeará. Hoy, cuando llega al trabajo y enciende el teléfono, hay cuatro líneas parpadeando a la vez. Así que te pones a trabajar respondiendo todas las llamadas..
Usted toma la línea uno y les dice 'por favor espere'. Luego tomas la línea dos y las pones en espera. A continuación, toma la línea tres y la pone en espera. Finalmente, la cuarta línea la contesta y habla con la persona que llama. Cuando termina con la cuarta persona que llama, cuelga y contesta la tercera llamada. Cuando termina con la tercera llamada, cuelga y contesta la segunda llamada. Cuando termina con la segunda llamada, cuelga y contesta la primera llamada. Cuando termine esa llamada, finalmente puede dejar el teléfono.
Cada una de las llamadas telefónicas en este ejemplo es como una llamada recursiva en una función. Cuando recibe una llamada, se coloca en la pila de llamadas (en lenguaje de código). Si no puede completar una llamada de inmediato, retiene la llamada. Si tiene una llamada de función que no se puede evaluar inmediatamente, permanece en la pila de llamadas. Cuando puede contestar una llamada, se contesta. Cuando su código puede evaluar una llamada de función, se extrae de la pila. Tenga en cuenta esta analogía mientras observa los siguientes ejemplos de código.
Todas las funciones recursivas necesitan un caso base para que terminen. Sin embargo, solo agregar un caso base a nuestra función no impide que se ejecute infinitamente. La función debe tener un paso para acercarnos al caso base. El último es el paso recursivo. En el paso recursivo, el problema se reduce a una versión más pequeña del problema.
Supongamos que tiene una función que sumará los números del 1 al n. Por ejemplo, si n = 4, sumará 1 + 2 + 3 + 4.
Primero, determinamos el caso base. Encontrar el caso base también se puede considerar como encontrar el caso donde el problema se puede resolver sin recursión. En este caso, es cuando n es igual a cero. El cero no tiene partes, por lo que nuestra recursión puede detenerse cuando alcanzamos 0.
En cada paso, restará uno del número actual. ¿Cuál es el caso recursivo? El caso recursivo es la suma de la función llamada con el número reducido..
función sum (num) if (num === 0) return 0; else return num + sum (- num) sum (4); // 10
Esto es lo que está sucediendo en cada paso:
Esta es otra forma de ver cómo la función está procesando cada llamada:
suma (4) 4 + suma (3) 4 + (3 + suma (2)) 4 + (3 + (2 + suma (1))) 4 + (3 + (2 + (1 + suma (0)) )) 4 + (3 + (2 + (1 + 0))) 4 + (3 + (2 + 1)) 4 + (3 + 3) 4 + 6 10
El argumento debería cambiar en el caso recursivo y acercarlo al caso base. Este argumento debe ser probado en el caso base. En el ejemplo anterior, como estamos restando uno en el caso recursivo, probamos si el argumento es igual a cero en nuestro caso base.
Accentsconagua
multiplicar (2,4) volverá 8. Escribe lo que sucede en cada paso para multiplicar (2,4).La repetición en una lista es similar a la repetición en un número, excepto que en lugar de reducir el número en cada paso, estamos reduciendo la lista en cada paso hasta llegar a una lista vacía..
Considere la función de suma que toma una lista como entrada y devuelve la suma de todos los elementos de la lista. Esta es una implementación para la suma de funciones:
función sum (l) if (empty (l)) return 0; else return car (l) + sum (cdr (l));
los vacío La función devuelve true si la lista no tiene elementos. los coche La función devuelve el primer elemento de la lista. Por ejemplo, coche ([1,2,3,4]) devuelve 1. El cdr La función devuelve la lista sin el primer elemento. Por ejemplo, cdr ([1,2,3,4]) devoluciones [2,3,4]. ¿Qué pasa cuando ejecutamos? suma ([1,2,3,4])?
suma ([1,2,3,4]) 1 + suma ([2,3,4]) 1 + (2 + suma ([3,4])) 1 + (2 + (3 + suma ([4 ]))) 1 + (2 + (3 + (4 + suma ([])))) 1 + (2 + (3 + (4 + 0))) 1 + (2 + (3 + 4)) 1 + (2 + 7) 1 + 9 10
Cuando vuelva a aparecer en una lista, verifique si está vacía. De lo contrario, realice el paso recursivo en una versión reducida de la lista.
longitud (['a', 'b', 'c', 'd']) debe volver 4. Escribe lo que pasa en cada paso.En el último ejemplo, estábamos devolviendo un número. Pero supongamos que quisiéramos devolver una lista. Eso significaría que, en lugar de agregar un número a nuestro paso recursivo, tendríamos que agregar una lista. Considera la función retirar, que toma un elemento y una lista como entrada y devuelve la lista con el elemento eliminado. Sólo se eliminará el primer elemento encontrado.
función remove (item, l) if (empty (l)) return []; else if (eq (car (l), item)) return cdr (l); else return cons (auto (l), remove (item, cdr (l))); eliminar ('c', ['a', 'b', 'c', 'd']) // ['a', 'b', 'd']Aquí el eq la función devuelve verdadero si ambas entradas son iguales. los contras La función toma un elemento y una lista como entradas y devuelve una nueva lista con el elemento agregado al principio..
Comprobaremos si el primer elemento de la lista es igual al elemento que queremos eliminar. Si es así, elimine el primer elemento de la lista y devuelva la nueva lista. Si el primer elemento no es igual al elemento que queremos eliminar, tomamos el primer elemento de la lista y lo agregamos al paso recursivo. El paso recursivo contendrá la lista con el primer elemento eliminado.
Seguiremos eliminando elementos hasta que lleguemos a nuestro caso base, que es una lista vacía. Una lista vacía significa que hemos recorrido todos los elementos de nuestra lista. Que hace eliminar ('c', ['a', 'b', 'c', 'd']) hacer?
eliminar ('c', ['a', 'b', 'c', 'd']) contras ('a', eliminar ('c', ['b', 'c', 'd']) ) contras ('a', contras ('b', eliminar ('c', ['c', 'd'])) contras ('a', cons ('b', ['d']) contras ('a', ['b', 'd']) ['a', 'b', 'd']En una situación en la que necesitamos crear una lista, tomamos el primer elemento y lo agregamos a la parte recursiva de nuestra lista.
eliminar ('c', ['a', 'b', 'c', 'd', 'c'] devuelve ['a', 'b', 'd']. Escribe lo que sucede paso a paso.Hay tres partes en una función recursiva. El primero es el caso base, que es la condición de terminación. El segundo es el paso para acercarnos a nuestro caso base. El tercero es el paso recursivo, donde la función se llama a sí misma con la entrada reducida.
La recursión es como la iteración. Cualquier función que pueda definir recursivamente también puede definirse utilizando bucles. Otras cosas a considerar cuando se usa la recursividad son recurrentes en listas anidadas y optimizan sus llamadas recursivas.
Un gran recurso para continuar aprendiendo sobre la recursión es el libro The Little Schemer. Te enseña a pensar recursivamente usando un formato de preguntas y respuestas.
