Recursividad

recursividad

> Tutorial de LeekScript

Requisitos previos:

----

La recursividad, en términos generales, es la capacidad de un objeto para referirse a sí mismo. En el mundo real, esto es más evidente en los fractales, así como cuando se colocan dos espejos frente a frente. También encontramos esta noción en frases del estilo: "Sueño que sueño que sueño." o "Creo que escribo que sueño que pienso que escribo...", etc. En programación, esto se manifiesta principalmente con funciones que se llaman a sí mismas:

bucle de función () { círculo(); }

La función anterior es la función recursiva más simple que existe. Cuando se le llama, no hace más que llamarse a sí mismo. Esto es lo mismo que usar un bucle infinito (p. ej., while(true);). Usaremos esta función como un esqueleto básico para todas nuestras futuras funciones recursivas.

Recursión

La recursividad es análoga a la deconstrucción. Se encuentra principalmente en algoritmos de tipo ''Divide and Conquer''. Para resolver nuestro problema, comenzamos por subdividirlo en subproblemas que sean más fáciles de resolver, repetimos el proceso hasta encontrar un problema que sepamos resolver directamente, y a partir de ahí, resolvemos los problemas superiores combinando nuestros problemas anteriores. soluciones

Establecer Suma de 0 a n

Queremos definir una función que tome un entero n como parámetro y devuelva la suma de 0 a n (por ejemplo, 0 + 1 + ... + n). Tomando nuestro esqueleto básico, podemos comenzar con la siguiente función:

función sumaN(n) { sumaN(?); ¿retorno?; }

Por el momento contamos con la siguiente información:

Cuando se trabaja de forma recursiva, siempre es una buena idea comenzar con la condición de parada. En el caso de la recursividad, queremos dejar de crear subproblemas cuando hayamos encontrado algo que podamos resolver. En este caso, la suma de 0 a 0 es algo que sabemos resolver. 0 es por lo tanto nuestro caso base, podemos devolver directamente la suma correspondiente.

función sumaN(n) { si (n === 0) { devuelve 0; } más { sumaN(?); ¿retorno?; } }

Ahora tenemos que averiguar cómo llegar al caso base. Podríamos restar n de sí mismo, pero en ese caso no seríamos capaces de sumar los enteros entre 0 y n, solo tendríamos disponibles 0 y n. Por lo tanto, tendremos que crear un subproblema que pueda resolver una suma con una n más cercana a nuestro caso base.

función sumaN(n) { si (n === 0) { devuelve 0; } más { sumaN(n - 1); ¿retorno?; } }

Ahora solo falta hacer la suma que se nos pidió al principio. Aquí, la suma de 0 a n es también la suma de la suma de 0 a n - 1 y n.

función sumaN(n) { si (n === 0) { devuelve 0; } más { devuelve n + sumN(n - 1); } }

Con un ternario:

función sumaN(n) { devolver n === 0? 0 : n + sumaN(n - 1); }

Siéntase libre de probar el código en su editor de Leekwars. Quizás descubras el principal problema con la recursividad. También puede visualizar la ejecución (de manera básica) en [este sitio] (http://www.pythontutor.com/visualize.html#mode=display).

Correcursión

/!\ Sección para rehacer, lo que se muestra es principalmente recursión de cola. No apto para múltiples sucursales. /!\ La corecursión es análoga a la construcción. A diferencia de la recursividad, donde buscamos llegar a un caso base a partir de nuestro problema principal, en la co-recursión comenzamos directamente con nuestro caso base y avanzamos hacia la solución del problema principal.

Recursión mutua

Ya hemos cubierto la recursividad mutua con espejos y oraciones. En programación, con funciones, esto se traduce en dos o más funciones llamándose entre sí. Presentamos a continuación el caso más simple de recursividad mutua:

function BucleMutuo() { ayudante mutuo(); }

función mut