fork/numbat

git clone https://git.julia.blue/fork/numbat

David PeterAdd two more recursive examplesd94a3e3

v1.6.0
923 B26 linesraw
1# Binomial coefficient using Pascal's rule
2#
3# Adapted from the Python version here:
4# https://en.wikipedia.org/wiki/Binomial_coefficient
5#
6# TODO: This could really benefit from logical and/or operators
7
8fn binomial_coefficient(n: Scalar, k: Scalar) -> Scalar =
9    if k < 0
10        then 0
11        else if k > n
12            then 0
13            else if k > n - k # Take advantage of symmetry
14                then binomial_coefficient(n, n - k)
15                else if k == 0
16                    then 1
17                    else if n <= 1
18                        then 1
19                        else binomial_coefficient(n - 1, k) + binomial_coefficient(n - 1, k - 1)
20
21assert_eq(binomial_coefficient(10, 0), 1)
22assert_eq(binomial_coefficient(10, 1), 10)
23assert_eq(binomial_coefficient(10, 2), 45)
24assert_eq(binomial_coefficient(10, 6), 210)
25assert_eq(binomial_coefficient(10, 9), 10)
26assert_eq(binomial_coefficient(10, 10), 1)