Mastering Recursion For Beginners-(Part 2)

Hello, I’m back with another example to help you grasp recursion better.

Question: Given N, count the number of ways in which N may be expressed as the sum of 1, 3, and 4.

First and foremost, anytime we write a recursive solution, we declare our function.

NumberofWays(X) : This function returns the number of ways to represent X as the sum of 1,3, and 4.

After defining this, we try to identify a transition, as though we were going one step down the recursion tree.

Instead of N, we obtain NumberofWays(N-1), NumberofWays(N-3), and NumberofWays(N-4) (See Diagram).

All you have to do here is trust that the function will return the proper value.
So we’ll just add all of the recursive calls, N->N-1, N->N-3, and N->N-4.

We receive the value of Subbranches here (Highlighted Red).

When N==0, we have successfully expressed N into 1,3,4, thus we return 1;

When N<0 it is impossible to express, we return 0.
The code is as follows:

As you can see here there are also overlapping subproblems so we can apply dynamic programming (optimized it).

We can tell that recursion is not that hard to understand and write code.