Recursion is an important topic where you have a base case and a recursive formula. But the main reason for recursions being difficult is that one has to figure out the recursive formula which is not always intuitive or easy. So today, I want to share the story when for the first time I was able to guess the recursive formula.

You can find the problem description here https://codeforces.com/problemset/problem/166/E . You are given a Tetrahedron with its 4 nodes denoted by A, B, C, D. You start your journey from D. In each step, you can move to any of the remaining 3 vertices (so if you are at A, you can go to B,C or D; if you are at B, you can go to A, C, or D etc). How many ways can you go to D with a path of length n?

So, let's assume at nth step, you finish your journey at D, and it took f(n,D) steps. So on the previous step, you were either at A, OR B, OR C with path length n-1.

Therefore,

f(n,D) = f(n-1, A)+f(n-1, B)+f(n-1, C)

It took me a lot of time to figure this out. Okay, now we need the base case. If n == 0, We have f(0,D) = 1 (because you always start from D, you take 0 steps to reach D, so the total number of ways is 1). if n ==1, we get f(1,D) = 0 because you start from D, you take a path of length 1, so you are at A, B or C, and you cannot go to D. So you need a path of minimum length 2 (D-A-D, D-B-D, D-C-D) in order to go from D to D.

Therefore, our base cases are:

f(0,D) = 1,  f(0,X) = 0 (X = A,B,C), f(1, D) = 0

That is how I found the recursive formula. Next, to solve the problem, you can take a plenty of approaches. For convenience, replace A,B,C,D with 0,1,2,3 (you can then use a for loop to simplify your code).

If you draw a ternary tree figure using the recursive formula, you will find that same value is calculated multiple times. Therefore, we have overlapping sub-problems, and so you can also use a dynamic programming approach.

If you print the first few values (i.e , for n = 1,2,3,4,... ), you can find a pattern in the output numbers. Using that pattern, you can derive a formula to find the nth term of the series. Also, I am quite sure there are other solutions to this problem.