8.1: Las muchas caras de la recursión

Considera las siguientes definiciones, todas las cuales deberían ser algo familiares para ti. Al leerlos, concéntrate en cómo son similares.

Coeficientes binomiales

Aquí hay una definición recursiva de coeficientes binomiales, que introdujimos en el Capítulo 2.

Definición\(\PageIndex{1}\): Binomial Coefficient - Recursion Definition

Asumir\(n\geq 0\) y\(n \geq k \geq 0\text{.}\) Definimos\(\binom{n}{k} \) por

• \(\displaystyle \binom{n}{0} = 1\)
• \(\binom{n}{n} =1\)y
• \(\binom{n}{k} = \binom{n-1}{k}+\binom{n-1}{k-1}\)si\(n > k > 0\)

Observación\(\PageIndex{1}\)

Una palabra sobre definiciones: Estrictamente hablando, cuando se definen objetos matemáticos como los coeficientes binomiales, deben definirse solo una vez. Dado que antes definimos coeficientes binomiales, en la Definición 2.4.1, otras declaraciones que los describan deberían ser teoremas. El teorema, en este caso, sería que la “definición” anterior es congruente con la definición original. Nuestro punto en este capítulo al discutir la recursión es observar definiciones alternativas que tienen una naturaleza recursiva. En los ejercicios, tendrás la oportunidad de demostrar que las dos definiciones son efectivamente equivalentes.

Así es como podemos aplicar la definición recursiva para calcular\(\binom{5}{2} \text{.}\)

\ begin {equation*}\ begin {split}\ binom {5} {2} &=\ binom {4} {2} +\ binom {4} {1}\\ &= (\ binom {3} {2} +\ binom {3} {1}) + (\ binom {3} {1} +\ binom {3} {0})\\ &= binom {3} {2} +2\ binom {3} {1} + 1\\ &= (\ binom {2} {2} +\ binom {2} {1}) + 2 (\ binom {2} {1} +\ binom {2} {0}) +1\\ &= (1+\ binom {2} {1}) + 2 (\ binom {2} {1} + 1) + 1\\ &=3\ binom {2} {1} + 4\\ &=3 (\ binom {1} {1} +\ binom {1} {0}) + 4\\ &=3 (1+1) +4 = 10\ end {split}\ end {ecuación*}

Polinomios y su evaluación

Definición\(\PageIndex{2}\): Polynomial Expression in \(x\) over \(S\) (Non-Recursive)

Dejar\(n\) ser un entero,\(n\geq 0\text{.}\) Un polinomio de\(n^{\text{th}}\) grado en\(x\) es una expresión de la forma\(a_nx^n+ a_{n-1}x^{n-1}+ \cdots + a_1x+a_0\text{,}\) donde\(a_n, a_{n-1},\ldots ,a_1,a_0\) se encuentran elementos de algún conjunto designado de números,\(S\text{,}\) llamado el conjunto de coeficientes y\(a_n\neq 0\text{.}\)

Nos referimos aquí\(x\) como una variable, aunque el término más preciso para\(x\) es una indeterminada. Hay una distinción entre los términos indeterminado y variable, pero esa distinción no entrará en juego en nuestras discusiones.

Los polinomios de grado cero se denominan polinomios constantes y son simplemente elementos del conjunto de coeficientes.

Esta definición a menudo se introduce en cursos de álgebra para describir expresiones como\(f(n) = 4n^3 + 2n^2 - 8n + 9\text{,}\) un polinomio de tercer grado, o cúbico, en\(n\text{.}\) Esta definición tiene un inconveniente cuando a la variable se le da un valor y la expresión debe ser evaluada. Por ejemplo, supongamos que\(n = 7\text{.}\) Tu primer impulso es probable que haga esto:

\ begin {ecuación*}\ begin {split} f (7) &= 4\ cdot 7^3 + 2\ cdot 7^2 - 8\ cdot 7 + 9\\ &=4\ cdot 343 +2\ cdot 49 -8\ cdot 7+9\\ &= 1423\ end {split}\ end {equation*}

Un recuento del número de operaciones realizadas muestra que se realizaron cinco multiplicaciones y tres adiciones/restas. Las dos primeras multiplicaciones\(7^2\) computan\(7^3\text{,}\) y las tres últimas multiplican las potencias de 7 veces los coeficientes. Esto le da los cuatro términos; y agregar/restar una lista de\(k\) números requiere\(k-1\) sumar/restar. La siguiente definición de una expresión polinómica sugiere otro método de evaluación más eficiente.

Definición\(\PageIndex{3}\): Polynomial Expression in \(x\) over \(S\) (Recursive)

Dejar\(S\) ser un conjunto de coeficientes y\(x\) una variable.

1. Una expresión polinómica de grado cero en\(x\) over\(S\) es un elemento distinto de cero de\(S\text{.}\)
2. Para\(n\geq 1\text{,}\) un\(n^{th}\) grado, la expresión polinómica en\(x\) over\(S\) es una expresión de la forma\(p(x)x + a\) donde\(p(x)\) es una expresión polinómica de\((n-1)^{st}\) grado en\(x\) y\(a\in S\text{.}\)

Podemos verificar fácilmente que\(f(n) = 4n^3 + 2n^2 - 8n + 9\) es una expresión polinómica de tercer grado en\(n\) más\(\mathbb{Z}\) basado en esta definición:

\ comenzar {ecuación*} f (n) = 4n^3 + 2n^2 - 8n + 9 = ((4n+2) n-8) n+9\ final {ecuación*}

Observe que 4 es un polinomio de grado cero ya que es un entero. Por lo tanto\(4n + 2\) es un polinomio de primer grado; por lo tanto,\((4n + 2) n - 8\) es un polinomio de segundo grado en\(n\) más\(\mathbb{Z}\text{;}\) por lo tanto,\(f(n)\) es un polinomio de tercer grado en\(n\) más\(\mathbb{Z}\text{.}\) La expresión final para\(f(n)\) se llama su forma telescópica . Si lo usamos para calcular solo\(f(7)\text{,}\) necesitamos tres multiplicaciones y tres adiciones/restas. Esto se llama método de Horner para evaluar una expresión polinómica.

Ejemplo\(\PageIndex{1}\): More Telescoping Polynomials

1. La forma telescópica de\(p(x) = 5x^4 + 12x^3 -6x^2 + x + 6\) es\((((5x + 12) x - 6) x + 1) x + 6\text{.}\) Usando el método de Horner, calcular el valor de\(p(c)\) requiere cuatro multiplicaciones y cuatro adiciones/restas para cualquier número real\(c\text{.}\)
2. \(g(x) = -x^5 + 3x^4 + 2x^2 + x\)tiene la forma telescópica\(((((- x + 3) x ) x + 2) x + 1) x\text{.}\)

Muchos lenguajes informáticos representan polinomios como listas de coeficientes, generalmente comenzando con el término constante. Por ejemplo, se\(g(x) = -x^5 + 3x^4 +\text{ }2x^2 + x\) representaría con la lista Tanto\(\{0,1,2,0,3,-1\}\text{.}\) en Mathematica como en Sage, se pueden ingresar y manipular expresiones polinómicas, por lo que la representación de lista es sólo interna. Algunos lenguajes de programación requieren que los usuarios programen operaciones polinómicas con listas. Dejaremos estos temas de programación a otra fuente.

Búsqueda Recursiva - La Búsqueda Binaria

A continuación, consideramos un algoritmo recursivo para una búsqueda binaria dentro de una lista ordenada de elementos. Supongamos que\(r=\{r(1),r(2), \ldots , r(n)\}\) representan una lista de\(n\) elementos ordenados por una clave numérica en orden descendente. El\(j^{th}\) elemento se denota\(r(j)\) y su valor clave por\(r(j).\texttt{key}\text{.}\) Por ejemplo, cada elemento puede contener datos sobre los edificios de una ciudad y el valor clave podría ser la altura del edificio. Entonces\(r(1)\) sería el rubro para el edificio más alto y\(r(1).\texttt{key}\) sería su altura. El algoritmo se\(\texttt{BinarySearch}(j, k)\) puede aplicar para buscar un ítem\(r\) con valor clave\(C\text{.}\) Esto se lograría mediante la ejecución de\(\texttt{BinarySearch}(1, n)\text{.}\) Cuando se complete el algoritmo, la variable\(\texttt{Found}\) tendrá un valor de\(\texttt{true}\) si se encontró un ítem con el valor de clave deseado, y el valor de\(\textrm{location}\) será el índice de un ítem cuya clave es\(C\text{.}\) Si\(\texttt{Found}\) mantiene el valor\(\texttt{false}\text{,}\) no existe tal ítem en la lista. La idea general detrás del algoritmo se ilustra en la Figura\(\PageIndex{1}\)

Figura\(\PageIndex{1}\): Esquema general para una búsqueda binaria

En la siguiente implementación de la Búsqueda Binaria en SageMath, buscamos dentro de una lista ordenada de enteros. Por lo tanto, los artículos en sí son las claves.

def BinarySearch(r,j,k,C):
    found = False
    if j <= k:
        mid = floor((j+k)/2)
        print('probing at position '+str(mid))
        if r[mid] == C:
            location = mid
            found = True

Secuencias definidas recursivamente

Para los dos ejemplos siguientes, considere una secuencia de números como una lista de números que consiste en un número cero, un primer número, un segundo número,... Si a una secuencia se le da el nombre\(S\text{,}\) el\(k^{th}\) número de\(S\) suele escribirse\(S_k\) o\(S(k)\text{.}\)

Ejemplo\(\PageIndex{2}\): Geometric Growth Sequence

Definir la secuencia de números\(B\) por

\ start {ecuación*} B_0 = 100\ textrm {y}\ end {ecuación*}

\ begin {ecuación*} b_k = 1.08 B_ {k-1}\ textrm {for} k\ geq 1\ texto {.} \ end {ecuación*}

Estas reglas estipulan que cada número de la lista es 1.08 veces el número anterior, siendo el número inicial igual a 100. Por ejemplo

\ begin {ecuación*}\ begin {split} B_3 &= 1.08 B_2\\ &=1.08\ izquierda (1.08B_1\ derecha)\\ &= 1.08\ izquierda (1.08\ izquierda (1.08 B_0\ derecha)\ derecha)\\ & = 1.08 (1.08 (1.08\ cdot 100))\\ &= 1.08^3\ cdot 100 125.971\ end {split}\ end {equation*}

Ejemplo \(\PageIndex{3}\): The Fibonacci Sequence

La secuencia de Fibonacci es la secuencia\(F\) definida por

\ begin {ecuación*} F_0= 1\ textrm {,} F_1= 1\ textrm {y}\ end {ecuación*}

\ begin {ecuación*} F_k = F_ {k-2} + F_ {k-1}\ textrm {for} k\ geq 2\ end {ecuación*}

Recursión

Todos los ejemplos anteriores se presentaron recursivamente. Es decir, cada “objeto” se describe en una de dos formas. Una forma es por una definición simple, que generalmente se llama la base de la recursión. La segunda forma es mediante una descripción recursiva en la que los objetos se describen en términos de sí mismos, con la siguiente calificación. Lo esencial para un uso adecuado de la recursión es que los objetos puedan expresarse en términos de objetos más simples, donde “más simple” significa más cerca de la base de la recursión. Para evitar lo que podría considerarse una definición circular, la base debe alcanzarse después de un número finito de aplicaciones de la recursión.

Para determinar, por ejemplo, el cuarto ítem de la secuencia de Fibonacci aplicamos repetidamente la regla recursiva para\(F\) hasta que nos quedemos con una expresión que involucra\(F_0\) y\(F_1\text{:}\)

\ begin {ecuation*}\ begin {split} F_4 &= F_2+F_3\\ &=\ left (F_0+F_1\ right) +\ left (F_1+F_2\ right)\\ &=\ left (F_0+F_1\ right) +\ left (F_1+\ left (F_0+F_1\ right)\ right)\ &= (1+1) + (1+ (1+1))\\ &=5\ end {split}\ end {ecuación*}

Iteración

Por otro lado, podríamos calcular un término en la secuencia de Fibonacci tal como\(F_5\) comenzando con los términos básicos y trabajando hacia adelante de la siguiente manera:

Mesa\(\PageIndex{1}\)

\(F_2= F_0+ F_1 =1 + 1 =2\)

\(F_3= F_1+ F_2=1+ 2=3\)

\(F_4= F_2+F_3=2+3=5\)

\(F_5=F_3+F_4= 3+5=8\)

Esto se denomina cálculo iterativo de la secuencia de Fibonacci. Aquí comenzamos con la base y trabajamos nuestro camino hacia un número menos simple, como el 5. Intenta computar\(F_5\) usando la definición recursiva para\(F\) como lo hicimos para\(F_4\text{.}\) Tomará mucho más tiempo del que hubiera tardado en hacer los cálculos anteriores. Los cálculos iterativos suelen ser más rápidos que los cálculos que aplican recursión. Por lo tanto, una habilidad útil es poder convertir una fórmula recursiva en una fórmula no recursiva, como una que requiere solo iteración o un método más rápido, si es posible.

Una fórmula iterativa para también\(\binom{n}{k} \) es mucho más eficiente que una aplicación de la definición recursiva. La definición recursiva no está exenta de méritos, sin embargo. Primero, la ecuación recursiva suele ser útil para manipular expresiones algebraicas que involucran coeficientes binomiales. En segundo lugar, nos da una idea de la interpretación combinatoria de\(\binom{n}{k}\text{.}\) Al elegir\(k\) elementos de\(\{1, 2, . . . , n\}\text{,}\) hay\(\binom{n-1}{k}\) formas de elegir todos\(k\)\(\{1,2, . . . ,n - 1\}\text{,}\) y hay\(\binom{n-1}{k-1}\) formas de elegir los\(k\) elementos si\(n\) se va a seleccionar y el \(k - 1\)elementos restantes provienen de\(\{1, 2, . . . , n - 1\}\text{.}\) Observe cómo usamos la Ley de Adición del Capítulo 2 en nuestro razonamiento.

BinarySearch Revisitado. En el algoritmo de búsqueda binaria, el lugar donde se utiliza la recursión es fácil de seleccionar. Cuando se examina un ítem y la clave no es la que deseas, la búsqueda se reduce a una sublista de no más de la mitad del número de ítems en los que estabas buscando antes. Obviamente, esta es una búsqueda más sencilla. La base está oculta en el algoritmo. Los dos casos que completan la búsqueda pueden considerarse como la base. O encuentras un elemento que quieres, o la sublista en la que te han dejado buscar está vacía, cuando\(j > k\text{.}\)

BinarySearch se puede traducir sin mucha dificultad a cualquier lenguaje que permita llamadas recursivas a sus subprogramas. La ventaja de tal programa es que su codificación sería mucho más corta que un programa no recursivo que realiza una búsqueda binaria. Sin embargo, en la mayoría de los casos la versión recursiva será más lenta y requerirá más memoria en el momento de la ejecución.

Inducción y Recursión

La definición de los enteros positivos en términos de Postulados de Peano es una definición recursiva. El elemento base es el número 1 y la recursión es que si\(n\) es un entero positivo, entonces también lo es su sucesor. En este caso,\(n\) es el objeto simple y la recursión es de tipo forward. Por supuesto, la validez de una prueba de inducción se basa en nuestra aceptación de esta definición. Por lo tanto, la aparición de pruebas de inducción cuando se utiliza recursión no es coincidencia.

Ejemplo\(\PageIndex{4}\): Proof of a Formula for \(B\)

Una fórmula para la secuencia\(B\) en el Ejemplo\(\PageIndex{2}\) es\(B = 100(1.08)^k\) para\(k\geq 0\text{.}\) A prueba por inducción seguir.

Si\(k= 0\text{,}\) entonces\(B = 100(1.08)^0 = 100\text{,}\) como se define. Ahora supongamos que para algunos\(k\geq 1\text{,}\) la fórmula para\(B_k\) es cierta.

\ begin {ecuation*}\ begin {split} B_ {k+1} &= 1.08B_k\ textrm {por la definición recursiva}\\ &=1.08\ left (100 (1.08) ^k\ right)\ textrm {por la hipótesis de inducción}\\ &= 100 (1.08) ^ {k+1}\ end {split}\ end {ecuación*}

por lo tanto, la fórmula es cierta para\(k+1\)

La fórmula que acabamos de probar\(B\) se llama expresión de forma cerrada. No implica signos de recurrencia o suma.

Definición\(\PageIndex{4}\): Closed Form Expression

Let\(E = E\left(x_1, x_2, \ldots ,x_n\right)\) Ser una expresión algebraica\(x_1, x_2, \ldots ,x_n\) que involucra variables a las que se les permite tomar valores de algún conjunto predeterminado. \(E\)es una expresión de forma cerrada si existe un número\(T\) tal que la evaluación de\(E\) con cualquier valor permitido de las variables no tomará más que\(T\) operaciones (alternativamente, unidades de\(T\) tiempo).

Ejemplo\(\PageIndex{5}\): Reducing a Summation to Closed Form

La suma no\(E(n)=\sum_{k=1}^n k\) es una expresión de forma cerrada porque el número de adiciones necesarias para evaluar\(E(n)\) crece indefinidamente con\(n\text{.}\) Una expresión de forma cerrada que calcula el valor de\(E(n)\) es la\(\frac{n(n+1)}{2}\text{,}\) que solo requiere\(T=3\) operaciones.

Ejercicios

Ejercicio\(\PageIndex{1}\)

Por la definición recursiva de coeficientes binomiales,\(\binom{7}{2}=\binom{6}{2} +\binom{6}{1}\text{.}\) Continuar expandiéndose\(\binom{7}{2}\) para expresarlo en términos de cantidades definidas por la base. Comprueba tu resultado aplicando la definición factorial de\(\binom{n}{k}\text{.}\)

Contestar

\ begin {equation*}\ begin {split}\ binom {7} {2} &=\ binom {6} {2} +\ binom {6} {1}\\ &=\ binom {5} {2} +\ binom {5} {1} +\ binom {5} {1} +\ binom {5} {0}\\ &=\ binom {5}} {2} +2\ binom {5} {1} +1\\ &=\ binom {4} {2} +\ binom {4} {1} +2 (\ binom {4} {1} +\ binom {4} {0}) +1\\ &=\ binom {4} {2} +3\ binom {4} {1} + 3\\ &= binom {3} {2} +\ binom {3} {1} +3 (\ binom {3} {1} +\ binom {3} {0}) +3\\ &=\ binom {3} {2} +4\ binom {3} {1} + 6\\ &=\ binom {2} {2} +\ binom {2} {1} + 4 (\ binom {2} {1} +\ binom {2} {0}) + 6\\ &=5\ binom {2} {1} + 11\\ &=5 (\ binom {1} {1} +\ binom {1} {0}) + 11\\ &=21\ end {split}\ end {equation*}

Ejercicio\(\PageIndex{2}\)

Definir la secuencia\(L\) por\(L_0 = 5\) y para\(k\geq 1\text{,}\)\(L _k = 2L_{k-1}-7\text{.}\) Determinar\(L_4\) y probar por inducción que\(L_k=7-2^{k+1}\text{.}\)

Ejercicio\(\PageIndex{3}\)

Let\(p(x) = x^5+ 3x^4 - 15x^3 + x - 10\text{.}\)

1. Escribir\(p(x)\) en forma telescópica.
2. Use una calculadora para calcular\(p(3)\) usando la forma original de\(p(x)\text{.}\)
3. Use una calculadora para calcular\(p(3)\) usando la forma telescópica de\(p(x)\text{.}\)
4. Compara tu velocidad en las partes b y c.

Contestar

1. \(p(x)\)en forma telescópica:\(((((x+3)x-15)x+0)x+1)x-10\)
2. \(\displaystyle p(3)=((((3+3)3-15)3-0)3+1)3-10=74\)

Ejercicio\(\PageIndex{4}\)

Supongamos que una lista de nueve ítems,\((r(l), r(2), . . . , r(9))\text{,}\) se ordena por clave en orden decreciente para que\(r(3).\texttt{key} = 12\) y\(r(4).\texttt{key} = 10\text{.}\) Liste las ejecuciones de los algoritmos BinarySearch que serían necesarios para completar BinarySearch (1,9) cuando:

1. La clave de búsqueda es C = 12
2. La clave de búsqueda es C = 11

Supongamos que los elementos distintos tienen claves distintas.

Ejercicio\(\PageIndex{5}\)

¿Qué hay de malo en la siguiente definición de\(f:\mathbb{R}\to \mathbb{R}\text{?}\)\(f(0) = 1\) y\(f(x) = f(x/2)/2\) si\(x\neq 0\text{.}\)

Contestar

La base no se alcanza en un número finito de pasos si intenta calcular\(f(x)\) para un valor distinto de cero de\(x\text{.}\)

Ejercicio\(\PageIndex{6}\)

Demostrar que las dos definiciones de los coeficientes binomios, Definición 2.4.1 y Definición\(\PageIndex{1}\), son equivalentes.

Ejercicio\(\PageIndex{7}\)

Demostrar por inducción que si\(n \geq 0\text{,}\)\(\sum_{k=0}^n \binom{n}{k} = 2^n\)