Hasta ahora hemos resuelto problemas de conteo utilizando principios como el aditivo, el multiplicativo o el de inclusión-exclusión. Estas herramientas resultan muy útiles para muchas situaciones, pero en ciertos casos se vuelven poco prácticas o demasiado complicadas.

Imagina, por ejemplo, que quieres saber de cuántas maneras distintas se pueden ordenar a cinco personas en una fila para tomarse una fotografía. Aplicar el principio multiplicativo implicaría multiplicar 5 opciones para la primera posición, 4 para la segunda, 3 para la tercera, y así sucesivamente. Aunque se puede resolver, el procedimiento no es tan directo si generalizamos el problema a 20 o 100 personas.

Otro caso aparece cuando se desea formar un comité de tres estudiantes elegidos entre diez compañeros. Aquí el orden de selección no importa: elegir a Ana, Beatriz y Carlos es lo mismo que elegir a Carlos, Beatriz y Ana. El principio multiplicativo no diferencia estas repeticiones, y habría que hacer ajustes adicionales que complican los cálculos.

Para resolver este tipo de situaciones de manera sistemática y eficiente, introducimos dos conceptos: permutaciones, que se enfocan en el ordenamiento de elementos, y combinaciones, que se centran en la selección de subconjuntos sin importar el orden. Estos nos permitirán ampliar el alcance de nuestras herramientas de conteo y enfrentar problemas más complejos de forma ordenada y general.

Una permutación de un conjunto de objetos es un ordenamiento de dichos objetos en un renglón. Por ejemplo, el conjunto de elementos {a,b,c} tiene seis permutaciones distintas:

\[ \{abc, acb, bac, bca, cab, cba\} \]

Cada una de estas secuencias representa un orden diferente de los mismos tres elementos. Como se puede observar, cuando el orden importa, el número de formas de organizar los elementos crece rápidamente.

Desde un punto de vista más formal, dado un conjunto A, una permutación de los elementos de A es una función biyectiva f:A→A, es decir, una correspondencia uno a uno entre los elementos del conjunto consigo mismo, que reordena sus elementos.

Si el conjunto A es finito y tiene n elementos, entonces el número total de permutaciones posibles es:

\[ n! = n \cdot (n-1) \cdot (n-2) \cdot \dots \cdot 2 \cdot 1 \]

Este resultado se deduce directamente del principio multiplicativo: hay n opciones para el primer lugar, n-1 para el segundo, y así sucesivamente hasta el último.

Ejemplo 1. ¿Cuántas formas diferentes hay de ordenar las letras de la palabra PUCE?

Solución:

La palabra tiene 4 letras distintas, por lo que el número total de permutaciones es:

\[ 4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24 \]

Ejemplo 2. ¿Cuántas formas diferentes hay de sentar a 8 personas en una fila?

Solución:

Como el orden importa, se trata de una permutación de 8 elementos:

\[ 8! = 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 40320 \]

es decir, existen 40320 formas distintas.

Ejemplo 3. ¿Cuántas formas diferentes hay de sentar a 8 personas en una mesa redonda?

Solución:

A diferencia del caso anterior —donde analizamos cómo ubicar a ocho personas en una fila—, en esta situación no hay extremos ni una posición inicial fija que distinga a un lugar del resto. Lo que importa es cómo están posicionadas unas personas respecto a otras, no el punto de inicio del conteo.

Cuando las permutaciones son circulares, cualquier rotación del mismo arreglo lineal se considera equivalente. Para contar únicamente las disposiciones distintas, se puede fijar a una de las personas en una posición cualquiera, y permutar a las demás alrededor de ella.

Como ya no se tienen en cuenta las rotaciones, el número de maneras distintas de sentar a las ocho personas es:

\[ (8-1)! = 7! = 5040 \text{ formas} \]

En estes ejemplo, hemos usado todos los elementos del conjunto para hacer las permutaciones, ahora, ¿qué pasa si no usamos todos los elementos sino solo unos cuantos? Esta es una versión más general: las r-permutaciones.

Una r-permutación (o variación) de un conjunto de n elementos es una selección ordenada de r elementos tomados del conjunto. Formalmente, se trata de una función biyectiva definida sobre un subconjunto

\[ B \subseteq A, \quad \text{con } |B| = r \]

El número de r-permutaciones de un conjunto de n elementos se denota por P(n,r) y se calcula como:

\[ P(n,r) = n (n-1) (n-2) \cdots (n-r+1) \]

o equivalentemente

\[ P(n,r) = \frac{n!}{(n-r)!} \]

Ejemplo 4. ¿Cuántas formas hay de seleccionar y ordenar 2 letras de la palabra PUCE?

Solución:

Aquí n=4 (hay 4 letras distintas), y queremos todas las 2-permutaciones:

\[ P(4,2) = \frac{4!}{(4-2)!} = \frac{4!}{2!} = \frac{4 \cdot 3 \cdot 2 \cdot 1}{2 \cdot 1} = 4 \cdot 3 = 12 \]

Muchas calculadoras científicas permiten calcular P(n,r) directamente, simplemente ingresando los valores de n y r, y seleccionando la función adecuada desde el menú o utilizando una tecla específica.

Dependiendo del modelo, es posible que encuentres notaciones alternativas para las r-permutaciones como:

\( P_{n,r}, \quad P_n^r, \quad nPr \)

Te recomendamos consultar el manual de tu calculadora para identificar la notación exacta y la secuencia de pasos correspondiente.

Revisemos algunos ejemplos adicionales tomados de Johnsonbaugh (2018).

Ejemplo 5. ¿De cuántas maneras pueden ordenarse las letras de la palabra ALGORITHM?

Solución:

La palabra tiene 9 letras distintas, así que:

\[ 9! = 362880 \text{ formas distintas} \]

En algunos problemas, ciertas letras o elementos deben mantenerse juntas como una unidad. En esos casos, se puede considerar esa unidad como un solo «bloque» y aplicar permutaciones al conjunto modificado.

Ejemplo 6. ¿Cuántas formas hay de ordenar las letras de ALGORITHM si las letras A y L deben permanecer juntas (en ese orden)?

Solución:

Consideramos «AL» como una sola unidad. Entonces estamos permutando 8 bloques: AL, G, O, R, I, T, H, M:

\[ 8! = 40320 \text{ formas distintas} \]

Supongamos que tenemos un conjunto S con n elementos, y deseamos formar subconjuntos de tamaño r sin importar el orden. ¿Cuántos subconjuntos distintos se pueden formar?

A cada uno de estos subconjuntos se lo llama una r- combinación del conjunto S. Es decir, una r-combinación es una selección de r elementos de S, sin tomar en cuenta el orden de los elementos. A diferencia de las permutaciones, aquí los arreglos como ab y ba se consideran el mismo subconjunto.

El número total de r-combinaciones de un conjunto de n elementos se denota por C(n,r), y también se conoce como el coeficiente binomial, que se escribe como:

\[ C(n,r) = \frac{P(n,r)}{r!} = \frac{n!}{r!(n-r)!} \]

En varios texto, se encuentra también esta notación para el coeficiente binomial:

\[ \binom{n}{r} \]

Al igual que para la permutaciones, muchas calculadoras científicas permiten calcular esto directamente, dependiendo del modelo, es posible que encuentres notaciones alternativas para las r-combinaciones como:

\( C_{n,r}, \quad C_n^r, \quad nCr \)

Ejemplo 7. ¿Cuántas formas hay de seleccionar 2 letras de la palabra PUCE si el orden no importa?

Solución:

En este caso se trata de una combinación de 2 elementos de un total de 4.

\[ C(4,2) = \binom{4}{2} = \frac{4!}{2! \cdot (4-2)!} = \frac{24}{2 \cdot 2} = 6 \]

Los subconjuntos son: PU, PC, PE, UC, UE, CE.

Ejemplo 8. ¿Cuántas formas distintas hay de formar un comité de 3 personas a partir de un grupo de 5?

Solución:

El orden en el comité no importa, así que usamos combinaciones:

\[ C(5,3) = \frac{5!}{3! \cdot (5-3)!} = \frac{5!}{3! \cdot 2!} = \frac{120}{6 \cdot 2} = 10 \]

Ejemplo 9. Suponga que en un grupo de 12 personas, hay dos que insisten en trabajar juntas o no participar. ¿Cuántos equipos de 5 personas se pueden formar bajo esa condición?

Solución:

Tenemos dos casos:

• Caso 1: el equipo incluye a los dos inseparables. Entonces debemos elegir 3 personas más de los 10 restantes: C(10,3)=120.
• Caso 2: el equipo no incluye a ninguno de los dos. Entonces elegimos las 5 personas entre las 10 restantes: C(10,5)=252.

Sumando ambos casos: 120+252=372" equipos posibles".

Ejemplo 10. ¿Cuántas cadenas de 8 bits tienen exactamente tres 1?

Solución:

Imaginemos las 8 posiciones vacías donde deben colocarse los bits. Queremos que exactamente 3 de esas posiciones contengan un 1, y las otras 5 contengan un 0.

El problema se reduce a elegir en qué 3 de las 8 posiciones colocaremos los 1. Una vez elegidas esas posiciones, las restantes se completan automáticamente con 0. Por lo tanto, el número total de cadenas con exactamente tres 1 es igual al número de subconjuntos de 3 posiciones elegidas entre 8 posibles:

\[ C(8,3) = \frac{8!}{3! \cdot 5!} = 56 \]

Entonces, existen 56 cadenas de 8 bits que contienen exactamente tres 1.

Ejemplo 11. Consideremos el juego tradicional ecuatoriano: el 40, en el que se utiliza una baraja sin las cartas del 8 al 10, es decir, una baraja de 40 cartas. Se reparten 5 cartas a un jugador. Analicemos algunas situaciones:

• ¿Cuántas manos distintas de 5 cartas se pueden repartir?

Figura 1

Ejemplo de una mano en el 40

Solución: Se trata de seleccionar 5 cartas sin importar el orden, de un conjunto de 40:

\[ C(40,5) = \frac{40!}{5! \cdot 35!} = 658008 \text{ manos posibles} \]

¿En cuántas manos aparece una «ronda» (es decir, un trío)?

Figura 2

Ejemplo de una ronda en el 40

Solución: Una ronda ocurre cuando se tienen tres cartas del mismo número (por ejemplo, tres K) y las otras dos cartas tienen denominaciones distintas del trío.

El número total de tríos se puede calcular en cuatro pasos:

• Elegimos la denominación del trío: hay 10 denominaciones (1 al 7 y J, Q, K): C(10,1).
• De esa denominación, elegimos 3 cartas entre las 4 posibles: C(4,3).
• De las cartas de las 9 denominaciones restantes (36 cartas), elegimos 2 diferentes para completar la mano: C(36,2).

Entonces, el total de manos con una ronda es: C(10,1)⋅C(4,3)⋅C(36,2)=10⋅4⋅630=25200.

¿En cuántas manos hay una doble ronda que gana el juego automáticamente (es decir, cuatro cartas del mismo número)?

Figura 3

Ejemplo de una doble ronda en el 40

Solución: Para contar las manos con exactamente un cuarteto y una carta adicional:

• Elegimos la denominación del cuarteto: C(10,1).
• Elegimos 4 cartas de esa denominación: C(4,4).
• De las 9 denominaciones restantes, elegimos 1 diferente: C(9,1).
• Para cada una, elegimos 1 carta entre 4: 4.

Entonces, el número total de manos con un cuarteto es: C(10,1)⋅C(4,4)⋅C(9,1)⋅4=10⋅1⋅9⋅4=360.

Hasta ahora hemos trabajado con situaciones en las que no se permitía repetir elementos: ni en las permutaciones (donde el orden importa), ni en las combinaciones (donde no importa). Sin embargo, en muchos contextos reales, los elementos pueden repetirse, y necesitamos adaptar nuestras herramientas de conteo para incluir estas posibilidades.

Por ejemplo, considera la palabra ENCEBOLLADO. Tiene 11 letras, pero algunas se repiten: hay 2 letras E, 2 letras L y 2 letras O. Si queremos contar cuántas «palabras distintas» podemos formar reordenando sus letras, no podemos simplemente usar 11!, porque estaríamos contando como diferentes arreglos que en realidad son idénticos por las repeticiones.

Para estos casos, usamos la siguiente fórmula: Dada una colección con n objetos de m tipos distintos, donde hay n_i objetos idénticos de cada tipo i, el número de ordenamientos de la colección es

\[ \frac{n!}{n_1! \, n_2! \, \cdots \, n_m!} \]

En el caso de ENCEBOLLADO, tenemos 8 «tipos» de letras distintas:

• Dos letras E
• Una letra N
• Una letra C
• Una letra B
• Dos letras O
• Dos letras L
• Una letra A
• Una letra D

así, el número de palabras que de pueden formar es

\[ \frac{11!}{2! \cdot 1! \cdot 1! \cdot 1! \cdot 2! \cdot 2! \cdot 1! \cdot 1!} = \frac{39916800}{8} = 4989600 \]

Otro tipo de problema común es cuando queremos hacer selecciones sin importar el orden, pero permitiendo repetir elementos. Supongamos que tenemos 5 tipos de helado, y queremos elegir una copa con 3 bolas, pudiendo repetir sabores.

En estos casos, usamos la siguiente fórmula: Dado un conjunto con n elementos, el número de selecciones no ordenadas de r elementos, con repeticiones, es

\[ C(n+r-1, r) = \binom{n+r-1}{r} \]

Así, en el ejemplo anterior, el número total de combinaciones posibles es:

\[ C(n+r-1, r) = C(5+3-1, 3) = C(7,3) = 35 \]

donde n es el número de tipos de elementos (sabores) y r el número de elementos que se seleccionan (bolas de helado).

También se pueden presentar problemas donde se desea distribuir elementos en grupos, como repartir caramelos entre niños, o asignar tareas entre empleados. Si queremos distribuir n elementos en k grupos (permitiendo que algunos grupos queden vacíos), sin importar el orden de los elementos ni de los grupos, usamos:

\[ C(n+k-1, k-1) = \binom{n+k-1}{k-1} \]

Ejemplo 12. ¿Cuántas soluciones enteras no negativas tiene la ecuación x_1+x_2+x_3+x_4=10?

Solución:

Este tipo de problema equivale a distribuir 10 unidades entre 4 variables (o cajas), permitiendo que alguna tenga cero. El número de soluciones se obtiene con:

\[ C(10+4-1, 4-1) = C(13,3) = 286 \]

A continuación se presenta una tabla resumen que compara las fórmulas para conteo en situaciones con o sin repetición, tanto en selecciones ordenadas (permutaciones) como no ordenadas (combinaciones):

Para realizar cálculos de permutaciones y combinaciones generalizadas en Python, podemos utilizar tanto la librería estándar math como funciones especiales del paquete scipy (White and Ray 2021). A continuación, se muestra un ejemplo que calcula el número de permutaciones y combinaciones al seleccionar 4 elementos de un conjunto de 20:

Código 1

Cálculo de permutaciones y combinaciones en Python

            
import math

# Cálculo de permutaciones P(20,4)
perm = math.factorial(20) / math.factorial(20 - 4)
print("Permutaciones:", perm)

# Cálculo de combinaciones C(20,4) usando scipy
from scipy.special import binom
comb = binom(20, 4)
print("Combinaciones:", comb)
# Nota: adaptado de White and Ray (2021)
            
          

Este código permite verificar fácilmente los resultados de los ejemplos vistos en clase y explorar nuevas situaciones modificando los valores de entrada.

La palabra «algoritmo» proviene del nombre del matemático persa del siglo IX, Muhammad ibn Musa al-Khwarizmi (Johnsonbaugh 2018), cuyas obras influyeron profundamente en el desarrollo de las matemáticas y la computación. Con el tiempo, su nombre fue latinizado como Algoritmo, y de ahí surgió el término que hoy usamos para referirnos a procedimientos precisos para resolver problemas.

En la actualidad, cuando hablamos de algoritmos, generalmente nos referimos a instrucciones claras y finitas que pueden ser ejecutadas por una computadora para transformar entradas en salidas. Sin embargo, los algoritmos no son exclusivos del mundo digital: también están presentes en nuestra vida cotidiana. Por ejemplo, seguir una receta de cocina para preparar un pastel implica una secuencia finita de pasos, donde se parte de unos ingredientes (entrada) y se obtiene un pastel (salida). Otro ejemplo es el algoritmo que aplicamos al buscar una palabra en un diccionario: comenzamos por la letra inicial, comparamos alfabéticamente y avanzamos hasta encontrar la entrada deseada.

También usamos algoritmos sin darnos cuenta al realizar tareas como calcular el vuelto en una compra, organizar libros por orden alfabético o seguir las instrucciones de montaje de un mueble. En todos estos casos, aplicamos un conjunto de reglas bien definidas para alcanzar un resultado. En el contexto de la computación, la diferencia es que los algoritmos deben estar escritos de forma tan precisa que una máquina pueda ejecutarlos sin ambigüedades ni interpretación humana.

Resolver un problema mediante un algoritmo requiere, en primer lugar, entender con claridad qué se desea obtener y cómo se presentan las situaciones a resolver. A esto lo llamamos problema algorítmico (Martínez 2022), y consiste en tres elementos fundamentales:

• Un problema a resolver.
• Una entrada, que describe las instancias que deseamos procesar.
• Una salida, que representa el resultado esperado y sus propiedades.

Ejemplo 1. Consideremos el siguiente problema algorítmico:

• Problema: Ordenar una lista finita de números enteros.
• Entrada: Una lista finita de números enteros L=[a₁,a₂,…,a_n].
• Salida: Una lista con los mismos elementos, pero ordenados de forma creciente: L'=[b₁,b₂,…,b_n] tal que b_i(i+1) para todo i, y que L' contenga exactamente los mismos elementos que L.

Un algoritmo es una serie de pasos finitos que resuelve un problema algorítmico. Esta serie de pasos debe funcionar correctamente para todas las posibles instancias válidas de entrada, no solo para unos pocos ejemplos. Su diseño implica especificar con claridad cómo se recibe la entrada, cómo se procesa y cómo se obtiene la salida deseada.

Todo algoritmo debe cumplir con las siguientes propiedades (Johnsonbaugh 2018; Erciyes 2021):

• Entrada: Puede recibir cero o más entradas desde el entorno externo. Ejemplo: Un algoritmo que genera un número aleatorio no necesita entrada; en cambio, uno que ordena números necesita una lista como entrada.
• Salida: Debe producir al menos una salida que sea la solución del problema. Ejemplo: El algoritmo que ordena una lista debe devolver una nueva lista ordenada.
• Definición precisa: Cada paso debe estar claramente definido y sin ambigüedad. Ejemplo: «Suma el número actual con el inmediato anterior» es claro; en cambio, «suma los números anteriores» es ambiguo.
• Finitud: El algoritmo debe terminar después de un número finito de pasos. Ejemplo: Un algoritmo que suma los primeros n números naturales termina; uno que espera una señal de red puede no terminar nunca.
• Efectividad: Cada operación debe ser básica y realizable en un tiempo razonable. Ejemplo: Dividir un número entre 2 es efectivo; calcular todos los posibles resultados de una operación sin límite de tiempo no lo es.
• Corrección: El algoritmo debe producir resultados correctos para todas las entradas válidas. Ejemplo: Un algoritmo que devuelve una lista ordenada de forma incorrecta no es útil, aunque termine rápido.

Es importante diferenciar entre un algoritmo y un programa. Un algoritmo es la idea general del procedimiento, mientras que un programa es su implementación concreta en un lenguaje que la computadora puede ejecutar. Además, algunos programas pueden estar diseñados para no terminar, como los servidores que esperan peticiones indefinidamente.

Un mismo algoritmo puede expresarse de diferentes maneras(Martínez 2022), dependiendo del nivel de abstracción:

• En lenguaje natural (palabras cotidianas).
• En pseudocódigo (una mezcla informal de instrucciones estructuradas).
• En lenguajes de programación como Python, C++, JavaScript, etc.

A medida que bajamos de nivel, los lenguajes son menos comprensibles para humanos pero más adecuados para que una computadora los ejecute. A esto se le llama nivel de abstracción: lo que está más «arriba» (lenguaje natural) es más expresivo, lo que está «abajo» (lenguaje de programación) es más formal y estructurado.

Incluso dentro de los lenguajes de programación existen distintos niveles. Por ejemplo, los lenguajes de alto nivel, como Python o Java, permiten escribir instrucciones cercanas al pensamiento humano, con estructuras de control y manejo automático de memoria. Por otro lado, los lenguajes de bajo nivel, como C o ensamblador, ofrecen mayor control sobre los recursos del sistema, pero requieren especificar detalles más técnicos, como la gestión de punteros o registros.

Figura 1

Niveles de abstracción

• Problema: Contar cuántos números impares hay en una lista.
• Entrada: Un número entero positivo n y una lista L = [a₁, a₂, …, aₙ].
• Salida: La cantidad de enteros en L que sean impares.

El algoritmo que resuelve este problema puede ser expresado en los diferentes niveles:

• Descripción en lenguaje natural:

Llevaremos una cuenta de cuántos números impares hay. Recorremos la lista de izquierda a derecha. Si el número no es divisible para 2 (es decir, si su residuo al dividirlo entre 2 es diferente a 0), aumentamos el contador. Al final, devolvemos ese número.

• Pseudocódigo:

Algoritmo 1

Figura

Algoritmo 1




• Código en Python:

Función Python - Contar Números Impares

            
def contar_impares(L):
    cont = 0
    for k in L:
        if k % 2 != 0:
            cont += 1
    print(cont)
            
          

Cuando diseñamos un algoritmo, no basta con que «parezca» que funciona: es esencial asegurarnos de que realmente resuelva el problema planteado en todos los casos posibles. Esta exigencia es similar a lo que ocurre con las demostraciones matemáticas: no se acepta una argumentación basada solo en ejemplos, sino que se requiere una justificación formal, clara y general.

De manera análoga, la correctitud de un algoritmo implica que, para toda entrada válida, el algoritmo produce la salida correcta según la especificación del problema. En otras palabras, un algoritmo es correcto si funciona correctamente en todas las instancias que debería resolver, no solo en algunas.

Para lograrlo, es importante acompañar cada algoritmo de una descripción precisa de lo que hace en cada paso, y de una demostración matemática que respalde su funcionamiento. Aunque en este curso no abordaremos a fondo las técnicas formales de verificación —como la inducción matemática, las invariantes de bucle o los esquemas de Hoare— es fundamental que desde ahora desarrolles el hábito de preguntarte no solo si un algoritmo funciona, sino si puedes justificar por qué funciona.

Veamos un ejemplo de un algoritmo que parece funcionar, pero en realidad no es correcto (Martínez 2022).

Ejemplo 3. Consideremos el siguiente problema algorítmico:

• Problema: Determinar si cierta expresión es un número primo.
• Entrada: Un número entero positivo n.
• Salida: Decidir si el número n² - n + 41 es un número primo.

Si probamos manualmente los valores de n=1,2,3,…,10, obtenemos las expresiones 41,43,47,53,61,71,83,97,113,131, que son todas ellas números primos. A partir de esto, alguien podría proponer un algoritmo que simplemente diga «sí» para cualquier valor de n, confiando en que la expresión siempre produce un número primo.

Sin embargo, esto sería un error. Aunque la expresión n² - n + 41 produce números primos durante un buen tramo inicial, no lo hace para siempre. Por ejemplo, si evaluamos en n=41, obtenemos:

\[ 41^2 - 41 + 41 = 1681 \]

Este número no es primo, ya que 1681=41×41. Por tanto, el algoritmo que responde siempre «sí» falla para esta instancia. Y basta con que falle en un solo caso para que el algoritmo sea incorrecto.

Este ejemplo muestra la importancia de no confiar únicamente en pruebas empíricas o ejemplos limitados. Aunque el algoritmo funcione para muchos valores de entrada, no podemos asegurar su validez general sin una demostración matemática. Demostrar la correctitud de un algoritmo es una tarea rigurosa, que en general requiere herramientas formales de razonamiento lógico y matemático, y cuya enseñanza excede el alcance de este curso. No obstante, debemos estar atentos a los posibles fallos y desconfiar de algoritmos que no tienen una justificación clara de por qué funcionan.

Una de las ideas más elegantes y poderosas en el diseño de algoritmos es la recursión. Una función se dice recursiva cuando se define a sí misma sobre entradas más pequeñas o simples del mismo problema. De manera general, podemos pensar en un proceso recursivo como aquel que resuelve un problema dividiéndolo en subproblemas de la misma naturaleza, hasta llegar a casos lo suficientemente simples como para resolverse directamente.

Formalmente, la recursión se basa en el siguiente principio:

Teorema 1: Principio de recursión finita.

Dados A un conjunto, c ∈ A, y una función g:A → A, existe una única función g:N → A tal que

1. \(f(0)=c\), y
2. \(f(n+1)=g(f(n))\), para todo \(n \in \mathbb{N}\).

Este principio nos permite definir funciones paso a paso: partimos de un valor inicial (caso base) y vamos generando los siguientes valores aplicando una misma regla (paso recursivo). Por ejemplo, si deseamos definir la potencia a^n para a∈R\{0} y n∈N, podemos usar una función recursiva.

Tomemos \( A = \mathbb{R} \), \( c = 1 \) y la función

\[ g : \mathbb{R} \to \mathbb{R}, \quad x \mapsto x \cdot a \]

Gracias al principio de recursión finita, existe una única función \(f:\mathbb{N}\to \mathbb{R}\) tal que:

• \(f(0)=1\)
• \(f(n+1)=g(f(n))=f(n)\cdot a,\) para todo \(n\ge 0\)

Si denotamos por a^n a f(n), obtenemos la definición recursiva de las potencias:

• \(a^0 = 1\)
• \(a^{n+1} = a^n \cdot a,\) para todo \(n \ge 0\)

Por motivos de programación, es más común escribir esta definición de forma descendente:

• \(a^0 = 1\)
• \(a^n = a^{n-1} \cdot a,\) para todo \(n > 0\)

En términos generales, el principio de recursión finita nos dice que, para definir una función f:N→A, basta con establecer un paso base (el valor inicial) y un paso recursivo (una regla que permita construir el siguiente valor a partir de los anteriores).

Por otro lado, un algoritmo es recursivo si resuelve un problema reduciéndolo a uno o más casos del mismo problema con entradas más pequeñas. Esto requiere siempre identificar dos cosas:

• Un caso base, que pueda resolverse directamente.
• Un caso recursivo, que reduzca el problema original y lo acerque al caso base.

Ejemplo 4. Consideremos el siguiente problema algorítmico:

• Problema: Calcular el factorial de un número natural n.
• Entrada: Un número natural n∈N.
• Salida: El valor de n!=1⋅2⋅3⋯n

La función factorial se puede definir de forma recursiva de la siguiente manera:

\[ n! = \begin{cases} 1, & \text{si } n = 0 \\ n \cdot (n-1)!, & \text{si } n > 0 \end{cases} \]

Esta definición captura los dos aspectos la función recursiva:

• El caso base: cuando n=0, el resultado es 1.
• El caso recursivo: cuando n>0, el resultado se obtiene multiplicando n por el factorial de n-1.

Ahora que entendemos la lógica detrás del factorial recursivo, podemos traducir la definición matemática a un lenguaje de programación. A continuación, se presenta el algoritmo primero en pseudocódigo para ilustrar la lógica de manera abstracta, y luego en Python, un lenguaje conocido por su sintaxis limpia que facilita la comprensión de la recursión.

Algoritmo 2

Cálculo recursivo del factorial

Ahora veamos cómo se traduce este mismo procedimiento a un lenguaje de programación.

Código 2

Función recursive para calcular el factorial

            
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)
# Nota: creación propia (Merino, A., 2025)
            
          

Como puedes ver, la sintaxis del código es un reflejo directo de la definición matemática. La condición return 1 corresponde al caso base, mientras que la línea return n * factorial(n - 1) representa el caso recursivo, llamando a la misma función para resolver una parte más pequeña del problema.