[자바 JAVA] 재귀함수 (vs 반복문)

정의:

재귀 함수란 함수 내부에서 자기 자신을 호출하여 문제를 해결하는 함수를 말한다.

즉, 함수가 자신을 호출하여 작업을 수행하는 방식이다.

 

재귀 함수는 문제를 간결하고 직관적으로 해결할 수 있도록 도와준다.

피보나치 fibonacci 수열과 같은 수학적인 계산 문제나, 이진 탐색과 같은 데이터 검색 문제에서 재귀 함수를 사용한다.

 

재귀 vs 반복문

재귀 함수와 반복문은 모두 반복적인 작업을 수행하는 데 사용되는 구조이지만, 각각의 사용에는 차이가 있다.

 

재귀 함수:

- 함수가 자기 자신을 호출해서 문제를 해결한다.

- 코드가 간단하고 이해하기 쉽다.

- 반복문으로 처리하기 어려운 문제들을 재귀 함수로 풀이 할 경우 코드가 간결해진다.

- 단점: 호출 스택이 계속해서 쌓이기 때문에 스택 오버플로우, 메모리 문제가 발생할 수 있다.

 

반복문:

- 일정한 작업을 수행하는 데 사용되는 구조다.

- 반복문은 재귀 함수보다 일반적으로 빠르고 메모리 사용량도 적다.

- 코드가 복잡해질 수 있으므로 종료 조건을 설정하는 것이 중요하다.

 

즉, 작은 문제를 해결하는 경우에는 재귀 함수를 사용하고, 큰 문제를 해결하기 위해서는 반복문을 사용하는 것이 좋다.

 

 재귀 함수의 예제: 배열을 입력받아 순서가 뒤집힌 배열을 리턴해야 합니다.

 

 

import java.util.*;

public class Solution { 
	public int[] reverseArr(int[] arr){
    //1. 새로운 배열로 기존 입력된 arr 배열의 마지막 인덱스의 값부터 넣어줍니다.

    //2. base case : 문제를 더 이상 쪼갤 수 없는 경우
      if(arr.length == 0) {       //입력된 배열이 빈 배열인 경우
        return new int[]{};         //빈 배열을 반환합니다.
      }
    //3. recursive Case : 그렇지 않은 경우
    //배열의 가장 마지막 요소만을 가지고 있는 head 배열을 선언, 할당합니다.
      int[] head = Arrays.copyOfRange(arr, arr.length - 1, arr.length);       
    //남은 요소를 가지고 있는 tail 배열을 선언 및 할당
    //해당 배열의 요소가 모두 제거될 때까지 재귀함수를 호출합니다.
      int[] tail = reverseArr(Arrays.copyOfRange(arr, 0, arr.length - 1));     
    
    //할당된 head배열과 tail 배열을 합친 새로운 배열을 선언, 할당합니다.
    //새로운 배열을 선언합니다. 배열의 크기는 head.length와 tail.length를 합친 크기로 선언합니다.
      int[] dest = new int[head.length + tail.length];
      
    //System.arraycopy메서드를 사용하여, head, tail 두 배열의 요소를 모두 dest 배열에 복사합니다.
      System.arraycopy(head, 0, dest, 0, head.length);
      System.arraycopy(tail, 0, dest, head.length, tail.length);

      return dest;
	} 
}

// 출력값 예시
// int[] output = reverseArr(new int[]{1, 2, 3});
// System.out.println(Arrays.toString(output)); // --> [3, 2, 1]