java/ 재귀 함수 Recursive Function

재귀 Recursion

함수가 자기 자신을 호출하는 과정

 

---

e.g. 자연수 n을 입력 받아 1부터 n까지의 합을 구하기

1. for문을 사용

지금껏 사용해 온 for문으로 변수 sum을 선언해주고,

1부터 시작해 입력 받은 n과 같아질 때까지 1씩 증가시키면서 sum에 더하는 방식으로 구할 수 있다. 

static int sumUsingLoop(int n){
    int sum = 0;
    for(int i=1; i<=n; i++) sum+=i;
    return sum;
}

 

이 경우를 식으로 나타내면 다음과 같다.

f(n) = 1 + 2 + 3 + ... + n

 

 

---

2. 재귀 함수를 사용

이를 재귀 함수를 이용한 방식으로 나타내면 다음과 같다.

 

f(1) = 1
f(n) = n + f(n-1)

 

이 경우 n=4의 값이 들어올 때 식은 다음과 같이 진행된다.

f(4) = 4 + f(3)
	f(3) = 3 + f(2)
		f(2) = 2 + f(1)

차례로 자기 자신을 호출해가다가 f(1)을 만나는 순간 f(1)=1이 반환되어 함수는 종료되고, f(4)의 값은 다음과 같이 구할 수 있다.

f(4) = 4 + 3 + 2 + f(1)
f(4) = 4 + 3 + 2 + 1 = 10

지금까지 작성한 식을 바탕으로 java 코드를 작성해본다.

static int sumUsingRecursion(int n){
    //f(1) = 1
    if(n==1) return 1;
    //f(n) = n + f(n-1)
    return n + sumUsingRecursion(n-1);
}

이와 같이 함수 안에서 자기 자신을 다시 호출하는 식으로 사용되는 함수를 재귀 함수라고 한다.

 

---

 재귀 함수 작성을 위한 가이드라인

 

* 재귀 함수는 주어진 문제를 하나 이상의 더 작은 문제로 쪼개어 작성할 수 있을 때 사용한다.
* 재귀를 멈추는 하나 이상의 base case가 작성되어야 한다.

 

e.g. 자연수 n을 입력받아 1씩 감소시키며 1까지 출력하는 printNum 메서드 작성하기

 

1. 재귀 함수에서 사용할 입력값과 출력값을 정한다

e.g.  

//input : int n
//output : void

 

---

2. 풀고자 하는 문제를 base case와 recursive case로 나눠본다.

 

• base case: 재귀를 멈추는 조건으로 반드시 하나 이상이 작성되어야 한다
  • 재귀 함수 호출을 반복하다가 base case에 도달하는 경우, 재귀는 중지되고 흐름은 재귀 함수가 호출되었던 곳에서 이어진다
  • base case가 정의되지 않았거나 base case에 도달할 수 없는 경우 stackoverflow가 발생한다
• recursive case: 재귀 함수 호출으로 해결할 부분으로, 더 작은 문제로 나눠질 수 있는 부분이다.

 

e.g.

• base case

n을 받아 1씩 감소하면서 출력하다가 n가 1보다 작아지는 경우, 즉 printNum(0)이 호출되는 경우 재귀가 중지되어야 한다.

//base case : if(n==0) return;

• recursive case

[n, n-1, n-2, ..., 1]은 [n + (n-1, n-2, ..., 1)]과 동일하다. 따라서 n을 1씩 감소시키면서 재귀 함수를 호출한다.

//recursive case : printNum(n-1);

 

---

3. 코드 작성

 

e.g.

void printNum(int n){
    //base case
    if(n==0) return;
    System.out.printf("%d ", n);
    //recursive case
    printNum(n-1);
}

 

n=5가 입력으로 주어진 경우
printNum(5)에서 재귀 함수로 printNum(4) + printNum(3) + printNum(2) + printNum(1) 까지 차례로 호출되다가
printNum(0)이 들어오는 순간 if문의 조건에 걸려 return문을 만나 처음의 메서드가 종료된다.

 

---

 

 

즉 재귀 함수는 함수 안에서 자기 자신을 다시 호출하는 함수를 말하고,

재귀는 base case를 먼저 정의하고 base case에 도달할 때까지 큰 문제를 더 작은 문제로 나눠가는 과정이라고 할 수 있다.

 

reference.

Recursion - GeeksforGeeks