Hacker News new | past | comments | ask | show | jobs | submit login

How do you solve the tree fringe problem with a for loop?



Since all recursive programs can be converted into iterative programs then you can "simply" (not always simple) convert recursive solutions like McCarthy's Lisp solution to a loop: https://dl.acm.org/action/showFmPdf?doi=10.1145%2F1045283 (page 5)

  (DE SAMEFRINGE (X Y)
         (OR (EQ X Y)
             (AND (NOT (ATOM X))
                  (NOT (ATOM Y))
                  (SAME (GOPHER X) (GOPHER Y)))))

  (DE SAME (X Y)
         (AND (EQ (CAR X) (CAR Y))
              (SAMEFRINGE (CDR X) (CDR Y))))

  (DE GOPHER (U)
         (COND ((ATOM (CAR U)) U)
               (T (GOPHER (CONS (CAAR U)
                                (CONS (CDAR U) (CDR U)))))))
Coroutines are not necessary for solving that problem (though they do offer a neat solution to it).


The results of that conversion are not fun




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: