Day 4 (Recursion questions)

It is day 4 of my 100 days DSA challenge and today I did two questions on the topic as follows:

1.) Fibonacci series:

The Fibonacci series is a sequence of numbers where each number is the sum of the two preceding ones. For instance, it starts with 0 and 1, and then each subsequent number is the sum of the two before it. Like this: 0, 1, 1, 2, 3, 5, 8, 13, and so on.

To find a particular number in the sequence, I wrote a code using a simple rule. For instance, if you want the 5th number in the sequence, it would be 3. Here is the code I used:

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

2.) Counting the ways to reach the nth stair:

For this problem, I worked on finding the number of different ways one can reach the nth stair. The rule is simple: you can either move up 1 stair or 2 stairs at a time.

The code I wrote to solve this problem is:

def count_ways_to_reach_stair(n):
    if n < 0:
        return 0
    if n == 0:
        return 1
    return count_ways_to_reach_stair(n - 1) + count_ways_to_reach_stair(n - 2)

These are basic problems solved using simple rules in programming to find the nth number in a Fibonacci sequence and count the ways to reach a particular stair.