CODEWITHSUNDEEP
recursionclojure
user227666
user227666

Reputation: 784

stuck in Clojure recursion

I am trying to write a recursive function in clojure. The function returns the greatest number of given collection. If the collection is emty then it should return nil. My code is:

(defn gum [coll]
 (if (empty? coll)
  0 
  (max (first coll)
   (gum (rest coll)))))

Expected result:

(gum [1 2 98 -3]) => 98
(gum [1 9]) => 9
(gum []) => nil

But I am getting:

(gum [1 2 98 -3]) => 98
(gum [1 9]) => 9
(gum []) => 0 (not desired result - should be `nil`)

This is because I have kept the value of (empty? coll) as 0. If I keep it as nil then (gum [1 2 98 -3]) won't work. Any suggestion as how to bring the value of (gum []) as nil and (gum [1 2 98 -3]) as 98 at the same time?

Upvotes: 0

Views: 329

Answers (5)

a.k
a.k

Reputation: 1203

This would work, using same logic as you have described, returning singleton elements instead of zero:

(defn gum [coll]
  (if (or (empty? coll) 
          (singleton? coll))
    (first coll)
    (max (first coll) (gum (rest coll)))))

with:

(defn singleton? [coll]
  (if (first coll) (empty? (rest coll)) false))

Upvotes: 0

Ivan Grishaev
Ivan Grishaev

Reputation: 1679

You should not call the same function inside because Clojure does not have tail recursion optimization (TRO). Use (recur arg1 arg2 etc) to iterate on the next step. And don't forget to add an if statement to leave the recursion.

Upvotes: 0

nha
nha

Reputation: 18005

Looks like you are trying to redefine the max function ?

Now if you are looking to understand how the max function works, it ususally a good idea to look at the source (source max) in a repl : 

(defn max
  "Returns the greatest of the nums."
  {:added "1.0"
   :inline-arities >1?
   :inline (nary-inline 'max)}
  ([x] x)
  ([x y] (. clojure.lang.Numbers (max x y)))
  ([x y & more]
   (reduce1 max (max x y) more)))

Note that (apply max []) will throw an exception rather than returning nil : ArityException Wrong number of args (0) passed to: core/max clojure.lang.AFn.throwArity (AFn.java:429)

Edit : That's why the approach to check first if we want to apply max and then (maybe) apply, as suggested by other answers :

(defn gum [coll]
  (if-let [s (seq coll)]
    (reduce max s)))

Upvotes: 0

Leonid Beschastny
Leonid Beschastny

Reputation: 51500

I think you want something like this:

(defn gum [[head & tail]]
  (if (empty? tail)
      head
      (max head (gum tail))))

I'm using destructuring here instead of first and rest, but it's the same as:

(defn gum [coll]
  (let [head (first coll)
        tail (rest coll)]
    (if (empty? tail)
        head
        (max head (gum tail)))))

But you should try to avoid constructions like (max head (gum tail)), because Clojure can't optimize it. Try using tail recursion with recur whenever possible:

(defn gum [[head & tail]]
  (if (empty? tail)
      head
      (recur (cons (max head (first tail))
                   (rest tail)))))

recur allows Clojure to use Tail Call Optimization to convert your recursive call into an iterative one, allowing it to be run in a constant stack space. It not only makes your code faster, but also protects it from stack overflow.

You should also consider using Higher Order Functions instead of recursion (as SaltyEgg suggested):

(defn gum [coll]
  (if-let [s (seq coll)]
    (reduce max s)))

In most cases they provide an easier solution. And they are pretty good optimized.

Upvotes: 3

SaltyEgg
SaltyEgg

Reputation: 1558

Try this:

(defn gum [coll]
 (if (empty? coll)
  nil 
  (reduce max coll)))

Upvotes: 1

Related Questions