If you're seeing this message, it means we're having trouble loading external resources on our website.

Si estás detrás de un filtro de páginas web, por favor asegúrate de que los dominios *.kastatic.org y *.kasandbox.org estén desbloqueados.

Contenido principal

Factorial recursivo

Para valores positivos de n, vamos a escribir n, ! como lo hicimos antes, como un producto de números empezando en n y bajando hasta llegar a 1: n, ! = n, dot, left parenthesis, n, minus, 1, right parenthesis, \@cdots, 2, dot, 1. Pero observa que left parenthesis, n, minus, 1, right parenthesis, \@cdots, 2, dot, 1 es otra manera de escribir left parenthesis, n, minus, 1, right parenthesis, !, así que podemos decir que n, !, equals, n, dot, left parenthesis, n, minus, 1, right parenthesis, !. ¿Viste lo que acabamos de hacer? Escribimos n, ! como un producto en el cual uno de los factores es left parenthesis, n, minus, 1, right parenthesis, !. Te dijimos que podemos calcular n, ! calculando left parenthesis, n, minus, 1, right parenthesis, ! y después multplicando el resultado de calcular left parenthesis, n, minus, 1, right parenthesis, ! por n. Puedes calcular la función factorial de n al calcular primero la función factorial de n, minus, 1. Decimos que calcular left parenthesis, n, minus, 1, right parenthesis, ! es un subproblema que resolvemos para calcular n!.
Veamos un ejemplo: calcular 5!.
  • Puedes calcular 5! como 5, dot, 4, !.
  • Ahora necesitas resolver el subproblema de calcular 4!, el cual puedes calcular como 4, dot, 3!.
  • Ahora necesitas resolver el subproblema de calcular 3!, el cual es 3, dot, 2, !.
  • Ahora 2!, el cual es 2, dot, 1, !.
  • Ahora necesitas calcular 1!. Podrías decir que 1! equivale a 1, porque es el producto de todos los enteros desde 1 hasta 1. O puedes aplicar la fórmula de 1, !, equals, 1, dot, 0, !. Vamos a hacerlo aplicando la fórmula.
  • Definimos 0! igual a 1.
  • Ahora puedes calcular 1, !, equals, 1, dot, 0, !, equals, 1.
  • Habiendo calculado 1, !, equals, 1, puedes calcular 2, !, equals, 2, dot, 1, !, equals, 2.
  • Habiendo calculado 2, !, equals, 2, puedes calcular 3, !, equals, 3, dot, 2, !, equals, 6.
  • Habiendo calculado 3, !, equals, 6, puedes calcular 4, !, equals, 4, dot, 3, !, equals, 24.
  • Por último, habiendo calculado 4, !, equals, 24, puedes terminar de calcular 5, !, equals, 5, dot, 4, !, equals, 120.
Así que ahora tenemos otra manera de pensar acerca de cómo calcular el valor de n, ! para todos los enteros no negativos n:
  • Si n, equals, 0, entonces declara que n, !, equals, 1.
  • De lo contrario, n debe ser positivo. Resuelve el subproblema de calcular left parenthesis, n, minus, 1, right parenthesis, !, multiplica este resultado por n y declara que n, ! es igual al resultado de este producto.
Cuando estamos calculando n, ! de esta manera, llamamos al primer caso, en donde inmediatamente sabemos la respuesta, el caso base, y llamamos al segundo caso, en donde tenemos que calcular la misma función pero en un valor diferente, el caso recursivo.

Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.

¿Quieres unirte a la conversación?

¿Sabes inglés? Haz clic aquí para ver más discusiones en el sitio en inglés de Khan Academy.