Direct Recursion

Good day software developers and software engineers. The forecast for today Thursday in the Twin Cities of Minneapolis and St. Paul calls for rain and thunderstorms. As usual the forecast changed at least a couple times in the past few days. Today the storm is forecasted for the evening hours. So far I have not heard thunder. I do not like to have my computers on during a thunderstorm. A couple times I have lost some equipment.

I was looking at a problem that required recursion. As always I like to read and experiment before diving into a solution. This time was no different.

On YouTube I found the video Recursion Variations Direct by: Tutorials Point (India) Ltd. It provided some information about a recursion variation called Direct.

I also found the Types of Recursions article by GeeksforGeeks. The information is similar yet different.

I looked for the same information in a few text books, but did not find much about the subject.

Recursion Variations:

* Direct
	- Tail recursion
	- Head recursion
	- Linear recursion
	- Tree recursion (Towers of Hanoi)
o Indirect
	- Nested

After some editing, I ended up considering Direct as a class of other recursions.

Direct Recursion:

A function is called direct recursive if it calls the same function. 

The definition that I found on-line seems to me as the base definition for a recursive function.

We will use a factorial function as an example of this type of recursion.

5
main <<< n: 5
main <<< factorial: 120

1
main <<< n: 1        
main <<< factorial: 1

Our test code reads the single input line that holds the value for the factorial that we need to compute.

The value is displayed to verify that all is well so far.

We then call the function of interest and display the returned value.

    /**
     * Test scaffold
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read `n` ****
        int n = Integer.parseInt(br.readLine().trim());

        // **** close buffered reader ****
        br.close();

        // ???? ????
        System.out.println("main <<< n: " + n);

        // **** call function of interest and display result ****
        System.out.println("main <<< factorial: " + factorial(n));
    }

The cod for the test scaffold is quite simple. We read the input line and extract the value for `n`. The value is displayed. We then call the function of interest and display the returned value.

    /**
     * Factorial
     * Direct recursion.
     */
    static int factorial(int n) {

        // **** sanity check(s) ****
        if (n < 0) return -1;

        // **** base case ****
        if (n <= 1) return 1;

        // **** recursive call ****
        return n * factorial(n - 1);
    }

The factorial function starts by issuing a sanity check.

We then check for the base case.

If the function is not done, it recursively calls the factorial function decrementing by one the value of `n`. When the factorial function returns, the returned value is multiplied by `n`.

I believe this function follows the KISS principle.

The entire code for this project can be found in my GitHub repository.

Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different web sites (i.e., HackerRank, LeetCode).

If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.

Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.

Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.

Regards;

John