Hey everyone,

I'm creating a series of educational [Posts + Videos] dedicated to beginners. The goal of this series is to provide free access for people around the globe to learn competitive programming by themselves.

The first topic that I am going to cover is recursion. The next topic will be dynamic programming and memoization, which I will publish next week. But you need to watch this video first in order to comprehend that one. (That video has references in this video).

If you like my work, I request you to support me so that my work can help more people. You can support by sharing the videos, liking the videos, and subscribing to the channel (which leads to more people watching the content).

You can watch the video here.

Recursion

Recursion is a way to solve a problem by solving smaller instances of the same problem. To understand what I am talking about, let's take a look at a few examples.

Factorial

Factorial is a mathematical operation denoted by an exclamation mark (!). It's applied to a non-negative integer and represents the product of all positive integers less than or equal to that number. For example, the factorial of 5 (written as 5!) is calculated as 5 × 4 × 3 × 2 × 1, which equals 120. In general, n factorial (n!) is the product of all positive integers up to n. The factorial function has applications in various mathematical calculations, permutations, and combinations.

Now, assume that we want to calculate n!. Based on the definition of n!, we can figure out that n! = n * (n — 1)!. So, if I solve this problem for n — 1, I can simply multiply it by n and have the answer for n. This is how we can solve a problem by solving a smaller instance of the same problem.

Fibonacci Sequence

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, typically starting with 0 and 1. So, the sequence begins 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on. Mathematically, it's expressed as f(n) = f(n-1) + f(n-2), with f(0) = 0 and f(1) = 1 as the starting values. This sequence appears in various natural phenomena and is known for its mathematical properties and connections to patterns in nature.

Now, if we want to calculate f(n), we can solve the problem for n-1 and n-2 and then simply add these two values. By doing this, we get f(n).

There is only one issue with solving this problem by recursion. We might have a lot of duplication of calculations here. This will lead to inefficiency in our solution. In the next video, I will talk about how we can make our solution more efficient, using dynamic programming and memoization.