Recursion, how it works?

Question

https://www.sololearn.com/post/910025/?ref=app

Answer 1

First of all, the program seems to be deliberately designed to be confusing. It is also wrong. fib(0) should be 0. The else block is not needed and it can even be simplified and corrected as:

def fib(x):
return fib(x-1) + fib(x-2) if x > 1 else x

So let me explain the program now.

A Fibonacci sequence is an integer sequence where the first two terms are 0 and 1. Consequent terms are calculated by adding the last two terms.

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

The nth term, fib(n) is defined as follows

if n = 0, fib(n) is 0
if n = 1, fib(n) is 1
else, fib(n) is fib(n-2) + fib(n-1)

To make it easier to implement we can say,

if n > 1, fib(n) is fib(n-2) + fib(n-1) else fib(n) is n.

Hence my code:

def fib(n):
return fib(n-1) + fib(n-2) if n > 1 else n

Note that fib is a function that calls itself. Such a function is called recursive function.

Note that fib(n) will always return the same result for the same value of n and fib(n) does not cause side effects. Therefore, fib is a pure function.

Answer 2

follow this video, it's perfectly explained there:
https://www.youtube.com/watch?v=dxyYP3BSdcQ

Answer 3

so let's do that with a given n :
fib(4) - > fib(3) + fib(2) - > (fib(2)+fib(0)) + (fib(1)+fib(0)) == 5
with fib(2)== 2 and fib(1)== 1 and fib(0)==1.
thanks Ore it's clear now.

Answer 4

Sp3kTr0👻 Yes. You got it. I am happy that my answer helped.

Answer 5

RKK I want only the explanation of that example.

Answer 6

RKK thanks anyway bro.