kindly explain.When n<=2 ,the answer is 5 ,but when n<=1,answer is 3. While n=n%5 so 9%5= 4. While 4 is bigger than both 1 and 2

Question

def rec(n):
n%=5
if n<=1:
return n
else:
return rec(n-1)+rec(n-2)
print(rec(9))
While 4 is bigger than both 1 and 2
Answer is 3 when it should be 5 in both cases.

Answer 1

Just put n<=2 , instead of n<=1 and output is 5.

Answer 2

This kind of number sequences is almost nonpredictable.
Reminds me to Collatz sequence.

Answer 3

When n<=2 the rec(n) function returns 1
Because 1%5 = 1 and 2%5 is 2

It all depends on the value of n%5, results will cycle from 0,1,1,2,3. You can never get 5 from the output of this function

Answer 4

what you mean n <= 2
For input 5, you get 0
For input 4 , you get 3 according to your code..! What is your doubt now?
What is purpose of program actually..?

Answer 5

You are skipping rec(2) or below
rec(4) calls rec(3) (*1) + rec(2) (*2) then
(*1) => rec(3) calls rec(2) +rec(1) =>2+1
and
(*2) => rec(2) returns 2

So finally (*1) + (*2) => 3+2=5

If it is n<=1 then recursion continues for rec(2) => rec(1) +rec(0) => 1+0=1

So rec(3) => rec(2)+rec(1)=>1+1=2
(*1) + (*2) => 2+1=3 only... .

Answer 6

Oh I understand what you mean now.
Its because the critera to exit the recusion has now changed

Again it is dependant on the n%5 value
Now when we exit recusion n can be either 1 or 2
Best thing to do here is write down each iteration for n.
So lets do that:

rec(2)
n = 2
As n <= 2 we return n which is 2
So you can see if you changed the if statement to n<=2
The rec(2) => 2 whereas when you had n<=1 it would go to rec(2-1) + rec(2-2) so you’re output if n<=1 for rec(2) is 1

You can then do this with rec(9) and compare the two
When you have if n<=1
Rec(9)
n = 4
Rec(3) + rec(2)
As we did earlier rec(2) is 1
Rec(3)
n= 3
Rec(2) + rec(1)
Rec(1) => 1
Rec(2)=> 1
So rec(9) => 1+1+1 which is 3

Now we change to if n<=2
rec(9)
n=4
rec(3) + rec(2)
Rec(2) => 2

Rec(3)
n= 3
Rec(2) + rec(1)
rec(2) => 2
Rec(1) => 1
So rec(9) => 1 +2+2 which is 5

This time you’ll find the output values cycle from 0,1,2,3,5

Answer 7

I haven't been through recursions. Beginner so... I actually got this question in challenge.