재귀호출 리마인드 내용 정리

📌 재귀호출

재귀호출 : 어떤 메소드가 자기 자신을 호출

• 재귀호출을 하면 반드시 탈출 조건이 필요
• 재귀호출은 조건문이 반드시 필요(탈출 조건)
• 탈출 조건이 없으면 무한히 재귀호출이 이어짐
• 예시) 피보나치 수열

피보나치 수열 예시 (출처 : https://news.samsungdisplay.com/23402)

• 탈출 조건(초기값)
• 점화식 = 어떤 수열이 서로 다른 항간의 관계로 표현된 것
• f(n) = f(n-1) + f(n-2)

 

재귀 호출의 예시(피보나치 수열)

int fibonacci(n) {
	if(n < 2) {   // 탈출 조건
    	return 1;
    }
    return fibonacci(n-1) + fibonacci(n-2);  // 재귀 호출(점화식 구현)
}

 

 

• 하노이의 탑
  • 더 작은 원반이 항상 더 큰 원반보다 위에 있도록 유지하면서 모든 원반을 옮기는 게임
   

하노이의 탑 그림 예시 (출처 : https://wonit.tistory.com/193)

 

• f(n, from, to, support)  =>  f(개수, 출발지, 도착지, 보조지)
• 출발지(A) : N개의 원판이 있을 때 옮기는 것을 시작하는 곳
• 도착지(C) : N개의 원판이 옮겨져야 하는 목표지
• 보조지(B) : N개의 원판이 목표 기둥으로 옮겨질 때 Buffer로써 사용되는 곳 (목적지로 가는 과정에서 중간 단계에서 사용되는 임시 공간)
• f(n, A, C, B) = f(n-1, A, B, C) + f(n-2 , A, C, B) + f(n-1, B, C, A)
• f(4, A, C, B) = f(3, A, B, C) + f(2, A, C, B) + f(3, B, C, A)

 

재귀 호출의 예시(하노이의 탑)

import java.util.List;
import java.util.ArrayList;

class Solution {
	public int[][] solution(int n) {
    	List<int[]> result = hanoi(1, 3, 2, n);
        return result.stream().toArray(int[][]::new);
    }
    
    List<int[]> hanoi(int start, int end, int support, int n) {
    	if(n == 1) {
        	List<int[]> result = new ArrayList<>();
            result.add(new int[]{start, end});
            return result;
        }
        
        List<int[]> result = hanoi(start, support, end, n-1);
        result.add(new int[]{start, end});
        result.addAll(hanoi(support, end, start, n-1));
        return result;
     }
}

 

• stream() : Java에서 컬렉션을 처리하는 기능(Java 8 이상)
  • 컬렉션을 순차적으로 처리하거나 변형하고 필터링 가능
  • result.stream().toArray(int[][]::new)
  • 리스트에 저장된 데이터를 배열로 변환하는 방법
  • stream() 메서드를 호출하여 위 리스트를 스트림으로 변환 그런 다음 toArray 메서드를 호출하여 스트림을 배열로 변환
  • toArray() 메서드의 인자로는 생성될 배열의 타입을 지정
  • 람다식을 사용하여 2차원 배열 생성(int[][]::new)

 

 

---

강사님께서 stream() 사용법을 찾아보고, 익히는게 좋다고 말씀하셨다. 장점으로는 한 줄로 간편하게 출력이 가능한 부분이다. 이처럼 간편한 컬렉션 처리로 복잡한 반복문이나 조건문을 작성할 필요 없이 선언적인 방식으로 데이터를 처리할 수 있다는 장점과 stream()은 병렬 처리를 지원하므로 멀티코어 프로세서를 활용하여 대량의 데이터를 처리할 때 성능을 향상시킬 수 있다는 장점을 가지고 있다.

 

반면, 컬렉션을 스트림으로 변환하면 메모리 사용량이 증가할 수 있다는 단점을 가지고 있다. 특히 컬렉션의 크기가 매우 큰 경우 부가적인 메모리 사용량이 성능에 영향을 줄 수 있다.

아래는 일반적으로 stream이 많이 사용하는 코드 형태 예제를 찾아보았고, 주어진 리스트에서 요소를 필터링하거나 매핑하여 새로운 리스트를 생성하고, 요소의 개수를 세는 등의 작업을 수행하는 코드이다.

 

List<String> dataList = Arrays.asList("apple", "banana", "orange", "grape", "watermelon");

// 리스트에서 필터링하여 새로운 리스트 생성
List<String> filteredList = dataList.stream()
                                   .filter(item -> item.startsWith("a"))
                                   .collect(Collectors.toList());

// 리스트에서 요소의 개수 세기
long count = dataList.stream()
                     .filter(item -> item.length() > 5)
                     .count();

// 리스트의 요소들을 대문자로 변환하여 새로운 리스트 생성
List<String> upperCaseList = dataList.stream()
                                    .map(String::toUpperCase)
                                    .collect(Collectors.toList());