Lecture "Introduction to Computational Thinking", exercise 2
Opened this issue · 10 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?
It will be 13, resulting from recursively adding the two previous numbers in the sequence. (For natural numbers 1 to 7, the result will respectively be: 1, 1, 2, 3, 5, 8, 13)
I agree with Nooshin's answer, but I didn't understand why we need to decrease n in each cycle rather than increase it
@arcangelo7 I believe that in this solution, n is acting as a sort of counter. We know that we want the 7th number in the sequence, and we know that the first two numbers in the sequence are 1 and 1. So we start counting down from 7, adding the two previous numbers of the sequence in each iteration.
The process is as follows: When n = 7, we are calculating 1 + 1, which is the 3rd number in the sequence. We decrement n (n = 6), and we calculate the 4th number (1 + 2). If we continue like this, when n reaches 3, we have the 7th number in the sequence, so we return the amount we have calculated in the final step (5 + 8).
If I need to find the value of the function when the input is n=7, I need to apply the function to the results of the function F=F(7-1)+F(7-2). Going backward, since we know F=F1 and F=F0 are equal to 1 and 0 respectively, we can find F2=1 and all the following values, until F7 which is equal to F7=F6+F5 which again is equal to F7=8+5.
I tried to solve this exercise using Python:
def fib (n):
if n <= 0:
return 0
elif n == 1:
return 1
else:
return (fib(n-1)+fib(n-2))
fib(7)
13
@arcangelo7 I believe that in this solution, n is acting as a sort of counter. We know that we want the 7th number in the sequence, and we know that the first two numbers in the sequence are 1 and 1. So we start counting down from 7, adding the two previous numbers of the sequence in each iteration.
The process is as follows: When n = 7, we are calculating 1 + 1, which is the 3rd number in the sequence. We decrement n (n = 6), and we calculate the 4th number (1 + 2). If we continue like this, when n reaches 3, we have the 7th number in the sequence, so we return the amount we have calculated in the final step (5 + 8).
@NoonShin, I've been thinking about it for a long time, but I finally understood. This is really counter-intuitive, but brilliant and beautiful. Thanks!
I rewrite in mathematical language the definition given in natural language:
The function for calculating the nth Fibonacci number takes as input an integer “n”.
F=F(n)
If “n” is less than or equal to 0, then 0 is returned as a result.
F=F(n<=0) = 0
Otherwise, if “n” is equal to 1, then 1 is returned.
F=F(n=1) = 1
Otherwise, return the sum of the same function with “n-1” as input and still the same function with “n-2” as input.
F=F(n-1)+F(n-2)
If the input is 7, F=F(7) and n=7
F=F(7-1)+F(7-2)=F(6)+F(5)
I need to find F6 and F5
F=F(6)=F(6-1)+F(6-2) = F=F(5)+F(4)
F=F(5)=F(5-1)+F(5-2) = F=F(4)+F(3)
I need to find F(4) and F(3)
F=F(4)=F(4-1)+F(4-2)=F(3)+F(2)
F=F(3)=F(3-1)+F(3-2)=F(2)+F(1)
I know that F(1)=1
I need to find F(2)
F=F(2)=F(2-1)+F(2-2)=F(1)+F(0)
I know that F(1)=1 and F(0)=0
So, I can rewrite it:
F=F(2)=F(1)+F(0)=1+0=1 F(2)=1
F=F(3)=F(2)+F(1)=1+1=2 F(3)=2
F=F(4)=F(3)+F(2)=2+1=3 F(4)=3
F=F(5)=F(4)+F(3)=3+2=5 F(5)=5
F=F(6)=F(5)+F(4)=5+3=8
And then, finally, F(7)
F=F(7)=F(6)+F(5)=8+5=13
I went through the exact same process as @elisasilvad
I agree with the previous answers. Anyway, since my reminiscences of maths are clearly not sufficient to complete the exercise with either an appropriate language or method, I just tried to put down schematically my mental process:
Input: 7
- n is neither less nor equal to 0 (can’t return 0 as a result)
- n is neither less nor equal to 2 (can’t return 1 as a result)
- Since the previous conditions couldn’t be applied with 7 as an input…
--> a= 1; b=1
-->c = a + b - n is neither less nor equal to 3 (can’t return 2 = c as a result)
- Since the previous conditions couldn’t be applied with 7 as an input…
--> a = (previous value of) b = 1
--> b = (previous value of) c = 2
--> n = input – 1 = 7 – 1 = 6
--> c= (a =1)+(b= 2) = 3
--> n= 6 --> (neither equal nor less than 3) -->a= 2; b =3 ; c= 5 --> n = n-1 = 5
-->n=5 -->(“) --> a=3; b=5; c=8 --> n= n-1 = 4
-->n=4 -->(“) --> a=5; b= 8; c= 13 --> n= n-1= 3 - n is now equal to 3 --> so I return c, whose value is now 13.
The process you are following works, but it seems to be related more to the first definition in natural language of the Fibonacci algorithm instead of the second definition. I see similar issues also in @NoonShin approach, as also reprised by @arcangelo7.
However, the fact you have focussed on the first definition in natural language instead of the second one could be due to my mistake in the text of the exercise I've provided, and that have corrected a few days ago mentioning explicitly the second natural language definition. Apologies for any misunderstanding.