La recursividad y la inducción pertenecen a la rama de las Matemáticas, estos términos se usan indistintamente. Pero hay algunas diferencias entre estos términos.
La recursividad es un proceso en el que una función se repite una y otra vez hasta que se satisface alguna función base. Se repite y utiliza sus valores anteriores para formar una secuencia. El procedimiento aplica una cierta relación a la función dada una y otra vez hasta que se cumple alguna condición básica. Consta de dos componentes:
1) Condición base : para detener una función recursiva, se necesita una condición. Esto se conoce como una condición base. La condición base es muy importante. Si la condición base no se encuentra en el código, la función puede entrar en un bucle infinito.
2) Paso recursivo : Divide un gran problema en pequeñas instancias que son resueltas por la función recursiva y luego recombinadas en los resultados.
Sea a 1 , a 2 …… a n ,una sucesión. La fórmula recursiva viene dada por:
an = an-1 + a1
Ejemplo : La definición de la serie de Fibonacci es recursiva. A menudo viene dada por la relación:
F N = FN-1 + FN-2 where F0 = 0
¿Cómo realizar la recursividad?
Supongamos que la función dada es
Tn = Tn-1 + C
Primero usamos la condición base dada. Denotemos la condición base por T 0 , n= 2. encontraremos T 1 . C es la constante.
Tn = Tn-1 + C //n=2
T2 = T2-1 + C
T1 = T1-1 + C
= T0 + C + C // Base condition achieved, recursion terminates.
Inducción
La inducción es la rama de las matemáticas que se utiliza para demostrar un resultado, una fórmula, un enunciado o un teorema. Se utiliza para establecer la validez de un teorema o resultado. Tiene dos reglas de funcionamiento:
1) Paso base : nos ayuda a probar que la declaración dada es verdadera para algún valor inicial.
2) Paso inductivo : establece que si el teorema es verdadero para el término n, entonces la declaración es verdadera para el término (n + 1).
Ejemplo : La afirmación es que el n-ésimo número de Fibonacci es como máximo 2 n .
¿Cómo probar una afirmación por inducción?
Paso 1 : probar o verificar que la afirmación es verdadera para n=1
Paso 2 : Suponga que la afirmación es verdadera para n=k
Paso 3 : Verifique que la afirmación sea verdadera para n=k+1, luego se puede concluir que la afirmación es verdadera para n.
Diferencia entre recursividad e inducción :
| S. No. | recursividad | Inducción |
|---|---|---|
| 1. | La recursividad es el proceso en el que se llama a una función una y otra vez hasta que se cumple alguna condición básica. | La inducción es la forma de probar un enunciado matemático. |
| 2. | Es la forma de definir de manera repetitiva. | Es la forma de probar. |
| 3. | Comienza desde el término n hasta el caso base. | Comienza desde el término inicial hasta el (n+1)ésimo. |
| 4. |
Tiene dos componentes:
|
Tiene dos pasos:
|
| 5. | Retrocedemos en cada paso para reemplazar los valores anteriores con las respuestas usando la función. | Solo probamos que la afirmación es verdadera para n=1. Entonces asumimos que n = k es cierto. Entonces probamos para n=k+1. |
| 6. | No se hacen suposiciones. | La suposición se hace para n= k |
| 7. | La función recursiva siempre se llama para encontrar términos sucesivos. | Aquí se prueban enunciados o teoremas y no se encuentran términos. |
| 8. | Puede conducir al infinito si no se da ninguna condición base. | No existe el concepto de infinito. |