This assignment requires you to write a Bash shell script "wrapper.bash" and a program in a general programming language, such as C or Python, called "fib-pict".
The argument for the fib-pict program should be an integer. Your program should compute fibonacci value for that integer both recursively and iteratively. Your output should be graphviz dot language "call graphs" representing the number of calls in computing each.
Here's example output for fib-pict 10:
digraph recursive {
label = "Recursive";
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
3 -> 2;
1 [ label = "fib(1) = 1"; ] ;
3 -> 1;
3 [ label = "fib(3) = fib(2) + fib(1)"; ] ;
4 -> 3;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
4 -> 2;
4 [ label = "fib(4) = fib(3) + fib(2)"; ] ;
5 -> 4;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
3 -> 2;
1 [ label = "fib(1) = 1"; ] ;
3 -> 1;
3 [ label = "fib(3) = fib(2) + fib(1)"; ] ;
5 -> 3;
5 [ label = "fib(5) = fib(4) + fib(3)"; ] ;
6 -> 5;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
3 -> 2;
1 [ label = "fib(1) = 1"; ] ;
3 -> 1;
3 [ label = "fib(3) = fib(2) + fib(1)"; ] ;
4 -> 3;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
4 -> 2;
4 [ label = "fib(4) = fib(3) + fib(2)"; ] ;
6 -> 4;
6 [ label = "fib(6) = fib(5) + fib(4)"; ] ;
7 -> 6;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
3 -> 2;
1 [ label = "fib(1) = 1"; ] ;
3 -> 1;
3 [ label = "fib(3) = fib(2) + fib(1)"; ] ;
4 -> 3;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
4 -> 2;
4 [ label = "fib(4) = fib(3) + fib(2)"; ] ;
5 -> 4;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
3 -> 2;
1 [ label = "fib(1) = 1"; ] ;
3 -> 1;
3 [ label = "fib(3) = fib(2) + fib(1)"; ] ;
5 -> 3;
5 [ label = "fib(5) = fib(4) + fib(3)"; ] ;
7 -> 5;
7 [ label = "fib(7) = fib(6) + fib(5)"; ] ;
8 -> 7;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
3 -> 2;
1 [ label = "fib(1) = 1"; ] ;
3 -> 1;
3 [ label = "fib(3) = fib(2) + fib(1)"; ] ;
4 -> 3;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
4 -> 2;
4 [ label = "fib(4) = fib(3) + fib(2)"; ] ;
5 -> 4;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
3 -> 2;
1 [ label = "fib(1) = 1"; ] ;
3 -> 1;
3 [ label = "fib(3) = fib(2) + fib(1)"; ] ;
5 -> 3;
5 [ label = "fib(5) = fib(4) + fib(3)"; ] ;
6 -> 5;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
3 -> 2;
1 [ label = "fib(1) = 1"; ] ;
3 -> 1;
3 [ label = "fib(3) = fib(2) + fib(1)"; ] ;
4 -> 3;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
4 -> 2;
4 [ label = "fib(4) = fib(3) + fib(2)"; ] ;
6 -> 4;
6 [ label = "fib(6) = fib(5) + fib(4)"; ] ;
8 -> 6;
8 [ label = "fib(8) = fib(7) + fib(6)"; ] ;
9 -> 8;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
3 -> 2;
1 [ label = "fib(1) = 1"; ] ;
3 -> 1;
3 [ label = "fib(3) = fib(2) + fib(1)"; ] ;
4 -> 3;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
4 -> 2;
4 [ label = "fib(4) = fib(3) + fib(2)"; ] ;
5 -> 4;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
3 -> 2;
1 [ label = "fib(1) = 1"; ] ;
3 -> 1;
3 [ label = "fib(3) = fib(2) + fib(1)"; ] ;
5 -> 3;
5 [ label = "fib(5) = fib(4) + fib(3)"; ] ;
6 -> 5;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
3 -> 2;
1 [ label = "fib(1) = 1"; ] ;
3 -> 1;
3 [ label = "fib(3) = fib(2) + fib(1)"; ] ;
4 -> 3;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
4 -> 2;
4 [ label = "fib(4) = fib(3) + fib(2)"; ] ;
6 -> 4;
6 [ label = "fib(6) = fib(5) + fib(4)"; ] ;
7 -> 6;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
3 -> 2;
1 [ label = "fib(1) = 1"; ] ;
3 -> 1;
3 [ label = "fib(3) = fib(2) + fib(1)"; ] ;
4 -> 3;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
4 -> 2;
4 [ label = "fib(4) = fib(3) + fib(2)"; ] ;
5 -> 4;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
3 -> 2;
1 [ label = "fib(1) = 1"; ] ;
3 -> 1;
3 [ label = "fib(3) = fib(2) + fib(1)"; ] ;
5 -> 3;
5 [ label = "fib(5) = fib(4) + fib(3)"; ] ;
7 -> 5;
7 [ label = "fib(7) = fib(6) + fib(5)"; ] ;
9 -> 7;
9 [ label = "fib(9) = fib(8) + fib(7)"; ] ;
10 -> 9;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
3 -> 2;
1 [ label = "fib(1) = 1"; ] ;
3 -> 1;
3 [ label = "fib(3) = fib(2) + fib(1)"; ] ;
4 -> 3;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
4 -> 2;
4 [ label = "fib(4) = fib(3) + fib(2)"; ] ;
5 -> 4;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
3 -> 2;
1 [ label = "fib(1) = 1"; ] ;
3 -> 1;
3 [ label = "fib(3) = fib(2) + fib(1)"; ] ;
5 -> 3;
5 [ label = "fib(5) = fib(4) + fib(3)"; ] ;
6 -> 5;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
3 -> 2;
1 [ label = "fib(1) = 1"; ] ;
3 -> 1;
3 [ label = "fib(3) = fib(2) + fib(1)"; ] ;
4 -> 3;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
4 -> 2;
4 [ label = "fib(4) = fib(3) + fib(2)"; ] ;
6 -> 4;
6 [ label = "fib(6) = fib(5) + fib(4)"; ] ;
7 -> 6;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
3 -> 2;
1 [ label = "fib(1) = 1"; ] ;
3 -> 1;
3 [ label = "fib(3) = fib(2) + fib(1)"; ] ;
4 -> 3;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
4 -> 2;
4 [ label = "fib(4) = fib(3) + fib(2)"; ] ;
5 -> 4;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
3 -> 2;
1 [ label = "fib(1) = 1"; ] ;
3 -> 1;
3 [ label = "fib(3) = fib(2) + fib(1)"; ] ;
5 -> 3;
5 [ label = "fib(5) = fib(4) + fib(3)"; ] ;
7 -> 5;
7 [ label = "fib(7) = fib(6) + fib(5)"; ] ;
8 -> 7;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
3 -> 2;
1 [ label = "fib(1) = 1"; ] ;
3 -> 1;
3 [ label = "fib(3) = fib(2) + fib(1)"; ] ;
4 -> 3;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
4 -> 2;
4 [ label = "fib(4) = fib(3) + fib(2)"; ] ;
5 -> 4;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
3 -> 2;
1 [ label = "fib(1) = 1"; ] ;
3 -> 1;
3 [ label = "fib(3) = fib(2) + fib(1)"; ] ;
5 -> 3;
5 [ label = "fib(5) = fib(4) + fib(3)"; ] ;
6 -> 5;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
3 -> 2;
1 [ label = "fib(1) = 1"; ] ;
3 -> 1;
3 [ label = "fib(3) = fib(2) + fib(1)"; ] ;
4 -> 3;
1 [ label = "fib(1) = 1"; ] ;
2 -> 1;
0 [ label = "fib(0) = 0"; ] ;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
4 -> 2;
4 [ label = "fib(4) = fib(3) + fib(2)"; ] ;
6 -> 4;
6 [ label = "fib(6) = fib(5) + fib(4)"; ] ;
8 -> 6;
8 [ label = "fib(8) = fib(7) + fib(6)"; ] ;
10 -> 8;
10 [ label = "fib(10) = fib(9) + fib(8)"; ] ;
}
digraph nonrecursive {
label = "Iterative";
10 [ label = "fib(10) = 0"; ] ;
10 [ label = "fib(10) = 1"; ] ;
2 -> 1;
2 -> 0;
2 [ label = "fib(2) = fib(1) + fib(0)"; ] ;
3 -> 2;
3 -> 1;
3 [ label = "fib(3) = fib(2) + fib(1)"; ] ;
4 -> 3;
4 -> 2;
4 [ label = "fib(4) = fib(3) + fib(2)"; ] ;
5 -> 4;
5 -> 3;
5 [ label = "fib(5) = fib(4) + fib(3)"; ] ;
6 -> 5;
6 -> 4;
6 [ label = "fib(6) = fib(5) + fib(4)"; ] ;
7 -> 6;
7 -> 5;
7 [ label = "fib(7) = fib(6) + fib(5)"; ] ;
8 -> 7;
8 -> 6;
8 [ label = "fib(8) = fib(7) + fib(6)"; ] ;
9 -> 8;
9 -> 7;
9 [ label = "fib(9) = fib(8) + fib(7)"; ] ;
10 -> 9;
10 -> 8;
10 [ label = "fib(10) = fib(9) + fib(8)"; ] ;
}
Your shell script wrapper.bash should run your program, pipe its output to dot, and then following the advice on this page to create a resulting PDF file with two suitable pages.
For example, try it with the value 10:
$ wrapper.bash output.pdf 10When you look at output.pdf, it should look like this.
When you run your script with the value 12:
$ wrapper.bash output2.pdf 12When you look at output2.pdf, it should look like this.