pythonrecursionlisphyrecursionerror

Why is this quicksort overflowing?


I have the following Hy code:

(defn quicksort [lst]
   (if (< (len lst) 2)
      (return lst)
      (do 
         (setv pivot (// (len lst) 2))
         (setv (, under same over) (, [] [] []))
         (for [i lst]
            (if (< i pivot)
               (.append under i)
               (if (= i pivot)
                  (.append same i)
                  (.append over i))))
         (return (+ (quicksort under) same (quicksort over))))))

Which I roughly translated from this Python function:

def quicksort(lst: list) -> list:
    if len(lst) < 2:
        return lst
    else:
        under, same, over = [], [], []
        pivot = lst[len(lst)//2]
        for i in lst:
            if i < pivot:
                under.append(i)
            elif i == pivot:
                same.append(i)
            elif i > pivot:
                over.append(i)

        return (quicksort(under) if under else []) + same + (quicksort(over) if over else [])

However, the Hy function throws the following error: (demonstrated in the online Hy interpreter)
RecursionError: maximum recursion depth exceeded while calling a Python object Hy online interpreter Am I calling the function wrong?


Solution

  • You wrote (// (len lst) 2), but the equivalent of the corresponding Python code is (get lst (// (len lst) 2)).