재귀적으로 동작하는 소스 코드에 대한 이해가 필요하다고 생각하여 정리해본다. 함수가 자기 자신을 호출하는 처리를 재귀(Recursive)라고 한다. 함수를 재귀적으로 사용하면 반복문처럼 사용하거나 결과가 다른 결과 도출을 위한 단계가 되도록 점진적인 처리를 하거나 대상의 범위 등을 달리해가며 같은 처리를 적용하여 원하는 결과를 만들어 내는 등 응용할 수 있는 방법이 다양하다. 재귀를 활용하여 팩토리얼을 구한다거나, 퀵정렬을 한다거나, 트리구조에서 하위 노드를 탐색한다거나 할 수 있다.
*클래스 내에 선언한 함수를 메소드(method)라고 표현하지만 해당 포스팅에서는 '함수'라는 단어로 통일한다.
1. 조건 없는 재귀 호출 = 무한궤도 영원한 굴레
자기 자신을 호출하는 재귀 함수의 모습은 다음과 같다.
private void recursive(){
recursive();
//영원히 주석이 있는 이 줄에는 도달할 수 없다. 함수를 끝낼 수 없는 것.
}하지만 위의 함수는 영원히 끝날 수 없으며 스택오버플로우를 발생시킨다. 자기자신을 호출하는 자기자신을 호출하는 자기 자신을 호출하는 자기자신을 호출하는 자기자신을 호출하는 자기 자신을 호출하는........ 무한 반복이기 때문이다. 호출한 함수가 종료 되어주어야 재귀호출 이후의 코드를 진행하거나 함수를 끝마칠 수 있다. 호출한 함수 그 자체도 계속하여 끝날 수 없는 자기 자신을 호출하는 무한 반복의 궤도에 빠지고 있다.
무한궤도에 빠지지 않으려면 무한 재귀 호출을 막기 위한 "조건"이 필수로 있어야 한다. 재귀 구조를 이용하여 얻고자 하는 결과가 어떠한 점진적인 처리의 결과라면 점진적인 처리의 시작점 또는 종료점이 있어야 한다.
이전 단계의 결과는 그 이전 단계의 결과로 구하고 그 이전 단계의 결과는 또 그 이전 단계의 결과로 구하고... 무한 굴레로 만들면 안된다. 특정 "조건" 에서는 재귀 호출을 하지 않는 시점이 필요하다. 더 이상 재귀호출을 하지 않는 그 순간, 마지막에 호출된 재귀함수부터 차례차례 종료가 될 것이고 재귀 호출을 한 함수는 재귀호출 이후의 코드를 실행하면서 차례차레 작업을 완수하고 스택에서 제거된다. 결국 최초 호출된 재귀함수도 종료되면서 원하는 결과를 만들어 낸다. 조건에 따라 더이상 재귀적으로 자신을 호출하지 않는 순간이 턴어라운드 되는 순간인 것이다.
2. 재귀호출을 할지 재귀호출을 멈출지 "조건"을 정해야 한다.
다음은 재귀함수를 반복문처럼 사용한 것이다. 1부터 n까지 콘솔창에 출력한다.
public static void main(String[] args){
recursive(10);
}
private static void recursive(int n){
if(n>1){
recursive(n-1);
}
//재귀호출을 했다면 내가 호출한 재귀 호출이 완료되어야 이 부분이 실행된다.
System.out.println(n);
}
recursive(10) : n이 10이니까 1보다 크네? recursive(9)를 호출! recursive(9) 가 완료 될 때까지 기다린다.
recursive(9) : n이 9니까 1보다 크네? recursive(8)을 호출! recursive(8)이 완료 될 때까지 기다린다.
recursive(8) : n이 8이니까 1보다 크네? recursive(7)을 호출! recursive(7)이 완료 될 때까지 기다린다.
recursive(7) : n이 7이니까 1보다 크네? recursive(6)을 호출! recursive(6)이 완료 될 때까지 기다린다.
recursive(6) : n이 6이니까 1보다 크네? recursive(5)을 호출! recursive(5)이 완료 될 때까지 기다린다.
...
recursive(2) : n이 2이니까 1보다 크네? recursive(1)을 호출! recursive(1)이 완료 될 때까지 기다린다.
recursive(1) : n이 1이니까 1보다 크지 않네? System.out.println(1);을 실행하고 종료! (턴어라운드 되는 순간)
recursive(2) : recursive(1)이 종료되었으므로 System.out.println(2);을 실행하고 종료!
...
recursive(6) : recursive(5)이 종료되었으므로 System.out.println(6);을 실행하고 종료!
recursive(7) : recursive(6)이 종료되었으므로 System.out.println(7);을 실행하고 종료!
recursive(8) : recursive(7)이 종료되었으므로 System.out.println(8);을 실행하고 종료!
recursive(9) : recursive(8)이 종료되었으므로 System.out.println(9);을 실행하고 종료!
recursive(10) : recursive(9)이 종료되었으므로 System.out.println(10);을 실행하고 종료!
재귀함수를 반복문과 같은 용도로 사용하였다. 위의 코드의 결과는 아래 for문의 결과와 일치한다.
int n=10;
for(int i=1; i<=n; i++){
System.out.println(i);
}
3. 거슬러 올라가는 재귀적 처리. 원하는 결과를 만들기 위해 거슬러 올라간다.
피보나치 수열의 현재 값은 이전값과 전전값의 합이다. 현재값 A[i] = A[i-1] + A[i-2]인 것이다. 피보나치 수열의 10번째 값을 구하려면 어떻게 해야할까? 현재 값을 구하려면 이전값과 전전값을 더하면 된다. 이전 값을 구하려면 이전 값의 이전값과 전전값을 더하면 된다. 전전값을 구하려면 전전값의 이전값과 전전값을 더하면 된다. 이러한 논리로 쭉쭉 거슬러 올라가면 되는데 어느 순간에는 이전 값을 구하기 위한 재귀호출이 아니라 실제 값을 반환하는 순간이 있어야 한다. 피보나치 수열은 1항부터 시작하지만 편의상 0항이 0이라고 생각하였다. 이렇게 할 경우 2항부터는 A[i] = A[i-1] + A[i-2] 의 공식이 성립한다. 이를 바탕으로 실제로 값을 반환하는 시점은 0항일 때 0, 1항일 때 1이 되도록 만드는 것이다.
0 1 2 3 4 5 6 7 8 9 10
0 1 1 2 3 5 8 13 21 34 55
pibonacci(10) : 피보나치10항을 구해야해. 그러려면 pibonacci(9)와 pibonacci(8)을 더해야지. 먼저 pibonacci(9)부터..
pibonacci(9) : 피보나치9항을 구해야해. 그러려면 pibonacci(8)과 pibonnaci(7)을 더해야지. 먼저 pibonacci(8)부터..
pibonacci(8) : 피보나치8항을 구해야해. 그러려면 pibonacci(7)과 pibonacci(6)을 더해야지. 먼저 pibonacci(7)부터..
...
pibonacci(2) : 피보나치2항을 구해야해. 그러려면 pibonacci(1)과 pibonacci(0)을 더해야지. 먼저 pibonacci(1)부터..
pibonacci(1) : 1항이니까 1을 반환하고 종료!
pibonacci(2) : pibonacci(1)이 종료됐으니 pibonacci(0)을 구한다.
pibonacci(0) : 0항이니까 0을 반환하고 종료!
pibonacci(2) : pibonacci(1)의 결과와 pibonacci(0)의 결과를 더해서 피보나치2항을 구했다. 이를 반환하고 종료한다.
...
pibonacci(8) : pibonacci(7)의 결과와 pibonacci(6)의 결과를 더해서 피보나치8항을 구했다.이를 반환하고 종료한다.
pibonacci(9) : pibonacci(8)의 결과와 pibonacci(7)의 결과를 더해서 피보나치9항을 구했다. 이를 반환하고 종료한다.
pibonacci(10) : pibonacci(9)의 결과와 pibonacci(8)의 결과를 더해서 피보나치10항을 구했다. 이를 반환하고 종료한다.
package main.java.Algorithm.recursive.pibonacci;
import java.util.*;
public class Pibonacci {
private static Map<Integer,Integer> piboMap = new HashMap<>();
public static void main(String[] args){
printPibonacci(10);
}
static int pibonacci(int n){
if(n<0){
System.out.println("1이상의 숫자를 입력하세요.");
}
if(piboMap.containsKey(n)){
return piboMap.get(n);
}
int currentNum;
if(n>=2){
currentNum = pibonacci(n-1) + pibonacci(n-2);
}else if(n==0){
currentNum = 0;
}else{
currentNum = 1;
}
piboMap.put(n,currentNum);
return currentNum;
}
static void printPibonacci(int n){
int i=1;
while(i<=n){
System.out.print(pibonacci(i) + " ");
i++;
}
System.out.println();
}
}
예제에서는 Map을 이용하여 이미 계산을 한 피보나치항의 결과를 저장하고, 저장된 결과값이 있는 경우에는 피보나치 재귀함수를 수행하지 않고 Map에서 값을 구하도록 하였다. pibonacci 재귀 함수의 호출이 중복되는 경우가 많다고 판단했기 때문이다.
4. Composite패턴에서의 재귀
아래의 그림과 같은 폴더 구조가 존재한다고 할 때 파일3의 용량을 확인하고 싶으면 어떻게 해야할까? 폴더를 하나하나 열어보고 그 안에 파일이 있으면 파일3인지 확인하고 용량을 확인할 수 있을 것이다. Composite패턴은 집합체와 요소를 동일시하여 다루는 패턴이다. 예시에서는 폴더와 파일을 동일시하여 다루기 때문에 파일이든 폴더든 동일한 함수( 구체적인 구현은 다르지만) 를 가지고 있으며 폴더일 경우 재귀적으로 하위폴더 및 파일에 대해 재귀적으로 처리하고 있다. 결과적으로 ROOT에서 fileSizeSearch() 함수를 한 번 실행하는 것만으로 재귀적으로 모든 폴더 및 파일을 확인할 수 있다.
FNF.java
package main.java.Algorithm.recursive.folderandfile;
public interface FNF {
abstract void fileSizeSearch(String name);
}Folder.java
package main.java.Algorithm.recursive.folderandfile;
import java.util.ArrayList;
public class Folder implements FNF{
private String name;
private ArrayList<FNF> fList = new ArrayList<>();
public Folder(String name){
this.name = name;
}
@Override
public void fileSizeSearch(String name) {
for(FNF f:fList){
f.fileSizeSearch(name);
}
}
public void addList(FNF f){
if(!fList.contains(f)){
fList.add(f);
}
}
}File.java
package main.java.Algorithm.recursive.folderandfile;
public class File implements FNF{
private int size;
private String name;
public File (int size, String name){
this.size = size;
this.name = name;
}
public String getName() {
return name;
}
@Override
public void fileSizeSearch(String name) {
if(this.name.equals(name)){
System.out.println(this.name + "파일의 크기는 : " + this.size);
}
}
}Main.java
package main.java.Algorithm.recursive.folderandfile;
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
Folder root = new Folder("root");
Folder A = new Folder("A");
Folder B = new Folder("B");
Folder C = new Folder("C");
Folder A1 = new Folder("A1");
Folder B1 = new Folder("B1");
File file1 = new File(10,"file1");
File file2 = new File(20,"file2");
File file3 = new File(30,"file3");
File file4 = new File(40,"file4");
File file5 = new File(50,"file5");
root.addList(A);
root.addList(B);
root.addList(C);
A.addList(A1);
B.addList(B1);
A1.addList(file1);
B1.addList(file2);
B1.addList(file3);
C.addList(file4);
C.addList(file5);
System.out.println("파일명을 입력하세요.");
String input = sc.nextLine();
root.fileSizeSearch(input);
}
}
직접 여러가지 예제를 구현해보면서 재귀함수에 대해 이해보고자 하였다. 함수가 스택에 쌓이는 장면을 상상하면서 어떤 조건에 재귀호출을 멈추는지, 어떤 처리를 통해 어떤 결과를 얻고자 하는지 생각해보는 것이 중요하다고 생각하였다.
'개발 > 개발관련' 카테고리의 다른 글
| [개발관련]배움의 중요성_ 김영한님의 강의를 듣고... (0) | 2023.07.18 |
|---|---|
| [개발관련] 이미지를 base64로 인코딩할 경우 HTTP 요청을 할 필요가 없는 이유_chatGPT (0) | 2023.07.12 |
| [개발관련] 프로세스와 포트에 대한 이해 (0) | 2023.06.29 |
| [개발관련] DNS전파 , 네임서버 (0) | 2023.06.27 |
| [개발관련] 액티브-스탠바이, 그리고 VIP (chatGPT) (0) | 2023.06.21 |