재귀함수(recursive function)

1. 재귀함수(Recursive function)란?

재귀함수(Recursive function)란 함수 내에서 자기 자신을 호출하는 형태의 함수이다. 문제를 동일하면서 더 작은 문제로 분리하여 해결하는데, 현재 해결해야 하는 일을 다음으로 넘긴다 생각하면 된다.

---

2. 재귀함수의 특징

☑️ 기저 조건과 유도 부분으로 구성된다.

• 📌 기저 조건(Base part): 재귀 호출을 멈추는 부분이다. 이를 설정하지 않으면 무한 루프에 빠지게 된다.
  • 재귀함수에서 기저 조건에 도달했을 때 return을 통해 함수 실행을 종료하고 이전 함수 호출 지점으로 돌아간다.
    • return: 함수 실행 중단 및 반환에 사용된다.
• 📌 유도 부분(Inductive part): 함수가 자기 자신을 호출하여 문제를 더 작은 단위로 분해하고 해결하는 부분이다.

☑️ 함수 호출시 프로그램 메모리 구조에서 스택을 사용한다.

• 재귀 호출은 반복적인 스택을 사용하기 때문에 메모리 및 속도에서 성능 저하가 발생한다.
• 재귀 호출이 깊게 들어갈수록 메모리 사용량이 늘어나 💥스택 오버플로우(stack overflow)와 같은 문제가 발생할 수 있다.

☑️ 반복문보다 코드가 간결하고 가독성이 좋다.

• 반복문과 재귀함수는 반복적인 동작을 수행한다는 공통점이 있다.
• 일반적으로 재귀함수의 오버헤드로 인해 반복문이 성능이 더 좋지만, 코드를 간결하고 가독성 좋게 작성할 수 있다는 장점이 있기 때문에 상황에 맞게 재귀함수를 사용하는 것이 필요하다.

3. 실습 코드(팩토리얼 계산)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	// 일반 반복문으로 구현
	private static int factorial1(int n) {
	
		int result=1;
		for(int i=n;i>0;i--) {
			result*=i;
		}
		return result;
	}
	
	// 재귀함수로 구현1(전역 변수 사용)
	private static int result=1;
	private static void factorial2(int n) {
		if(n==0) {
			return;
		}
		result*=n;
		factorial2(n-1);
	}
	
	// 재귀함수로 구현2(계산 값 반환)
	private static int factorial3(int n) {
		if(n<=1) return 1;
		// 선행재귀: 재귀 호출이 일어난 후 현재 노드의 작업이 수행됨.
		return n*factorial3(n-1);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
		int N=Integer.parseInt(in.readLine());
		
		System.out.println(factorial1(N));
		factorial2(N);
		System.out.println(result);
		System.out.println(factorial3(N));
	}
}