Ejemplos de recursividad en Clojure

recursividad.clj

(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))