educative.io

Educative

A Complex Example

def rec_count(number):

print(number)

# Base case

if number == 0:

    return 0

rec_count(number - 1)  # A recursive call with a different argument

print(number)

rec_count(5)

def fib(n):

# The base cases

if n <= 1:  # First number in the sequence

    return 0

elif n == 2:  # Second number in the sequence

    return 1

else:

    # Recursive call

    return fib(n - 1) + fib(n - 2)

print(fib(6))

I didnot understand this topic please explain sir

Hi! These functions are both recursive, meaning they call themselves.

The first function, rec_count, takes an integer as input and decrements it until it becomes 0. If we take 5 as an example input, the function first prints out 5 as it is, then calls itself again with 4 as an input (i.e. number - 1). This function call now prints out 4 and calls itself again, this time with 3 as an input. This continues until it hits 0, where the base case becomes true, after which it returns into the previous function call. Every function call returns in a reverse fashion, with the latest call returning first, all the way up to the very first call with input 5.

The second function returns numbers in the Fibonacci series. The Fibonacci series is a sequence of numbers where each number is the sum of the two numbers before it (0, 1, 1, 2, 3, 5, 8…). The first two numbers are 0 and 1 respectively, and these form the base case for our function. If we take 3 as an input to our function (i.e. the third number in the Fibonacci series), the fib function will make calls to fib(2) and fib(1). Both these calls are handled in the base cases, returning 1 and 0 respectively. These two are then added and returned, giving 1 as the final answer.

i tried fib(4) and tried to make sense of the answer through the output as shown below:
def fib(n):
# The base cases
if n <= 1: # First number in the sequence
return 0
elif n == 2: # Second number in the sequence
return 1
else:
# Recursive call
print(‘n=’, n)
print(‘equation=’, fib(n - 1) + fib(n - 2))
return fib(n - 1) + fib(n - 2)

print(fib(4))

The output shows:
n= 4
n= 3
equation= 1
equation= 2
n= 3
equation= 1
2

i get that the first step should be fib(3) - fib(2), returning 3 and 1 respectively. Adding them becomes 4 again. So i thought maybe fib(n - 2) portion is dropped because it has broke out of the recursive. Therefore n = 3 is carried through the next cycle, make it fib(3-1) returning 1. Therefore 1+1 = 2 (final answer).

But i think my understanding is wrong because it wouldn’t work for n=5 with this way of thinking.