[TIL] 2022.07.21 | 재귀함수

 

재귀 함수

재귀 함수(Recursion)는 특정 함수 내에서 자기 자신을 다시 호출하여 정의된 기능을 수행해나가는 함수로써 

요구되는 기능을 작은 범주로 세분화해서 제일 작은 문제부터 먼저 해결해 나감으로써 문제를 해결해나가는 방식이라고 할 수 있다.

또한 "반복문 -> 재귀함수" / "재귀함수 -> 반복문" 로 구현이 가능하다.  

 

재귀 함수는 계속 자신을 호출하는 방식을 사용하기 때문에 종료 구간인 Base Case를 정의해야 한다.

한번 아래의 예제를 살펴보자

 

재귀함수 예제 | Loop 

public class RecursionEx
{
    public static void main(String[] args)
    {
        Recursion();
    }
 
    public static void Recursion()
    {
        System.out.println("Nworld.dev");
        Recursion();
    }
}

// Output

Nworld.dev
Nworld.dev
Nworld.dev
...

 

블로그 주소를 무한 루프로 계속 돌고있다 그 이유는 계속 호출하고 있기 때문이다.

그래서 Base Case를 정해야한다

 

재귀함수 예제 | Base Case Set

public class RecursionEx
{
    public static void main(String[] args)
    {
        Recursion(10); // 출력될 수를 정해준다 
    }
 
    public static void Recursion(int limit) // 매개변수로 정수형 limit 선언
    {
        if(limit == 0) return; // 매개변수가 0이 된다면 루프를 종료한다
        System.out.println("Nworld.dev"); // 블로그 주소를 출력한다.
        Recursion(limit - 1); // 받아온 매개변수에서 1을 차감한다.
    }
}

// Output

Nworld.dev
Nworld.dev
Nworld.dev
...

 

정수 10을 메서드에 매개변수로 넣어주고 Base Case를 지정했으니

블로그 주소가 10변 출력될것이다 그 이유는 limit - 1 을 통해 limit이 0이 된다면 반복을 종료한다.

 

재귀 함수 응용 | 팩토리얼

// 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.
// 첫째 줄에 정수 N(0 ≤ N ≤ 12)이 주어진다.

import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
 
		Scanner input = new Scanner(System.in);
		
		int type = input.nextInt();
		input.close();
		
		int answer = factorial(type);
		System.out.println(answer);
		
	}
	
	public static int factorial(int type) {
		if(type <= 1) return 1;
		return type * factorial(type - 1);		
	}
 
}

백준예제 자바 팩토리얼 문제를 풀어보았다..