Last active
February 28, 2017 01:19
-
-
Save jason-carter/58645f3e54901f34802ec9f6fd182e81 to your computer and use it in GitHub Desktop.
FutureLearn Functional Programming In Erlang 1.19: Recursion
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
-module(recursion). | |
-export([fib/1, pieces/1, cake/2, factorial/1, binomialcoefficient/2]). | |
% Give a recursive definition of the function fib/1 computing the | |
% Fibonacci numbers... | |
fib(0) -> 0; | |
fib(1) -> 1; | |
fib(X) -> (fib (X-1)) + (fib (X-2)). | |
% and give a step-by-step evaluation of fib(4). | |
% fib(4) | |
% fib(3) + fib(2) | |
% fib(2) + fib(1) + fib(1) + fib(0) | |
% fib(1) + 1 + 1 + 0 | |
% 1 + 1 + 1 + 0 | |
% 3 | |
% According to wikipedia: | |
% | |
% https://en.wikipedia.org/wiki/Lazy_caterer%27s_sequence | |
% | |
% The proof section contains the following: | |
% | |
% Since f(0)=1, because there is one piece before any cuts are | |
% made, this can be rewritten as f(n)=1+(1+2+3+...+n). | |
% | |
% Which looks like a formula we can recurse :-) | |
pieces(0) -> 1; | |
pieces(Cuts) -> pieces(Cuts-1) + Cuts. | |
% Again, 3D version of this is the cake number, according to Wikipedia: | |
% | |
% https://en.wikipedia.org/wiki/Cake_number | |
% | |
factorial(0) -> 1; | |
factorial(1) -> 1; | |
factorial(N) when N < 0 -> 1; | |
factorial(N) -> factorial(N-1) * N. | |
binomialcoefficient(N,K) -> factorial(N) / (factorial(K) * factorial(N - K)). | |
cake(N,0) -> binomialcoefficient(N,0); | |
cake(N,K) -> cake(N, K-1) + binomialcoefficient(N,K). | |
% I think K is the dimension, and N is the number of cuts | |
% so cake(5,3) means 5 cuts in 3 dimensions (=26). |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Thanks for posting your work, Jason. Your style is spare and yet readable. I like it a lot.