La recursividad es un concepto fundamental en informática y matemáticas que permite que las funciones se llamen a sí mismas, permitiendo la solución de problemas complejos a través de pasos iterativos. Una representación visual comúnmente utilizada para comprender y analizar la ejecución de funciones recursivas es un árbol de recursividad. En este artículo, exploraremos la teoría detrás de los árboles de recursividad, su estructura y su importancia para comprender los algoritmos recursivos.

¿Qué es un árbol de recursividad?

Un árbol de recursividad es una representación gráfica que ilustra el flujo de ejecución de una función recursiva. Proporciona un desglose visual de las llamadas recursivas, mostrando la progresión del algoritmo a medida que se ramifica y finalmente alcanza un caso base. La estructura de árbol ayuda a analizar la complejidad del tiempo y comprender el proceso recursivo involucrado.

Estructura de árbol

Cada nodo en un árbol de recursividad representa una llamada recursiva particular. La llamada inicial se muestra en la parte superior, y las llamadas posteriores se ramifican debajo de ella. El árbol crece hacia abajo, formando una estructura jerárquica. El factor de ramificación de cada nodo depende de la cantidad de llamadas recursivas realizadas dentro de la función. Además, la profundidad del árbol corresponde al número de llamadas recursivas antes de llegar al caso base.

Caso base

El caso base sirve como condición de terminación para una función recursiva. Define el punto en el que se detiene la recursividad y la función comienza a devolver valores. En un árbol de recursividad, los nodos que representan el caso base suelen representarse como nodos hoja, ya que no dan lugar a más llamadas recursivas.

Llamadas recursivas

Los nodos secundarios en un árbol de recursividad representan las llamadas recursivas realizadas dentro de la función. Cada nodo secundario corresponde a una llamada recursiva separada, lo que resulta en la creación de nuevos subproblemas. Los valores o parámetros pasados ​​a estas llamadas recursivas pueden diferir, lo que genera variaciones en las características de los subproblemas.

Flujo de ejecución:

Recorrer un árbol de recursividad proporciona información sobre el flujo de ejecución de una función recursiva. A partir de la llamada inicial en el nodo raíz, seguimos las ramas para llegar a llamadas posteriores hasta encontrar el caso base. A medida que se alcanzan los casos base, las llamadas recursivas comienzan a regresar y sus respectivos nodos en el árbol se marcan con los valores devueltos. El recorrido continúa hasta que se haya recorrido todo el árbol.

Análisis de complejidad temporal

Los árboles de recursividad ayudan a analizar la complejidad temporal de los algoritmos recursivos. Al examinar la estructura del árbol, podemos determinar la cantidad de llamadas recursivas realizadas y el trabajo realizado en cada nivel. Este análisis ayuda a comprender la eficiencia general del algoritmo e identificar posibles ineficiencias u oportunidades de optimización.

Introducción

• Piensa en un programa que determina el factorial de un número. Esta función toma un número N como entrada y devuelve el factorial de N como resultado. El pseudocódigo de esta función se parecerá a,

 // find factorial of a number factorial(n) { // Base case if n is less than 2: // Factorial of 0, 1 is 1 return n // Recursive step return n * factorial(n-1); // Factorial of 5 => 5 * Factorial(4)... } /* How function calls are made, Factorial(5) [ 120 ] | 5 * Factorial(4) ==> 120 | 4. * Factorial(3) ==> 24 | 3 * Factorial(2) ==> 6 | 2 * Factorial(1) ==> 2 | 1 */ 

• La recursividad se ejemplifica con la función que se mencionó anteriormente. Estamos invocando una función para determinar el factorial de un número. Luego, dado un valor menor del mismo número, esta función se llama a sí misma. Esto continúa hasta llegar al caso básico, en el que no hay más llamadas a funciones.
• La recursividad es una técnica para manejar problemas complicados cuando el resultado depende de los resultados de instancias más pequeñas del mismo problema.
• Si pensamos en funciones, se dice que una función es recursiva si sigue llamándose a sí misma hasta llegar al caso base.
• Cualquier función recursiva tiene dos componentes principales: el caso base y el paso recursivo. Dejamos de pasar a la fase recursiva una vez que llegamos al caso básico. Para evitar una recursión interminable, los casos base deben definirse adecuadamente y son cruciales. La definición de recursividad infinita es una recursividad que nunca llega al caso base. Si un programa nunca llega al caso base, se seguirá produciendo un desbordamiento de pila.

Tipos de recursividad

En términos generales, existen dos formas diferentes de recursividad:

• Recursión lineal
• Recursión de árbol
• Recursión lineal

Recursión lineal

• Una función que se llama a sí misma sólo una vez cada vez que se ejecuta se dice que es linealmente recursiva. Un buen ejemplo de recursividad lineal es la función factorial. El nombre 'recursión lineal' se refiere al hecho de que una función linealmente recursiva tarda una cantidad de tiempo lineal en ejecutarse.
• Eche un vistazo al pseudocódigo a continuación:

 function doSomething(n) { // base case to stop recursion if nis 0: return // here is some instructions // recursive step doSomething(n-1); } 

• Si miramos la función hacerAlgo(n), acepta un parámetro llamado n y hace algunos cálculos antes de llamar al mismo procedimiento una vez más pero con valores más bajos.
• Cuando se llama al método doSomething() con el valor del argumento n, digamos que T(n) representa la cantidad total de tiempo necesaria para completar el cálculo. Para esto, también podemos formular una relación de recurrencia, T(n) = T(n-1) + K. K sirve aquí como constante. Se incluye la constante K porque la función necesita tiempo para asignar o desasignar memoria a una variable o realizar una operación matemática. Usamos K para definir el tiempo ya que es muy diminuto e insignificante.
• La complejidad temporal de este programa recursivo puede calcularse simplemente ya que, en el peor de los casos, el método doSomething() se llama n veces. Formalmente hablando, la complejidad temporal de la función es O(N).

Recursión de árbol

• Cuando realiza una llamada recursiva en su caso recursivo más de una vez, se denomina recursividad de árbol. Un ejemplo eficaz de la recursividad del árbol es la secuencia de Fibonacci. Las funciones recursivas de árbol operan en tiempo exponencial; no son lineales en su complejidad temporal.
• Eche un vistazo al pseudocódigo a continuación,

 function doSomething(n) { // base case to stop recursion if n is less than 2: return n; // here is some instructions // recursive step return doSomething(n-1) + doSomething(n-2); } 

• La única diferencia entre este código y el anterior es que este realiza una llamada más a la misma función con un valor menor de n.
• Pongamos T(n) = T(n-1) + T(n-2) + k como la relación de recurrencia para esta función. K sirve una vez más como constante.
• Cuando se realiza más de una llamada a la misma función con valores más pequeños, este tipo de recursividad se conoce como recursividad de árbol. El aspecto intrigante ahora es: ¿cuánto tiempo requiere esta función?
• Adivine basándose en el árbol de recursividad a continuación para la misma función.
  
• Puede que se le ocurra que es un desafío estimar la complejidad del tiempo observando directamente una función recursiva, particularmente cuando se trata de una recursividad de árbol. El método del árbol de recursión es una de varias técnicas para calcular la complejidad temporal de dichas funciones. Examinémoslo con más detalle.

¿Qué es el método del árbol de recursividad?

• Las relaciones de recurrencia como T(N) = T(N/2) + N o las dos que cubrimos anteriormente en la sección de tipos de recursividad se resuelven utilizando el enfoque del árbol de recursividad. Estas relaciones recurrentes a menudo utilizan una estrategia de divide y vencerás para abordar los problemas.
• Se necesita tiempo para integrar las respuestas a los subproblemas más pequeños que se crean cuando un problema más grande se divide en subproblemas más pequeños.
• La relación de recurrencia, por ejemplo, es T(N) = 2 * T(N/2) + O(N) para el tipo Merge. El tiempo necesario para combinar las respuestas a dos subproblemas con un tamaño combinado de T(N/2) es O(N), lo cual también es cierto en el nivel de implementación.
• Por ejemplo, dado que la relación de recurrencia para la búsqueda binaria es T(N) = T(N/2) + 1, sabemos que cada iteración de la búsqueda binaria da como resultado un espacio de búsqueda que se reduce a la mitad. Una vez determinado el resultado, salimos de la función. A la relación de recurrencia se le ha agregado +1 porque se trata de una operación de tiempo constante.
• La relación de recurrencia T(n) = 2T(n/2) + Kn es una que se debe considerar. Kn denota la cantidad de tiempo necesaria para combinar las respuestas a subproblemas de n/2 dimensiones.
• Representemos el árbol de recursividad para la relación de recurrencia antes mencionada.

Podemos sacar algunas conclusiones del estudio del árbol de recursividad anterior, incluyendo

1. La magnitud del problema en cada nivel es lo único que importa para determinar el valor de un nodo. El tamaño del problema es n en el nivel 0, n/2 en el nivel 1, n/2 en el nivel 2, etc.

cadena.contiene java

2. En general, definimos la altura del árbol como igual a log (n), donde n es el tamaño del problema y la altura de este árbol recursivo es igual al número de niveles del árbol. Esto es cierto porque, como acabamos de establecer, las relaciones de recurrencia utilizan la estrategia de divide y vencerás para resolver problemas, y pasar de un tamaño de problema n a un tamaño de problema 1 simplemente requiere tomar log (n) pasos.

• Considere el valor de N = 16, por ejemplo. Si se nos permite dividir N entre 2 en cada paso, ¿cuántos pasos se requieren para obtener N = 1? Considerando que estamos dividiendo por dos en cada paso, la respuesta correcta es 4, que es el valor de log(16) base 2.

registro(16) base 2

registro(2^4) base 2

4 * log(2) base 2, ya que log(a) base a = 1

entonces, 4 * log(2) base 2 = 4

3. En cada nivel, el segundo término de la recurrencia se considera raíz.

Aunque la palabra 'árbol' aparece en el nombre de esta estrategia, no es necesario ser un experto en árboles para comprenderla.

¿Cómo utilizar un árbol de recursividad para resolver relaciones de recurrencia?

El costo del subproblema en la técnica del árbol de recursividad es la cantidad de tiempo necesario para resolver el subproblema. Por lo tanto, si observa la frase 'costo' vinculada con el árbol de recursividad, simplemente se refiere a la cantidad de tiempo necesaria para resolver un determinado subproblema.

Entendamos todos estos pasos con algunos ejemplos.

Ejemplo

Considere la relación de recurrencia,

T(n) = 2T(n/2) + K

Solución

La relación de recurrencia dada muestra las siguientes propiedades,

Un problema de tamaño n se divide en dos subproblemas, cada uno de ellos de tamaño n/2. El costo de combinar las soluciones a estos subproblemas es K.

Cada problema de tamaño n/2 se divide en dos subproblemas, cada uno de tamaño n/4, y así sucesivamente.

En el último nivel, el tamaño del subproblema se reducirá a 1. En otras palabras, finalmente llegamos al caso base.

Sigamos los pasos para resolver esta relación de recurrencia,

k algoritmo del vecino más cercano

Paso 1: dibujar el árbol de recursividad

Paso 2: Calcula la altura del árbol

Como sabemos que cuando dividimos continuamente un número entre 2, llega un momento en que este número se reduce a 1. Al igual que con el tamaño del problema N, supongamos que después de K divisiones entre 2, N se vuelve igual a 1, lo que implica, ( norte/2^k) = 1

Aquí n/2^k es el tamaño del problema en el último nivel y siempre es igual a 1.

Ahora podemos calcular fácilmente el valor de k a partir de la expresión anterior llevando log() a ambos lados. A continuación se muestra una derivación más clara,

norte = 2^k

• registro(n) = registro(2^k)
• registro(n) = k * registro(2)
• k = iniciar sesión(n) / iniciar sesión(2)
• k = log(n) base 2

Entonces la altura del árbol es log (n) en base 2.

Paso 3: Calcule el costo en cada nivel

• Costo en el Nivel 0 = K, se fusionan dos subproblemas.
• Costo en el Nivel 1 = K + K = 2*K, dos subproblemas se fusionan dos veces.
• Costo en el Nivel 2 = K + K + K + K = 4*K, dos subproblemas se fusionan cuatro veces. etcétera....

Paso 4: Calcule la cantidad de nodos en cada nivel

Primero determinemos la cantidad de nodos en el último nivel. Del árbol de recursividad podemos deducir esto.

• El nivel 0 tiene 1 (2^0) nodo
• El nivel 1 tiene 2 (2^1) nodos
• El nivel 2 tiene 4 (2^2) nodos
• El nivel 3 tiene 8 (2^3) nodos

Entonces, el nivel log(n) debe tener 2^(log(n)) nodos, es decir, n nodos.

Paso 5: Resume el costo de todos los niveles.

• El costo total se puede escribir como,
• Costo total = Costo de todos los niveles excepto el último nivel + Costo del último nivel
• Costo total = Costo para el nivel 0 + Costo para el nivel 1 + Costo para el nivel 2 +.... + Costo para el nivel log(n) + Costo para el último nivel

El costo del último nivel se calcula por separado porque es el caso base y no se realiza ninguna fusión en el último nivel, por lo que el costo para resolver un solo problema en este nivel es un valor constante. Tomémoslo como O (1).

Pongamos los valores en las fórmulas,

• T(n) = K + 2*K + 4*K + .... + log(n)` veces + `O(1) * n
• T(n) = K(1 + 2 + 4 + .... + log(n) veces)` + `O(n)
• T(n) = K(2^0 + 2^1 + 2^2 + ....+ log(n) veces + O(n)

Si observas detenidamente la expresión anterior, forma una progresión geométrica (a, ar, ar^2, ar^3... tiempo infinito). La suma de GP viene dada por S(N) = a / (r - 1). Aquí está el primer término y r es la razón común.