This post is part of a personal study group activity, summarizing the content after reading through the book "Grokking Algorithms."

In programming languages, recursion means a function calling itself. Recursion is one of the most important concepts in algorithms, and by its very nature, it can effectively improve complex computations and the time they take to run.

JAVASCRIPT
/**
 * 재귀 함수
 */
function recursive()
{
	console.log('recursive');

	recursive();
}

OUTPUT
recursive
recursive
recursive
recursive
recursive
recursive
...

The source code above is a simple example demonstrating the nature of recursion. Calling the function above prints the word "recursive" endlessly.

This happens because the recursive function endlessly calls itself from within itself. On the surface, this might look like a pointless trick, but harnessing recursion's properties well makes it an extremely powerful tool.

Up until now, whenever we needed to repeat some action in code, we used loops. Repetition statements like for and while let us repeat an action as many times as we want.

Here's how you'd design code that counts down from 10 to 0.

JAVASCRIPT
/**
 * 루프를 활용한 카운트다운 함수
 * 
 * @param {number} start: 시작 숫자
 */
function countdown(start)
{
	for (let i = start; i >= 0; i--)
	{
		console.log(i);
	}
}

INPUT
10

OUTPUT
10
9
8
7
6
5
4
3
2
1
0

The source above is a countdown implementation written in JavaScript using a loop. But instead of using a loop, you can also structure it with recursion, as shown below.

JAVASCRIPT
/**
 * 재귀를 활용한 카운트다운 함수
 * 
 * @param {number} start: 시작 숫자
 */
function countdown(start)
{
	console.log(start);

	countdown(start - 1);
}

INPUT
10

OUTPUT
10
9
8
7
6
5
4
3
2
1
0
-1
-2
...

Conversely, the source code above performs a countdown using recursion instead of a loop. It prints start, then passes start minus 1 back into countdown, calling itself again.

Most loops can be replaced with recursion. Beyond simply serving as a substitute, recursion can also, unlike loops, offer meaningful performance improvements in certain cases.

But before that, let's look at the output of the source code above. Normally, a countdown counts from a given number down to 1 or 0. Yet the source above keeps going past 0, down through -1, -2... endlessly. Why does this happen?

The recursive function described in the previous section can't really be called a countdown. It's really no different from just listing numbers endlessly starting from the input. This happens because this recursive function has nothing resembling a brake.

Since what we actually want is a countdown to 0, we need to change it so that once start's value reaches 0, it no longer calls itself.

JAVASCRIPT
/**
 * 재귀를 활용한 완전한 카운트다운 함수
 * 
 * @param {number} start: 시작 숫자
 */
function countdown(start)
{
	console.log(start);

	// 값이 0보다 클 경우
	if (start > 0)
	{
		countdown(start - 1);
	}
}

INPUT
10

OUTPUT
10
9
8
7
6
5
4
3
2
1
0
...

The source above fixes this issue. It only calls itself again if start is greater than 0. Once it's less than or equal to 0, recursion no longer occurs and execution ends. This is what puts the brakes on execution.

Just as we insert a specific condition into a for or while loop to make it repeat only as many times as we want, recursion likewise needs a similar condition attached so that it repeats only as much as intended.

Of course, while the two loop constructs make it clear exactly where and how to specify such a condition, recursion builds the condition inside the code itself, so the mechanism isn't as obvious. That's why people new to recursion, or those without much experience with it, aren't used to setting up conditions this way, and sometimes end up writing recursive functions that run forever.

This condition that stops recursion is called the base case. In the countdown example above, the base case is start > 0.

As mentioned earlier, recursion's condition isn't visually obvious. Because of this, in some cases it can even be difficult just to read recursive code. Let's practice reading recursive code through a simple example.

Among the things we learned in high school math is the factorial operation. Factorial is written like $5!$, and its result is $5 \times 4 \times 3 \times 2 \times 1 = 120$. In general form, this can be written as follows.

$$n! = n \times (n - 1) \times (n - 2) \times \dotsb \times 2 \times 1$$

The factorial operation can be shortened to $n! = n \times (n - 1)!$. This kind of pattern is very well suited to applying recursion.

JAVA
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

/**
 * 누구나 자료 구조와 알고리즘 팩토리얼 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/07/31/about-algorithm-chapter09/">재귀를 사용한 재귀적 반복</a>
 * @since 2021.08.02 Mon 22:57:53
 */
public class Factorial
{
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int index = Integer.parseInt(reader.readLine());
		
		writer.write(String.valueOf(factorial(index)));
		
		writer.close();
		reader.close();
	}
	
	/**
	 * 팩토리열 연산 결과 반환 함수
	 *
	 * @param index: [int] 인덱스
	 *
	 * @return [int] 팩토리얼 연산 결과
	 */
	private static int factorial(int index)
	{
		// 인덱스가 1일 경우
		if (index == 1)
		{
			return 1;
		}
		
		// 인덱스가 1이 아닐 경우
		else
		{
			return index * factorial(index - 1);
		}
	}
}

INPUT
10

OUTPUT
3628800

The book describes the following method for reading recursive code.

1. Find what the base case is.
2. Look at the function assuming it's handling the base case.
3. Look at the function assuming it's handling the condition immediately before the base case.
4. Keep analyzing this way, moving up one condition at a time.

JAVA
// 인덱스가 1일 경우
if (index == 1)
{
	return 1;
}

// 인덱스가 1이 아닐 경우
else
{
	return index * factorial(index - 1);
}

The structure of the source code above is very simple, so it's not hard to spot the branch. The branch is between the case where index == 1 and the case where it isn't.

JAVA
// 인덱스가 1이 아닐 경우
else
{
	return index * factorial(index - 1);
}

Since recursion means a function calling itself, we can infer that the else branch is where recursion happens. That means the branch where recursion doesn't happen is the base case.

JAVA
// 인덱스가 1일 경우
if (index == 1)
{
	return 1;
}

In other words, the base case of the recursive function above is index == 1. factorial(1) returns 1. Based on this base case, expanding out factorial(4)'s execution gives us the following.

1. $\text{factorial(4)} = 4 \times \text{factorial(3)}$
2. $\text{factorial(4)} = 4 \times 3 \times \text{factorial(2)}$
3. $\text{factorial(4)} = 4 \times 3 \times 2 \times \text{factorial(1)}$
4. $\text{factorial(4)} = 4 \times 3 \times 2 \times 1 = 24$

This is how the function performs its computation by sequentially calling itself. Since a recursive function's base case is what halts the recursion, expanding it out based on the base case makes it relatively easy to understand the computation.

While it's important for us to understand recursive functions, ultimately the computer is the one actually executing the code. In other words, understanding how the computer interprets recursion is just as important as understanding it ourselves.

In the previous chapter, we covered stacks. When a computer handles recursion, it manages it using a stack. Let's see how a computer manages factorial(4) using a stack.

1. Call factorial(4).

Since factorial(4) calls factorial(3) internally, factorial(4) is pushed onto the stack and factorial(3) is executed. At this point, factorial(4) hasn't finished—its computation is merely paused due to the recursive call.

2. Call factorial(3).

Likewise, since the recursion calls factorial(2) during computation, execution is paused and pushed onto the stack in the same way.

3. Call factorial(2).

Same as above.

4. Call factorial(1).

Since factorial(1) is the base case, no further recursive call happens. It returns 1 and finishes. However, since data still remains on the stack, we know the overall computation isn't finished yet.

5. Finish factorial(2).

factorial(2)'s result depends on factorial(1)'s result. Since factorial(1)'s result has now been computed, factorial(2) can finish. Its computation ends and it's removed from the stack.

6. Finish factorial(3).

factorial(3)'s computation ends and it's removed from the stack.

7. Finish factorial(4).

factorial(4)'s computation ends and it's removed from the stack. Since no data remains on the stack, the entire computation is complete.

As shown above, recursion relies on a stack to perform its computation. If the base case is set up incorrectly, recursive computation could end up running forever. In that case, the stack would likewise keep growing endlessly, and once memory can no longer handle it, a stack overflow occurs.

The factorial operation we've covered so far could, in fact, be solved without much difficulty using a loop, and the code shown didn't offer much of an advantage from using recursion either.

This time, let's design code around a topic where recursion offers a more meaningful advantage. By its very structure, recursion is best suited for algorithms where the algorithm needs to call itself. In other words, whether to use recursion comes down to whether the function needs to call itself again, more so than a simple loop.

If you've ever loaded a file list in code, this will feel familiar. Loading the entire file list within a given folder is trickier than you might expect. Simply grabbing the file list immediately under a folder would be easy, but grabbing files from its subfolders, and their subfolders, and so on, isn't nearly as simple.

Let's write code that prints out the list of all folders in the current folder and its subfolders. First, let's start simple, ignoring subfolders, and just grab the list of folders that exist directly in the current folder.

The folder's root path is D:\root, and its structure is as follows.

JAVA
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Objects;

/**
 * 누구나 자료 구조와 알고리즘 폴더 리스트 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/08/04/about-algorithm-chapter09/">재귀를 사용한 재귀적 반복</a>
 * @since 2021.08.03 Tue 22:55:59
 */
public class DirectoryList
{
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		writer.write("폴더 리스트를 출력할 경로를 입력하세요 >> ");
		writer.flush();
		
		String path = reader.readLine();
		
		String[] list = getList(path);
		
		writer.write(Arrays.toString(list));
		writer.newLine();
		writer.flush();
		
		writer.close();
		reader.close();
	}
	
	/**
	 * 폴더 리스트 반환 함수
	 *
	 * @param path: [String] 경로
	 *
	 * @return [String[]] 폴더 리스트
	 */
	private static String[] getList(String path)
	{
		return Arrays.stream(Objects.requireNonNull(new File(path).listFiles(File::isDirectory))).map(File::getName).toArray(String[]::new);
	}
}

INPUT
D:\root

OUTPUT
[a, b, c]

This only prints the immediate subfolder list of the current folder. Let's improve the code to print one additional level of subfolders.

JAVA
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

/**
 * 누구나 자료 구조와 알고리즘 폴더 리스트 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/08/04/about-algorithm-chapter09/">재귀를 사용한 재귀적 반복</a>
 * @since 2021.08.03 Tue 23:32:46
 */
public class MoreDirectoryList
{
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		writer.write("폴더 리스트를 출력할 경로를 입력하세요 >> ");
		writer.flush();
		
		String path = reader.readLine();
		
		ArrayList<String> list = getList(path);
		
		writer.write(String.valueOf(list));
		writer.newLine();
		writer.flush();
		
		writer.close();
		reader.close();
	}
	
	/**
	 * 폴더 리스트 반환 함수
	 *
	 * @param path: [String] 경로
	 *
	 * @return [ArrayList<String>] 폴더 리스트
	 */
	private static ArrayList<String> getList(String path)
	{
		ArrayList<String> list = new ArrayList<>();
		
		File[] files = new File(path).listFiles(File::isDirectory);
		
		// 파일 배열이 유효할 경우
		if (files != null)
		{
			for (File file : files)
			{
				list.add(file.getName());
				
				File[] files1 = file.listFiles(File::isDirectory);
				
				// 파일 배열이 유효할 경우
				if (files1 != null)
				{
					for (File file1 : files1)
					{
						list.add(file1.getName());
					}
				}
			}
		}
		
		return list;
	}
}

INPUT
D:\root

OUTPUT
[a, a1, a2, b, b1, b2, c, c1, c2]

This now also prints out the subfolders of each folder. Looking at the code, whenever something is a folder, the same code runs one more time. But this approach is extremely limited. If the folder depth were fixed, you could keep repeating the same code like this indefinitely, but such a case almost never occurs in practice, making this approach meaningless.

In this case, using recursion lets you print out the subfolder list for every level with very little effort.

JAVA
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

/**
 * 누구나 자료 구조와 알고리즘 재귀 폴더 리스트 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/08/04/about-algorithm-chapter09/">재귀를 사용한 재귀적 반복</a>
 * @since 2021.08.03 Tue 23:36:43
 */
public class RecursiveDirectoryList
{
	private static final ArrayList<String> LIST = new ArrayList<>();
	
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		writer.write("폴더 리스트를 출력할 경로를 입력하세요 >> ");
		writer.flush();
		
		String path = reader.readLine();
		
		getList(path);
		
		writer.write(String.valueOf(LIST));
		writer.newLine();
		writer.flush();
		
		writer.close();
		reader.close();
	}
	
	/**
	 * 폴더 리스트 산출 함수
	 *
	 * @param path: [String] 경로
	 */
	private static void getList(String path)
	{
		File[] files = new File(path).listFiles(File::isDirectory);
		
		// 파일 배열이 유효할 경우
		if (files != null)
		{
			for (File file : files)
			{
				LIST.add(file.getName());
				
				getList(file.getPath());
			}
		}
	}
}

INPUT
D:\root

OUTPUT
[a, a1, a2, b, b1, b11, b2, c, c1, c11, c12, c2]

Using recursion, we can print out every folder name under all subfolders. There's no need to awkwardly repeat the same code, and we can print out the full folder-name list without needing to know how deep the subfolder structure goes.

The traversal order is as follows.

The key points of this chapter are as follows.

• Recursion is a structure where a function calls itself.
• Most loops can be replaced with recursion.
• By an algorithm's structure, recursion is most suitable when the algorithm needs to call itself.

Even when solving Baekjoon algorithm problems, quite a few of them required recursion, which shows just how widely recursion is used in algorithms. Summarizing the properties of recursion through this chapter should be a big help going forward when solving algorithm problems.