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 in the code here, there are overlapping sub-problems, so we can apply dynamic programming (optimising it) to solve this problem. The main idea is to store the solutions to sub-problems and reuse them later.

This demonstrates that recursion is not that hard to understand and write code for.