How to resolve the algorithm Catalan numbers step by step in the PicoLisp programming language

Published on 12 May 2024 09:40 PM
#Picolisp

How to resolve the algorithm Catalan numbers step by step in the PicoLisp programming language

Table of Contents

Problem Statement

Catalan numbers are a sequence of numbers which can be defined directly: Or recursively: Or alternatively (also recursive):

Implement at least one of these algorithms and print out the first 15 Catalan numbers with each. Memoization   is not required, but may be worth the effort when using the second method above.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Catalan numbers step by step in the PicoLisp programming language

Source code in the picolisp programming language

# Factorial
(de fact (N)
   (if (=0 N)
      1
      (* N (fact (dec N))) ) )

# Directly
(de catalanDir (N)
   (/ (fact (* 2 N)) (fact (inc N)) (fact N)) )

# Recursively
(de catalanRec (N)
   (if (=0 N)
      1
      (cache '(NIL) N  # Memoize
         (sum
            '((I) (* (catalanRec I) (catalanRec (- N I 1))))
            (range 0 (dec N)) ) ) ) )

# Alternatively
(de catalanAlt (N)
   (if (=0 N)
      1
      (*/ 2 (dec (* 2 N)) (catalanAlt (dec N)) (inc N)) ) )

# Test
(for (N 0 (> 15 N) (inc N))
   (tab (2 4 8 8 8)
      N
      " => "
      (catalanDir N)
      (catalanRec N)
      (catalanAlt N) ) )

You may also check:How to resolve the algorithm Hello world/Standard error step by step in the Phix programming language
You may also check:How to resolve the algorithm Sequence of non-squares step by step in the R programming language
You may also check:How to resolve the algorithm Vampire number step by step in the Go programming language
You may also check:How to resolve the algorithm Loops/For with a specified step step by step in the PILOT programming language
You may also check:How to resolve the algorithm URL decoding step by step in the Wren programming language