Lecture "Introduction to Computational Thinking", exercise 2
Opened this issue · 21 comments
What is the result of applying the second natural language definition of the Fibonacci function in Section "Natural languages vs programming languages" using “7” as input?
127
According to the definition, the number 7 is not less or equal to 0 and it is not equal to 1. So, we have to return the sum between 7-1=6 and 7-2=5.
Considering that the F. sequence starts from 0 and 1 and that each number is the sum of the two preceding ones, we have F2=F1+F0=1, F3=F2+F1=2, F4=F3+F2=3. Continuing in this way we will obtain the results of 6 and 5, respectively 5 and 8, so the result is 13.
Implementing the function of Fibonacci with the concept of recursion we know that if "n" is greater than 1 the function returns the sum of the same function with “n-1” as input and still the same function with “n-2” as input, so:
The result is 13 and I gained it following recursively the instructions that say that F(n) is the sum of F (n - 1) and F (n - 2), where n in this case is 7.
F(7) = F(6) + F(5)
F(6) = F(5) + F(4)
F(5) = F(4) + F(3)
F(4) = F(3) + F(2)
F(3) = F(2) + F(1)
F(2) = F(1) + F(0)
So F(2)=1; F(3)=2; F(4)=3; F(5)=5; F(6)=8; F(7)=13
The result is 13.
Being 7 (our input n) different (and bigger) than both 0 and 1, we have to sum two fibonacci functions. The first with input (n-1) and the second with input (n-2).
Therefore, we will have F(6)+F(5).
We apply the same instructions recursively and at the end we go back summing together all the results. We end up with F(7) = F(6)+F(5) = 13.
n = 7 (function input)
a = 1
b = 1
Loop while():
Loop 1:
c = a + b = 1 + 1 = 2
Is n less or equal to 3? NO
a = b = 1
b = c = 2
n = n - 1 = 6
Loop 2:
c = a + b = 1 + 2 = 3
Is n less or equal to 3? NO
a = b = 2
b = c = 3
n = n - 1 = 5
Loop 3:
c = a + b = 2 + 3 = 5
Is n less or equal to 3? NO
a = b = 3
b = c = 5
n = n - 1 = 4
Loop 4:
c = a + b = 3 + 5 = 8
Is n less or equal to 3? NO
a = b = 5
b = c = 8
n = n - 1 = 3
Loop 5:
c = a + b = 5 + 8 = 13
Is n less or equal to 3? NO
a = b = 8
b = c = 13
n = n - 1 = 2
The function recalls itself 2 times every time that we call it with an input different from either 0 or 1, in other words to find the result we have to apply the function again and again to every number starting from "n" until we get 1 or 0 as a result in every step.
At the first iteration "n" is 7, reaching the third condition of the function, we have to recall the function using 6 and 5 as input and sum the final results, 8 and 5, obtained by recalling the function two times for every intermediate result. We get 13 as the final result.
It's "13", but my first take was "11". ... a dumb error, that demonstrated me remembering a bit more math definitions would have helped avoiding me the trial/error step, since the first result I got didn't match casting out nines with the Fibonacci rules.
It happen because I misinterpreted the natural language and was applying the "(n-1)+(n-2)" rule not recursively on the sequence i.e. ignoring it was a function; so just applying the rules partially, with the assumption that "the sequence" was the one of the natural numbers.
What I got then was the sequence of odd numbers, and for "n=7": (n-1)+(n-2) = (nx2)-3 = 13-3 = 11 .
Applying those instructions, it leads us to the concept of recursion. If 'n' is less or equal 0, it returns 0 and if 'n' is equal 1, it returns 1. But taking '7' as input, it returns the sum of the function respectively with "7-1" and "7-2".
Then, according to the recursion concept, it will be:
F(0) = 0 F(1) = 1
F2 = F(1) + F(0) = 1
F3 = F(2) + F(1) = 2
F4 = F(3) + F(2) = 3
F5 = F(4) + F(3) = 5
F6 = F(5) + F(4) = 8
F7 = F(6) + F(5) = 13
The final result is 13.
Since 7>1, I have to consider the "else" statement. As I tried to show below, the correct number is 13 (i.e. the sum of the yellow cells).
after realizing that n isn't either equal or less to zero and neither equal to one, I had to obtain the sum of the F(n-1) and F(n-2), which was thirteen.
(a,b) = 1
(n) = 7
(c) = (a+b) = 2
n > 3 --> a=b; b=c
F(n) = a+b+c
F(n>3) = (a+b) + (a+b) + (a+b) + (a+b)
F(7 - 1) = 4(a+b) - 1
F(7 - 1) = 6 + 7 = 13
If we apply the concept of recursion:
n > 1 —> n = 1 | n= (n-1) + (n-2)
F2 = F(1) + F(0) = 1
F3 = F(2) + F(1) = 2
F4 = F(3) + F(2) = 3
F5 = F(4) + F(3) = 5
F6 = F(5) + F(4) = 8
F7 = F(6) + F(5) = 13
n = 7
i.e.: n > 0; n > 1; n > 2
a = 1;
b = 1;
c = a + b = 2;
n > 3
a = b = 1;
b = c = 2;
c = a + b = 3;
n = n - 1 = 6;
n > 3
a = b = 2;
b = c = 3;
c = a + b = 5;
n = n - 1 = 5;
n > 3
a = b = 3;
b = c = 5;
c = a + b = 8;
n = n - 1 = 4;
n > 3
a = b = 5;
b = c = 8;
c = a + b = 13;
n = n - 1 = 3;
n = 3
a = b = 8;
b = c = 13;
c = a + b = 21;
n = n - 1 = 2;
n < 3
Being n=7, therefore n>3. According to the instructions, one must "repeat the following
operations indefinitely until a value is returned. Set the variable
“c” as the sum of “a” plus “b”. Then assign the value of “b” to “a” and the
value of “c” to “b”, and finally decrease the value of “n” by 1
before repeating".
Knowing that
a=1
b=1
c= a+b,
the operations should unfold as follows:
(n=7) a+b=c --> 1+1=2
(n=7-1=6) 1+2=3
(n=6-1=5) 2+3=5
(n=5-1=4) 3+5=8
(n=4-1=3) 5+8=13
At this point n=3 so we can apply the following instructions: If “n” is less than or equal to “3”
then return “c”.
Therefore the result should be c=13
(I had to read the C programming language to understand that though, lol. Natural language instructions were very confusing...)
F(7)=F(6)+F(5)=8+5=13
F(6)=F(5)+F(4)=5+3=8
F(5)=F(4)+F(3)=2+3=5
F(4)=F(3)+F(2)=2+1=3
F(3)=F(2)+F(1)=1+1=2
F(2)=F(1)+F(0)=1+0=1
F(1)=1
F(0)=0
So the result is 13
The result is 13.
F(7)=F(6)+F(5)
So, if
F(0)=0
F(1)=1
F(2)=F(1)+F(0)=1+0=1
F(3)=F(2)+F(1)=1+1=2
F(4)=F(3)+F(2)=2+1=3
F(5)=F(4)+F(3)=3+2=5
F(6)=F(5)+F(4)=5+3=8
then
F(7)=8+5=13
n=7 is neither equal nor less than 1, thus pushing the computing agent to continuously call the function till 'n' becomes 0 or 1 and add all the elements to give the final result as 13. The calculation will look something like this -
The important point is that the computing agent doesn't recall the function recursively if the value of n becomes 1 or less as it makes the first condition true.
Taking into account the Natural language definition and the operations written in C for the Fibonacci function which takes as an input n=7 will have the following steps:
-7 is not less than or equal to 0 and neither is less than or equal to 2 so we will associate value “1” to two distinct variables “a” and “b” and we will enter in the while loop;
-we repeat the operations from the loop indefinitely until a value is returned;
-we set the variable “c” as the sum of “a” and “b”;
-in the end, "n" becomes "3" which is less than or equal to “3” and we return “c” whose value will be the sum between "a" = 5 and "b" = 8, ie 13.
I couldn't come up directly with the cleaner block of code before writing it down. so attaching the paper & pen scibbles.
F(0) = 0
F(1) = 1
F(2) = F(2-1) + F(2-2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(3-1) + F(3-2) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(4-1) + F(4-2) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(5-1) + F(5-2) = F(4) + F(3) = 3 + 2 = 5
F(6) = F(6-1) + F(6-2) = F(5) + F(4) = 5 + 3 = 8
F(7) = F(7-1) + F(7-2) = F(6) + F(5) = 8 + 5 = 13
I am attaching the Natural Language version to highlight the part where I faced an Issue in qoutes:
The function for calculating the nth Fibonacci number takes as input
an integer “n”. If “n” is less than or equal to 0, then 0 is returned
as a result. Otherwise, if “n” is equal to 1, then 1 is returned.
Otherwise,
> return the sum of the same function with “n-1” as input
> and still the same function with “n-2” as input.
The sentence is confusing to me.
Using the definition of the Fibonacci function, in the second natural language, that is the high-level language (in this case the C programming language) using "7" as input we have two conditions:
- if n<=0 the computer will return 0;
- if n<=2 the computer will return 1.
In this instance none of those are right, because n=7, so we have a third condition, that introduces three integers a, b, c, and assign both to a and b an initial value of 1.
Now the computer enters in the while loop, that will end only when it will meet the condition n<=3, in which case the computer will return c, that is the final result of the Fibonacci function.
The while loop starts with - c=a+b --> c= 1+1
now the computer checks the condition n<=3, but n=7 so it goes on.
If the condition is not satisfied the computer has new instructions: - a=b --> a=1
- b=c --> b=2.
- n-- (so we remove 1 to the value of n) --> n=7-1=6
Now the computer has three new values and it restarts the loop.
This time we have changed the value of a and b so - c=1+2=3
- n=6
It don't meet again the condition, so again: - a=b --> a=2
- b=c --> b=3
- n-- --> n=6-1 = 5.
The computer will repeat the loop until n=3. - a=b --> a=3
- b=c --> b=4
- n-- --> n=5-1 = 4
And again c=3+4=7; n=4. - a=b --> a=4
- b=c --> b=7
- n-- --> n=4-1 = 3
Now c=4+7=13. This time the condition is satisfied (n=3) and it end the loop by returning c.
So the result is 13.