Skip to content

Instantly share code, notes, and snippets.

@gorkaio
Created May 6, 2020 05:16
Show Gist options
  • Save gorkaio/1cf3c12af3ec69265a1029c7d8e1cb25 to your computer and use it in GitHub Desktop.
Save gorkaio/1cf3c12af3ec69265a1029c7d8e1cb25 to your computer and use it in GitHub Desktop.
-module(recursion).
-export([fib/1,fibTail/1,pieces/2]).
-export([fibTest/0,fibTailTest/0,piecesTest/0]).
% Fibonaaci
fib(0) -> 0;
fib(1) -> 1;
fib(N) when N>1 ->
fib(N-2) + fib(N-1).
fibTest() ->
0 = fib(0),
1 = fib(1),
1 = fib(2),
2 = fib(3),
3 = fib(4),
5 = fib(5),
8 = fib(6),
13 = fib(7),
55 = fib(10),
passed.
% Tail recursive fibonacci
fibTail(N) -> fibTail(N, 0, 1).
fibTail(0, A, _) -> A;
fibTail(N, A, B) -> fibTail(N-1, A+B, A).
fibTailTest() ->
0 = fibTail(0),
1 = fibTail(1),
1 = fibTail(2),
2 = fibTail(3),
3 = fibTail(4),
5 = fibTail(5),
8 = fibTail(6),
13 = fibTail(7),
55 = fibTail(10),
passed.
% N cuts
% Reference: http://www.jlmartin.faculty.ku.edu/MiniCollege2012/handout.pdf
pieces(_,0) -> 1;
pieces(0,_) -> 1;
pieces(N, D) when N>=0, D>=1 ->
pieces(N-1,D-1) + pieces(N-1, D).
piecesTest() ->
% Dimension 0
1 = pieces(0,0), % 0 cuts in dimension 0
1 = pieces(1,0), % 1 cuts in dimension 0 ¯\_(ツ)_/¯
% Dimension 1
1 = pieces(0,1),
2 = pieces(1,1),
3 = pieces(2,1),
% Dimension 2
1 = pieces(0,2),
2 = pieces(1,2),
4 = pieces(2,2),
7 = pieces(3,2),
11 = pieces(4,2),
% Dimension 3
1 = pieces(0,3),
2 = pieces(1,3),
4 = pieces(2,3),
8 = pieces(3,3),
15 = pieces(4,3),
% Dimension 4
1 = pieces(0,4),
2 = pieces(1,4),
4 = pieces(2,4),
8 = pieces(3,4),
16 = pieces(4,4),
31 = pieces(5,4),
passed.
@sushant12
Copy link

thank you for mentioning the link to the reference.

@elbrujohalcon
Copy link

Nice job!
Sytlistic tip: Erlang community (and tools, like eunit) tend to prefer using snake_case (i.e. pieces_test/0) over camelCase for function names, module names, and atoms in general.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment