Recursion 개념

Recursion Function

• 재귀 함수
• 함수 내부에서 자기 자신을 호출하는 함수
• 재귀함수를 사용하는 동안 함수 호출이 계속 쌓이기 때문에(호출 스택이 많아짐) 성능이 저하될 수 있다.
• -> 종료 조건인 Base case 명확히 설정 필요

 

호출 스택

• 프로그램에서 함수나 메서드를 호출할 때 해당 함수나 메서드의 실행이 끝날 때까지 실행되는 다른 함수나 메서드의 호출 정보를 저장하는 자료구조
• 디버깅, 예외처리, 재귀함수 등 다양하게 사용
• 함수가 호출될 때마다 그 함수의 호출 정보를 저장하고 함수의 실행 결과가 ㅏ반환되면 해당 함수의 호출 정보를 스택에서 제거한다.

 

 

장점

• 코드의 가독성 높음

 

 

단점

• 재귀함수를 호출할 때마다 스택에 새로운 프레임 생성 -> 스택이 깊어질 경우 스택 오버플로우 발생 가능

 

 

재귀함수 예시

 

1) 1부터 N까지의 합 구하기

 

public class Main
{
    public static void main(String[] args)
    {
        System.out.println("1부터 5까지의 합: " + Function(5));
    }
 
    public static int Function(int num)
    {
        if(num == 1)
        {
            return 1;
        }
        else
        {
            return num + Function(num -1);
        }
    }
}

 

num이 만약 1일 경우 1을 반환하고 함수가 종료된다.

1이 아닐 경우에는 num 값에 Function(num -1)값을 더해서 반환한다.

 

 

2) 팩토리얼 계산

 

팩토리얼: 1부터 N까지의 정수를 곱한 값

public class Main
{
    public static int factorial(int n) {
    	// Base case: n이 1 이하일 경우 1을 반환
    	if (n <= 1) {
    	    return 1;
    	}
    	// Recursive case: n-1에 대한 팩토리얼 값을 구하고 n과 곱셈
    	else {
        	return n * factorial(n-1);
    	}
	}
}

 

N이 1 이하일 경우 1을 반환한다.

N-1에 대한 팩토리얼 값을 구하고 N을 곱한다.

 

 

 

 

참고

https://adjh54.tistory.com/194#1)%20%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98(Recursion%20Function)-1

[Java/알고리즘] 재귀 함수(Recursion Function) 이해하기

https://lktprogrammer.tistory.com/106

[자바 프로그래밍] 재귀(Recursion) 알고리즘 기초

https://jelong.tistory.com/entry/%EC%9E%90%EB%B0%94-%EC%9E%AC%EA%B7%80Recursion-%ED%95%A8%EC%88%98%EB%9E%80-%EC%89%BD%EA%B2%8C-%EC%9D%B4%ED%95%B4%ED%95%B4%EB%B3%B4%EC%9E%90

[Java] 재귀(Recursion) 함수란? 쉽게 이해해보자