Automatas

Función es recursiva

Una función es recursiva si en su definición tiene al menos un llamado a sí misma. Un tipo de datos es recursivo si está definido en términos de sí mismo.
Ejemplo:
Elconjunto de potencias de 2: 1 2 4 8 16 32 64... podemos definirlas como p(0) = 1 y p(n+1) = p(n)*2

Ejemplos de funciones recursivas

λ Potencias de dos
λ Factorial
λ Serie de Fibonacci
λTriangulo de Sierpinski

Potencias de dos

λ Definición:
[pic]
λ En scheme:

[pic]
Factorial

λ Definición:
[pic]
λ En scheme:

[pic]

Fibonacci

λ Definición

[pic]
λ En scheme:[pic]

Triangulo

[pic]

Todas las funciones recursivas tienen las siguientes características:
1. tienen uno o más casos base: criterio de parada.
2. tienen un caso recursivo: se llama ala misma función
Los ejemplos anteriores tienen caso base y caso Recursivo?
- Potencias de 2
- Factorial
- Fibonacci
- Triangulo

Cómo todas las funciones recursivas tienen la misma estructura,el cuerpo de la función (en scheme) será un condicional.

λ ¿Cuantas condiciones debo poner?
Una por cada caso base
Una por el caso recursivo
λ Se debe probar primero el caso base, porquesi este tiene errores (lógicos) es posible que la función se quede haciendo un ciclo infinito.

Funciones Recursivas Primitivas

Algunas funciones recursivas primitivas:

• Funcionesconstantes

• Correspondencia entre cualquier tupla de 5 elementos y el valor 3

• Correspondencia entre cualquier tupla de 3 elementos y el valor 5

• Función predecesor

•Función predecesor

• Función equal:

• Función not:

• Funciones tabulares:
|Entrada |Salida |
|0 |3 |
|4 |5 ||otros |2 |

Funciones primitivas recursivas

La clase de funciones primitivas recursivas es la clase mas chica de funciones I que contiene a las funciones iniciales:...