📌재귀

1. 메서드 안에서 또 자신의 메서드를 호출하는 것을 말한다.

2. 모든 재귀함수는 for 문으로 바꿀 수 있다.

3. 반복해서 메서드를 호출하므로 call stack에 메서드가 종료되지 않고 계속 쌓이게 된다. 이 과정이 for 문보다 메모리를 더 사용한다.

4. 메서드를 호출하고 매서드가 종료된 이후에 복귀를 위한 컨텍스트 스위칭 비용이 발생하게 된다.

재귀 사용방법

1. 종료조건을 반드시 작성
2. 문제를 작은 단위로 쪼갠다.

예시 - factorial

public class Factorial {
    public int factorial(int num) {
        int result;

        // base case
        if (num == 1) return result = 1;

        // recursive case
        result = num * factorial(num - 1);
        return result;
    }
}

class Factorial_Test {
    public static void main(String[] args) {
        Factorial f = new Factorial();

        int output = f.factorial(3);
        System.out.println(output);
    }
}

output = 6

• factorial(3) = 3x2x1 이다. factorial(2) = 2x1
  즉, factorial(3) = 3 x factorial(2)가 된다.

• main메서드에서 factorial(3)를 호출

  • factorial(3) = 3 x factorial(2)
  • factorial(2) = 2 x factorial(1)
  • factorial(1) = 1

public int factorial(int n) {
    int result;

    // base case
    if (n == 1) return result = 1;

    // recursive case
    result = n * factorial(n - 1);
        
    return result;
}

• 처음 factorial(3)이 call stack에 쌓이고 메서드가 실행되다가
  result = n * factorial(n - 1); 여기서 다시 factorial(2)가 호출된다. 이 때 아직 result의 값은 정해지지 않았다. = 대입 연산자는 가장 마지막에 연산되기 때문에 재귀가 먼저 발생한다.

• factorial(1)이 됐을 때 if (n == 1) return result = 1; 종료조건이 실행되면서 result = 1을 return 하면서 factorial(1) 메서드는 call stack에서 사라지고 factorial(2)로 되돌아간다.
  이제 여기서

result = 2 * factorial(2 - 1); 

// result = 2 * factorial(1) = 2 * 1 = 2   
return result;

이 두 문장이 실행되는 것이다. 그럼 factorial(2)는 result = 2를 리턴하고 factorial(3)으로 되돌아간다.

result = 3 * factorial(3 - 1);

// result = 3 * factorial(2) = 3 * 2 = 6
return result;

factorial(3)으로 와서 이 두 문장을 실행하고 result = 6 을 main메서드 output에 저장하고 출력한다.

그림으로 표현🔽

예시 - reverseArr

배열을 입력받아 순서가 뒤집힌 배열을 리턴하는 메서드

public class ReverseArr {
    public int[] reverseArr(int[] arr) {
        if (arr.length == 0) return new int[]{};

        int[] head = Arrays.copyOfRange(arr, arr.length - 1, arr.length);
        int[] tail = reverseArr(Arrays.copyOfRange(arr, 0, arr.length - 1));

        List<int[]> list = new ArrayList<>();
        list.add(head);
        list.add(tail);

        return list.stream().flatMapToInt(Arrays::stream).toArray();
    }
}

class ReverseArr_Test {
    public static void main(String[] args) {
        ReverseArr r = new ReverseArr();

        int[] output = r.reverseArr(new int[]{1, 2, 3});
        System.out.println(Arrays.toString(output));
    }
}

output = [3, 2, 1]

int[] tail = reverseArr(Arrays.copyOfRange(arr, 0, arr.length - 1)); : 메서드 중간에 재귀함수가 있다.
종료조건인 if (arr.length == 0) return new int[]{};가 만족되서 return이 될때까지 tail에 저장되지 않고 메서드가 계속 호출된다.
그러다가 종료조건을 통해 return 값이 생기면 이 값을 tail에 저장하고 종료조건 바로 전 메서드로 복귀하고

    List<int[]> list = new ArrayList<>();
    list.add(head);
    list.add(tail);

    return list.stream().flatMapToInt(Arrays::stream).toArray();

위의 재귀함수 이후 나머지 문장들이 수행된다. 이 문장 마지막에 return이 수행되서 메서드가 종료되고 또 이 바로 전 메서드로 복귀하고 위의 문장들을 수행한다.
이 과정을 반복하고 마지막 메서드의 return 문의 결과값을 main 메서드에서 출력하게 되는 것이다.

그림으로 표현🔽

---

📌DFS / BFS

DFS :
BFS :