Comprensión de recursión con JavaScript

Introdución

Algúns problemas resólvense máis naturalmente usando a recursión. Por exemplo, unha secuencia como Fibonacci ten unha definición recursiva. Cada número nel é a suma dos dous números anteriores da secuencia. Os problemas que requiren que constrúen ou corten unha estrutura de datos semellante á árbore tamén se pode resolver con recursión. O tren para pensar recursivamente darache unha poderosa capacidade de abordar estes problemas.

Neste tutorial vou facer unha revisión paso a paso de varias funcións recursivas para ver como funcionan e mostran técnicas que pode usar para definir as funcións recursivas de forma sistemática.

Contido:

• Cal é a recursión?
• Recursión con números
• Recursión con listas
• Listas de construción
• revisión

Cal é a recursión?

Unha función definida recursivamente é unha función que está definida en termos dunha versión máis sinxela de si mesma. Este é un exemplo simplificado:

function doA(n) { ... doA(n-1);}

para entender como o recorrente funciona conceptualmente, veremos un exemplo que non ten nada que ver co código. Imaxina que é responsable de responder chamadas telefónicas no seu traballo. Xa que esta é unha empresa ocupada, o teléfono ten varias liñas para que poida asistir a varias chamadas ao mesmo tempo. Cada liña telefónica é un botón do receptor e, cando hai unha chamada entrante, o botón fará Flash. Hoxe, cando chegue ao traballo e acenda o teléfono, hai catro liñas parpadeando ao mesmo tempo. Polo tanto, comeza a traballar respondendo todas as chamadas.

Responder a liña unha e dicir “Agarde”. Entón conteste a liña dúas e poñelas en espera. A continuación responde ás tres liñas e póñao en espera. Finalmente, contestas a cuarta liña e falas coa persoa que estás chamando. Cando termine coa cuarta persoa que colgar e responder a terceira chamada. Cando remate coa terceira chamada, colgar e responder o segundo. Cando termine coa segunda chamada, colgar e responder o primeiro. Cando acabas con esa chamada, podes finalmente colgar o teléfono.

Cada unha das chamadas telefónicas deste exemplo é como unha chamada recursiva nunha función. Cando reciba unha chamada, colócase na pila de chamadas (en termos de código). Se non pode rematar unha chamada inmediatamente, está en espera. Se tes unha chamada a unha función que non se pode avaliar de inmediato, mantense na pila de chamadas. Cando pode responder unha chamada, isto é servido. Cando o seu código é capaz de avaliar a chamada a unha función, elimínase da pila. Ten presente esta analoxía mentres comprobe os seguintes exemplos de código.

Recursións con números

Todas as funcións recursivas precisan dun caso base para poder rematar. Non obstante, o simple feito de engadir un caso base á nosa función non impedirá que se executase infinitamente. A función debe dar un paso para achegarse ao caso base. Finalmente, hai o paso recursivo. No paso recursivo, o problema redúcese a unha versión máis pequena do problema.

Supoña que ten unha función que engadirá os números de 1 a n. Por exemplo, se n = 4, a función engadirá 1 + 2 + 3 + 4.

Primeiro determinamos o caso base. Atopar o caso base é como atopar o caso en que o problema pode ser resolto sen recursión. Neste exemplo é cando n é igual a cero. Zero non ten partes, polo que a nosa recursión pode parar ao chegar a 0.

En cada paso vai restar o valor un ao número actual. Cal é o caso recursivo? O caso recursivo é a función SUMA invocada co número reducido.

function sum(num){ if (num === 0) { return 0; } else { return num + sum(--num) }}sum(4); //10

Isto é o que ocorre en cada paso:

• Ir á suma (4).
• 4 é igual a 0? Non. Coloque a suma (4) en espera e vai á suma (3).
• 3 é igual a 0? Non. Coloque a suma (3) en espera e ir á suma (2).
• 2 é igual a 0? Non. Coloque a suma (2) en espera e vai á suma (1).
• 1 é igual a 0? Non. Sumen (1) en espera e vai a suma (0).
• 0 é igual a 0? Si. Avaliar a suma (0).
• reta suma (1).
• reta suma (2).
• reta suma (3).
• reta sum (4).

Esta é outra forma de ver como a función está a procesar cada chamada:

sum(4)4 + sum(3)4 + ( 3 + sum(2) )4 + ( 3 + ( 2 + sum(1) ))4 + ( 3 + ( 2 + ( 1 + sum(0) )))4 + ( 3 + ( 2 + ( 1 + 0 ) ))4 + ( 3 + ( 2 + 1 ) )4 + ( 3 + 3 ) 4 + 6 10

O argumento debe cambiar no caso recursivo e achegarse ao caso base. Este argumento debe ser verificado no caso base. No exemplo anterior, xa que estamos a restaurar o valor un no caso recursivo, debemos verificar se o argumento é igual a cero no noso caso base.

tarefa

1. implementar A función de soma usando un ciclo en vez de recursión.
2. crea unha función que multiplica dous números recursivamente. Por exemplo, multiply(2,4) producirá 8. Escriba o que ocorre durante cada paso para multiply(2,4).

Recursión con listas

A recursión dunha lista é similar á recursión dun número, pero no canto de reducir o número en cada paso, reduciremos a lista en cada paso ata que teñamos unha lista baleira.

Considere a función de suma que recibe unha lista como entrada e devolve a suma de todos os elementos desta lista. Esta é unha implementación para a función de suma:

function sum(l){ if (empty(l)) { return 0; } else { return car(l) + sum(cdr(l)); }}

a función empty devolve o valor verdadeiro (verdadeiro) se A lista non ten elementos. A función car devolve o primeiro elemento da lista. Por exemplo, car() Devolve o valor 1. A función

devolve a lista sen o primeiro elemento. Por exemplo,cdr()devolve. O que ocorre cando executamossum()?

sum()1 + sum()1 + ( 2 + sum() )1 + ( 2 + ( 3 + sum() ))1 + ( 2 + ( 3 + ( 4 + sum() )))1 + ( 2 + ( 3 + ( 4 + 0 ) ))1 + ( 2 + ( 3 + 4 ) )1 + ( 2 + 7 ) 1 + 910

Cando executar a recursión nunha lista é revisada se está baleiro. Se non, o paso recursivo realízase nunha versión reducida da lista.

tarefa

1. retribúe esta función de suma para que use un ciclo para engadir cada elemento de A lista en vez de usar a recursión.
2. define unha función chamada lonxitude (lonxitude) que recibe unha lista como entrada e devolve o número de elementos nesa lista. Non debe usar a función de lonxitude integrada en JavaScript. Por exemplo, length() debe devolver o valor 4. Escriba o que ocorre en cada paso.

Listas de construción

no Último exemplo que volvemos un número. Pero supoña que queremos devolver unha lista. Isto significa que no canto de engadir un número ao noso paso recursivo, necesitamos engadir unha lista. Considere a función remove (Eliminar), que recibe un elemento e unha lista como entrada e devolve a lista sen o elemento que queremos eliminar. Só o primeiro elemento que atopamos será eliminado.

function remove(item, l){ if (empty(l)) { return ; } else if (eq(car(l), item)) { return cdr(l); } else { return cons(car(l), remove(item, cdr(l))); }}remove('c', ) //

Aquí, a función eq devolve un valor real (TRUE) Se ambas entradas son iguais. O cons recibe un elemento e unha lista como insumos e devolve unha nova lista co elemento engadido ao comezo dela.

Comprobamos se o primeiro elemento da lista é igual ao elemento que queremos eliminar. Se é así, elimina o primeiro elemento da lista e devolve a nova lista. Se o primeiro elemento non é igual ao elemento que queremos eliminar, tomamos o primeiro elemento da lista e engadimos ao paso recursivo. O paso recursivo conterá a lista co primeiro elemento eliminado.

Seguiremos a eliminar elementos ata chegar ao noso caso base, que é unha lista baleira. Unha lista baleira significa que viaxamos todos os seus elementos. Que fai a función remove('c', )?

remove('c', )cons( ‘a’, remove(‘c’, ) )cons( ‘a’ , cons( ‘b’, remove(‘c’, ) ))cons( ‘a’, cons( ‘b’, )cons( ‘a’, )

nunha situación na que necesitamos construír unha lista, tomamos o primeiro elemento e engadímoslo á parte recursiva da nosa lista.

tarefa

1. retenen a función Eliminar para que use ciclos en vez de recursión para eliminar un elemento de Unha lista.
2. Modificar a función Eliminar para eliminar todas as aparicións dun elemento nunha lista. Por exemplo, remove(‘c’, devolve. Escribe o que pasa paso a paso.

Revisión

Unha función recursiva ten tres partes. O primeiro é o caso base, que é a condición de terminal. O segundo é o paso que chega ao noso caso base. O terceiro é o paso recursivo, no que a función está invocada a si mesma cunha entrada reducida.

A recursión é como iteración. Calquera función que poida definir de forma recursiva tamén pode definirse usando ciclos. Outros aspectos a considerar ao usar esta técnica son a recursión en listas aniñadas e a optimización das súas chamadas recursivas.

Un gran recurso para seguir aprendendo sobre a recursión é o libro The Little Schemer. Isto ensínache a pensar en usar de forma recursiva un formato de preguntas e respostas.