Date post: | 28-Nov-2014 |
Category: |
Documents |
Upload: | john-portella |
View: | 545 times |
Download: | 0 times |
EJERCICIOS DE RECURSION
1.- Factorial
N! = N (N-1)! Para N>1 1!=1
Ejemplo: Factorial 4 = 4*3*2*1 =24
Código en Lisp
CL-USER 1 > (defun fact (x) (if (= x 0) 1 (* x (fact (- x 1)))))
FACT
CL-USER 2 > (fact 4)
24
2.- Fibonacci
Fib(n) = Fib(n-1) + Fib(n-2) si n>1,
Fib(n)=1 si n <= 1
Ejemplo: Fibonacci 5 = 1 2 3 5 8 Se mostrara el último elemento.
Código en Lisp
CL-USER 3 > (defun fibo (x) ( if ( <= x 1) 1 (+ (fibo (- x 1)) (fibo (- x 2)))))
FIBO
CL-USER 4 > (fibo 5)
8
3.- Multiplicación recursiva
a * b = a + (a*(b-1)) si b>0,
a * b = 0 si b=0
Ejemplo: Multiplicación entera de 4 *3 = 4 + (4 * (3-1)) =…=12
Código en Lisp
CL-USER 3 : 1 > ( defun multi(a b) (if (> b 0) (+ a ( multi a (- b 1))) 0))
MULTI
CL-USER 4 : 1 > (multi 3 4)
12
4.- Exponenciación entera
𝑎𝑏 = a * 𝑎𝑏−1 si b>0
𝑎𝑏 = 1 si b=0
Ejemplo: Exponenciación 45 = 4 * 45−1 =… = 1024
Código en Lisp
CL-USER 8 : 1 > (defun expo(a b) (if (> b 0) (multi a (expo a (- b 1))) 1))
EXPO
CL-USER 9 : 1 > (expo 4 3)
64
5.- Algoritmo de Euclides
m.c.d. (a , b) = m.c.d. (b , a mod b) si b>0
m.c.d. (a , b) = a si b=0
Ejemplo: m.c.d. (57, 23) = m.c.d. (23, 1) = m.c.d. (1,0) = 1
Código en Lisp
CL-USER 3 : 1 > (defun mcd(a b) (if (> b 0) (mcd b (mod a b)) a))
MCD
CL-USER 4 : 1 > (mcd 57 23)
1
6.- Suma recursiva
Se suman todos los elementos de una lista.
Ejemplo: sumaRec (1 (3 4) 7 8 9)= 32
Código en Lisp
CL-USER 7 : 2 > (defun sumaRec3 (lista) (if(endp lista) 0 if(atom (car lista))
(+ (car lista) (sumaRec3(cdr lista)))
(+ (sumaRec3(car lista)) (sumaRec3(cdr lista))))))
SUMAREC3
CL-USER 8 : 2 > (sumaRec3 '( (1 2 4) (6 7 8) (9 9 9)))
7.- Mostrar una lista empezando pos sus extremos y
continuando adentro de ella
Ej: (mostraXt ‘( (1 2 3) 4 5 6 7 8)) => 1 3 2 8 4 7 5 6
Código en Lisp
CL-USER 9 : 3 > (defun mostraXt(lista)
(if(endp lista)
NIL
(if(atom(car lista))
(progn
(print (car lista))
(mostraXt(reverse(cdr lista)))
)
(progn
(mostraXt(car lista))
(mostraXt(reverse(cdr lista)))
)
)))
MOSTRAXT
CL-USER 10 : 3 > (mostraXt '( (1 2 3) 4 5 6 7 8))
1 3 2 8 4 7 5 6 NIL
8.- Contar todos los elementos de una lista
Código en Lisp
CL-USER 7 : 3 > (defun contar3(lista)
(if(endp lista)
0
(if(atom(car lista))
(+ 1 (contar3(cdr lista)))
(+ (contar3(car lista)) (contar3(cdr lista)))
)))
CONTAR3
CL-USER 8 : 3 > (contar3 '(1 2 4))
3
9.- Cuenta cuantos elementos de una lista son “lista”
Código en Lisp
CL-USER 17 : 5 > (defun contarLista (lista)
(if(endp lista)
0
(if (atom(car lista))
(+ 0 (contarLista(cdr lista)))
(progn
(setq x (+ 1 (contarLista(car lista))))
(+ x (contarLista(cdr lista)))))))
CONTARLISTA
CL-USER 18 : 5 > (contarLista '(1 (2 (3 4 5)) (3 (4 5 6)))) => 4
10. Primo de un numero entero positivo
Ej: (es_primo 15) NIL
(es_primo 3) T
o CL-USER 5 > (defun es_primo (numero)
(es_primo_recursivo numero 2))
ES_PRIMO
o CL-USER 6 > (defun es_primo_recursivo (numero divisor)
(if (>= divisor numero) t
(if (= 0 (mod numero divisor)) nil
(es_primo_recursivo numero (+ 1 divisor)))))
ES_PRIMO_RECURSIVO
o CL-USER 14 : 4 > (es_primo 25)
NIL
o CL-USER 15 : 4 > (es_primo 5)
T