Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Ejemplos de recursividad en Clojure
(ns recursividad)
;; Ejemplos de recursividad en Clojure
;; Lecturas:
;; http://biolab.uspceu.com/aotero/recursos/docencia/TEMA%207.pdf
;; https://gheize.wordpress.com/2007/09/28/recursividad/
;; http://www.grycap.upv.es/gmolto/docs/eda/EDA_Tema_5_Parte_I_gmolto.pdf
;; Tipos de recursividad lineal:
;; tr: tail recursion (recursividad final o de cola)
;; ntr: non-tail recursion (no final o no de cola)
;; Factorial
(defn trfactorial [x]
(letfn [(r [i a]
(if (> i x)
a
(r (inc i) (* a i))))]
(r 1 1)))
;; (map (fn [x] [x (trfactorial x)]) (range 6))
(defn ntrfactorial [x]
(if (zero? x)
1
(* x (ntrfactorial (dec x)))))
;; (map (fn [x] [x (ntrfactorial x)]) (range 6))
;; (defn factorial [x]
;; (reduce * (range 1 (inc x))))
;; Producto mediante sumas
(defn trproducto [x y]
(letfn [(r [i a]
(if (== i x)
a
(r (inc i) (+ a y))))]
(r 0 0)))
;; (map (fn [x] (trproducto x x)) (range 6))
(defn ntrproducto [x y]
(if (zero? x)
0
(+ y (ntrproducto (dec x) y))))
;; (map (fn [x] (ntrproducto x x)) (range 6))
;; (defn producto [x y]
;; (reduce + (repeat x y)))
;; División (entera) mediante restas
(defn trdivisión [x y]
(letfn [(r [i a]
(if (< a y)
i
(r (inc i) (- a y))))]
(r 0 x)))
;; (map (fn [x] (trdivisión x 2)) (range 6))
(defn ntrdivisión [x y]
(if (< x y)
0
(inc (ntrdivisión (- x y) y))))
;; (map (fn [x] (ntrdivisión x 2)) (range 6))
;; (defn división [x y]
;; (count (range y (inc x) y)))
;; Exponenciación mediante multiplicaciones
(defn trexponenciación [x y]
(letfn [(r [i a]
(if (== i y)
a
(r (inc i) (* a x))))]
(r 0 1)))
;; (map (fn [x] (trexponenciación x 3)) (range 6))
(defn ntrexponenciación [x y]
(if (zero? y)
1
(* x (ntrexponenciación x (dec y)))))
;; (map (fn [x] (ntrexponenciación x 3)) (range 6))
;; (defn exponenciación [x y]
;; (reduce * (repeat y x)))
;; Invertir orden de digitos de un número
(defn trnúmero-invertido [n]
(letfn [(f [x xs]
(if (zero? x)
xs
(f (quot x 10) (conj xs (rem x 10)))))
(g [xs ys b]
(if (empty? xs)
ys
(g (drop-last xs) (cons [(last xs) b] ys) (* b 10))))
(h [xs a]
(if (empty? xs)
a
(h (rest xs) (+ a (* ((first xs) 0) ((first xs) 1))))))]
(h (g (f n []) [] 1) 0)))
;; (map trnúmero-invertido (range 10 50 5))
(defn ntrnúmero-invertido [n]
(if (< n 10)
n
(+ (* (rem n 10)
(int (Math/pow 10 (int (Math/log10 n)))))
(ntrnúmero-invertido (quot n 10)))))
;; (map ntrnúmero-invertido (range 10 50 5))
;; (defn número-invertido [x]
;; (let [xxs (reduce (fn [m i]
;; (let [nx (quot (m :x) 10)
;; nxs (rem (m :x) 10)]
;; (conj m [:x nx] [:xs (cons nxs (m :xs))])))
;; {:x x :xs []}
;; (range (count (str x))))
;; xs (reverse (xxs :xs))
;; yys (reverse (map (fn [xs] (apply * (apply repeat xs)))
;; (map (fn [x y] [x y])
;; (range 0 (count (str x)))
;; (repeat (count (str x)) 10))))
;; ys (map (fn [x y] [x y]) xs yys)]
;; (apply + (map (fn [xs] (apply * xs)) ys))))
;; Sumatoria de los digitos de un número
(defn trsumatoria-digitos [n]
(letfn [(r [x a]
(if (zero? x)
a
(r (quot x 10) (+ a (rem x 10)))))]
(r n 0)))
;; (map (fn [x] (trsumatoria-digitos x)) (range 10 16))
(defn ntrsumatoria-digitos [n]
(if (== n 0)
n
(+ (rem n 10) (ntrsumatoria-digitos (quot n 10)))))
;; (map (fn [x] (ntrsumatoria-digitos x)) (range 10 16))
;; (defn sumatoria-digitos [x]
;; (let [xs (reduce (fn [m i]
;; (let [nx (quot (m :x) 10)
;; nxs (rem (m :x) 10)]
;; (conj m [:x nx] [:xs (cons nxs (m :xs))])))
;; {:x x :xs []}
;; (range (count (str x))))]
;; (reduce + (xs :xs))))
;; Multiplicación por duplicación (método ruso)
(defn trmultiplicación-por-método-ruso [x y]
(letfn [(f [n xs]
(if (zero? n)
xs
(f (quot n 2) (conj xs (quot n 2)))))
(g [n xs i f]
(if (== i f)
xs
(g (* 2 n) (conj xs (* 2 n)) (inc i) f)))
(h [xs ys zs]
(if (or (empty? xs) (empty? ys))
zs
(h (rest xs) (rest ys) (conj zs [(first xs) (first ys)]))))
(i [xs ys]
(if (empty? xs)
ys
(i (rest xs) (if (odd? ((first xs) 0))
(conj ys ((first xs) 1))
ys))))
(j [xs a]
(if (empty? xs)
a
(j (rest xs) (+ a (first xs)))))]
(let [as (f x [x])
bs (g y [y] 1 (count as))
abs (h as bs [])
bsf (i abs [])]
(j bsf 0))))
;; (map (fn [x] (trmultiplicación-por-método-ruso x 2)) (range 5 11))
(defn ntrmultiplicación-por-método-ruso [x y]
(cond
(== x 1) y
(not (zero? (rem x 2))) (+ y (ntrmultiplicación-por-método-ruso (quot x 2) (* 2 y)))
:else (ntrmultiplicación-por-método-ruso (quot x 2) (* 2 y))))
;; (map (fn [x] (ntrmultiplicación-por-método-ruso x 2)) (range 5 11))
;; Sumar los números enteros encontrados en un vector
(defn trsumatoria-vector [xs]
(letfn [(r [ys a]
(if (empty? ys)
a
(r (rest ys) (+ a (first ys)))))]
(r xs 0)))
;; (map trsumatoria-vector [[10 20 30] [] [40 50]])
(defn ntrsumatoria-vector [xs]
(if (empty? xs)
0
(+ (first xs) (ntrsumatoria-vector (rest xs)))))
;; (map ntrsumatoria-vector [[10 20 30] [] [40 50]])
;; (defn sumatoria-vector [xs]
;; (reduce + xs))
;; Multiplicar los números enteros encontrados en un vector
(defn trproducto-vector [xs]
(letfn [(r [ys a]
(if (empty? ys)
a
(r (rest ys) (* a (first ys)))))]
(r xs 1)))
;; (map trproducto-vector [[10 20 30] [] [40 50]])
(defn ntrproducto-vector [xs]
(if (empty? xs)
1
(* (first xs) (ntrproducto-vector (rest xs)))))
;; (map ntrproducto-vector [[10 20 30] [] [40 50]])
;; (defn producto-vector [xs]
;; (reduce * xs))
;; Máximo común divisor de dos números enteros
(defn ntrmcd1 [x y]
(if (zero? y)
x
(ntrmcd1 y (rem x y))))
;;;; Por el método de Euclides
(defn ntrmcd2 [x y]
(let [mayor (if (> x y) x y)
menor (if (< x y) x y)
resto (rem mayor menor)]
(if (zero? resto)
menor
(ntrmcd2 menor resto ))))
;; (map (fn [par]
;; [(lrmcd1 (par 0) (par 1)) (ntrmcd2 (par 0) (par 1))])
;; [[5 15] [6 16] [7 17] [8 18] [9 19] [10 20]])
;; El número mayor de un vector de números
;;;; Si el vector dado está vácio regresa un vector vácio,
;;;; en caso contrario un vector con el número mayor.
(defn trmayor-vector [xs]
(letfn [(r [ys zs]
(if (empty? ys)
zs
(r (rest ys) (cond
(empty? zs) [(first ys)]
(> (first ys) (first zs)) [(first ys)]
:else zs))))]
(r xs [])))
;; (map trmayor-vector [[10 20 30] [] [30 20 10]])
(defn ntrmayor-vector [xs]
(if (empty? xs)
[]
(let [resultado-siguiente (ntrmayor-vector (rest xs))]
(cond
(empty? resultado-siguiente) [(first xs)]
(> (first xs) (first resultado-siguiente)) [(first xs)]
:else resultado-siguiente))))
;; (map ntrmayor-vector [[10 20 30] [] [30 20 10]])
;; (defn mayor-vector [xs]
;; (if (empty? xs)
;; []
;; [(apply max xs)]))
;; Sumatoria de las sumatorias de vectores anidados
;; o bien, la sumatoria de una matriz de números.
(defn trsumatoria-vector-vectores [xss]
(letfn [(r1 [ys a]
(if (empty? ys)
a
(r1 (rest ys) (+ a (first ys)))))
(r2 [yss a]
(if (empty? yss)
a
(r2 (rest yss) (r1 (first yss) a))))]
(r2 xss 0)))
;; (map (fn [xs] (trsumatoria-vector-vectores xs))
;; [[[10 20] [] [30]]
;; [[] [10 20] [30]]
;; [[] [30] [10 20]]])
(defn ntrsumatoria-vector-vectores [xss]
(cond
(empty? xss) 0
(number? (first xss)) (+ (first xss) (ntrsumatoria-vector-vectores (rest xss)))
:else (+ (ntrsumatoria-vector-vectores (first xss))
(ntrsumatoria-vector-vectores (rest xss)))))
;; (map (fn [xs] (ntrsumatoria-vector-vectores xs))
;; [[[10 20] [] [30]]
;; [[] [10 20] [30]]
;; [[] [30] [10 20]]])
;; (defn sumatoria-vector-vectores [xss]
;; (reduce + (map (fn [xs] (apply + xs)) xss)))
;; Cadena de carácteres invertida
(defn trcadena-de-carácteres-invertida [xs]
(letfn [(r [ys zs]
(if (empty? ys)
zs
(r (rest ys) (str (first ys) zs))))]
(r xs "")))
;; (map trcadena-de-carácteres-invertida ["hola" " " "mundo" "!"])
(defn ntrcadena-de-carácteres-invertida [xs]
(if (empty? xs)
""
(str (first xs) (ntrcadena-de-carácteres-invertida (rest xs)))))
;; (map ntrcadena-de-carácteres-invertida ["hola" " " "mundo" "!"])
;; (defn cadena-de-carácteres-invertida [s]
;; (apply str (reverse s)))
;; Número de letras vocales existentes en una cadena de carácteres
(defn trtotal-letras-vocales [xs]
(letfn [(r [ys a]
(if (empty? ys)
a
(r (rest ys) (+ a (case (first ys)
\a 1
\e 1
\i 1
\o 1
\u 1
0)))))]
(r xs 0)))
;; (map trtotal-letras-vocales ["hola" "mundo" "!"])
(defn ntrtotal-letras-vocales [xs]
(if (empty? xs)
0
(+ (case (first xs)
\a 1
\e 1
\i 1
\o 1
\u 1
0) (ntrtotal-letras-vocales (rest xs)))))
;; (map ntrtotal-letras-vocales ["hola" "mundo" "!"])
;; (defn total-letras-vocales [s]
;; (reduce (fn [a c] (+ a (case c
;; \a 1
;; \e 1
;; \i 1
;; \o 1
;; \u 1
;; 0)))
;; 0
;; s))
;; Insertar un número de acuerdo a su orden en un vector de
;; números ordenados de menor a mayor.
(defn trinsertar-número-vector [x xs]
(letfn [(r [ys zs]
(cond
(and (empty? ys) (empty? zs)) (conj zs x)
(and (empty? ys) (< (last zs) x)) (conj zs x)
(empty? ys) zs
:else (r (rest ys)
(cond
(and (not (empty? zs)) (< (last zs) x) (> (first ys) x))
(conj zs x (first ys))
(and (empty? zs) (> (first ys) x))
(conj zs x (first ys))
(and (empty? ys) (== (count zs) (count xs)))
(conj zs (first ys) x)
:else
(conj zs (first ys))))))]
(r xs [])))
;; (map (fn [xs] (trinsertar-número-vector 5 xs))
;; [[]
;; [4]
;; [6]
;; [3 4]
;; [6 7]
;; [2 3 4 6]
;; [4 6 7 8]
;; [3 4 6 7]
;; [1 2 3 4 6 7 8 9]
;; [1 2 3]
;; [7 8 9]])
;; (defn insertar-número-vector [x xs]
;; (let [menores (filter (fn [n] (< n x)) xs)
;; mayores (filter (fn [n] (> n x)) xs)]
;; (vec (concat menores [x] mayores))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Recursividad mutua
;; https://es.wikipedia.org/wiki/Recursi%C3%B3n_mutua
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defn es-par? [número]
(letfn [(par? [número]
(if (zero? número)
true
(impar? (dec número))))
(impar? [número]
(if (zero? número)
false
(par? (dec número))))]
(par? número)))
;; (map es-par? (range 3 9))
(defn es-impar? [número]
(letfn [(par? [número]
(if (zero? número)
true
(impar? (dec número))))
(impar? [número]
(if (zero? número)
false
(par? (dec número))))]
(impar? número)))
;; (map es-impar? (range 3 9))
(defn es-positivo? [número]
(letfn [(positivo? [número]
(if (< número 0)
false
(negativo? número)))
(negativo? [número]
(if (> número 0)
true
(positivo? número)))]
(positivo? número)))
;; (map es-positivo? (range -5 6 2))
(defn es-negativo? [número]
(letfn [(positivo? [número]
(if (< número 0)
true
(negativo? número)))
(negativo? [número]
(if (> número 0)
false
(positivo? número)))]
(negativo? número)))
;; (map es-negativo? (range -5 6 2))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.