What is Recursion?

In this article we will explain some of the key concepts of recursion, which is a widely used and extremely powerful programming technique. If you’re serious about your programming career, or just want to expand your programming knowledge, you should definitely get at least a basic understanding of recursion.

So, let’s cut to the chase – what is Recursion? More precisely; what is a recursive method?

A Recursive method is a method that in some way calls itself, either directly or indirectly. 

If this makes your head spin, don’t worry. Let’s illustrate this with an example in Java, and we’ll name our method recursiveMethod. 

Note: I highly recommend that you bring up your favorite IDE and code along with this tutorial. This will give you some valuable hands on experience, and help you get a better understand of recursion.

Do you see how the recursiveMethod calls itself? That’s recursion!

Now, this method is of course useless. In fact, the whole program will run out of memory, as a call to the recursiveMethod would initiate an endless “loop”, producing a StackOverflowError.
Why is that? Try to answer this question yourself before proceeding..

The reason why this method produce a StackOverflowError is because we didn’t provide our method with a base case. In simpler terms, we don’t progress towards an end condition which can be solved without using recursion. 

Rule 1 of Recursion: You must always provide a base case.

Note: The following exercises do not represent how you would use recursion in real world applications. Generally speaking, if you can solve a problem using a loop, you should do that, instead of using recursion. The examples used in this tutorial are simply meant to demonstrate how recursion works.

Exercise 1: Change the recursiveMethod so that it counts down from 3 to 0 without using a loop. Hint: Provide a base case which can be solved without using recursion.

Do you see what’s going on here? Our base case is the first test in the method. First, we check whether n is less than 0. If this returns true, we return and terminate the recursive calls.
If the condition returns false, we print out n. The recursive call on line 14 decrements n with 1 each time it is called. This brings us to the second rule of recursion;

Rule 2 of Recursion: You must always progress towards a base case.

Exercise 2: Change the recursiveMethod so that it counts from 0 to 3 without using a loop. Hint: You can solve this without altering the base case, and still provide 3 as the initial parameter to the method.

If you understand what’s going on here, great! However, if you don’t quite get why the entire order is changed when we move System.out.println() to after the recursive method call, that’s fine.
Just keep on reading, and you’ll get it eventually.

Exercise 3: Create a recursive method which calculates the factorial of a number. For example, the factorial of 5 is: 5! = 5 x 4 x 3 x 2 x 1 = 120.

The following GIF illustrates how this method will be run by the compiler.

Illustration of factorial recursion

Note: To understand how recursion works, you should be familiar with stacks

How Recursion works internally

When creating and calling recursive methods, the compiler makes use of something called the call stack. 

Whenever you call a method it is placed on top of the call stack.
Note that there can be multiple methods on the call stack, and each method is processed sequentially.
Said in other words; the last method placed on the call stack will be executed first!

Note that there is nothing special about the call stack, in terms of how it behaves. It adheres to the same principles as a regular stack, which tells us that it follows the LIFO (Last In First Out) cycle.

Okay, let’s provide this knowledge with a walkthrough of exercise 1 and 2.

Walkthrough of recursion exercise 1

We first make our initial call to recursiveMethod, passing in 3. The table below illustrates the following steps:

CallsValue of nCondition
Call to recursiveMethod(n)3
Is n less than 0?3false
System.out.println(n)3
Call to recursiveMethod(n – 1)2
Is n less than 0?2false
System.out.println(n)2
Call to recursiveMethod(n – 1)1
Is n less than 0?1false
System.out.println(n)1
Call to recursiveMethod(n – 1)0
Is n less than 0?0false
System.out.println(n)0
Call to recursiveMethod(n – 1)-1
Is n less than 0?-1TRUE
Base case reached-1RETURN

Walkthrough of recursion exercise 2

We first make our initial call to recursiveMethod, still passing in 3. We keep our base case, but place the recursive call before the call to System.out.println().

CallsValue of nConditionCall stack
Call to recursiveMethod(n)3recursiveMethod(3)
Is n less than 0?3falserecursiveMethod(3)
Call to recursiveMethod(n – 1)2recursiveMethod(2)
recurseMethod(3)
Is n less than 0?2falserecursiveMethod(2)
recursiveMethod(3)
Call to recursiveMethod(n – 1)1recursiveMethod(1)
recursiveMethod(2)
recursiveMethod(3)
Is n less than 0?1falserecursiveMethod(1)
recursiveMethod(2)
recursiveMethod(3)
Call to recursiveMethod(n – 1)0recursiveMethod(0)
recursiveMethod(1)
recursiveMethod(2)
recursiveMethod(3)
Is n less than 0?0falserecursiveMethod(0)
recursiveMethod(1)
recursiveMethod(2)
recursiveMethod(3)
Call to recursiveMethod(n – 1)-1recursiveMethod(0)
recursiveMethod(1)
recursiveMethod(2)
recursiveMethod(3)
Is n less than 0?-1TRUE
Base case is reached, the call stack will now be popped
Pop the call stack,0recursiveMethod(1)
recursiveMethod(2)
recursiveMethod(3)
System.out.println()0recursiveMethod(2)
recursiveMethod(3)
Pop the call stack1recursiveMethod(2)
recursiveMethod(3)
System.out.println()1recursiveMethod(2)
recursiveMethod(3)
Pop the call stack2recursiveMethod(3)
System.out.println()2recursiveMethod(3)
Pop the call stack3
System.out.println()3

In my opinion, this example is great for illustrating of recursion works. Each time a recursive call is made in recursiveMethod, it is added to the call stack. When we reach our base case, n less than 0, the program starts to pop the call stack.

Summary

This article provided you with a very basic introduction to how recursion works.

  • A recursive method is a method which calls itself, either directly or indirectly.
  • Recursive methods must always provide a base case, which can be solved without using recursion.
  • Recursive methods must always proceed towards the base case, avoiding circular logic / infinite “loops”.
Tutorials will only get you so far..
If you wish to expand your Java skill-set and become an advanced Java developer, I personally recommend the Comprehensive Java Course by Edureka.
You can get 25% with the coupon code LIMITED25 😉

Leave a Reply

Your email address will not be published. Required fields are marked *