재귀

---

---

반복과 재귀

 

• 반복과 재귀는 유사한 작업을 수행 할 수 있다.
• 반복은 수행하는 작업이 완료될때 까지 계속 반복
• 재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용하는 방법

 

재귀

• 어떠한 개념이나 문제에 대한 정의를 내리는 것
• 그 개념이나 문제를 포함하는 작은 개념이나 부분문제로 나타내고
• 더이상 작은 개념, 부분문제가 없는 상황 까지 반복
• 자신만의 상태 보존 가능

반복문(for)

• 반복의 결과의 상태를 저장 불가
• 각각의 반복마다 상태를 유지하기 힘듬
• "단위 반복"이 중요

---

재귀 함수

 

재귀 함수란?

함수 내부에서 '자기 자신을 호출' 하는 함수를 의미한다. 이를 통해 함수가 자신을 반복적으로 호출하며서 원하는 결과를 도출할 수 있다. => 호출 스택에 쌓인다.

 

호출 스택 이란?

여러 함수들(functions)을 호출하는 스크립트에서 해당 위치를 추적하는 인터프리터를 위한 메커니즘이다. 현재 어떤 함수가 실행중인지, 그 함수 내에서 어떤 함수가 호출되어야 하는지, 등을 제어한다.

 

---

재귀 예시

 

팩토리얼(!)

public class Factorial {
    public static void main(String[] args) {
        int input = 4; 
        System.out.println(fact(input));
}	

public static int fact(int n) {
    if (n <= 1)			
        return n;		
    else 			
        return fact(n-1) * n;
    }
}

 

위의 코드를 보면 fact 메서드 안에서  n이 1일때 까지 자기 자신을 호출하는 재귀를 볼 수 있다

 

재귀적 정의

Basis rule :

• N <= 1 경우, n = 1

inductive rule :

• N > 1, N! = N * (N - 1)!

<재귀 호출 과정>

 

4! 계산 과정

1. fact(4)에서 fact(3)을 호출 한다
2. fact(3)에서 fact(2)을 호출 한다
3. fact(2)에서 fact(1)을 호출 한다
4. fact(1)은 1을 리턴한다.
5. fact(2)는 자기 자신의 값과 리턴값을 곱해서 리턴한다.  :  2
6. fact(3)는 자기 자신의 값과 리턴값을 곱해서 리턴한다.  :  6
7. fact(4)는 자기 자신의 값과 리턴값을 곱해서 리턴한다.  :  24

---

재귀 장단점

 

장점

• 변수를 여럿 만들 필요가 없다. => 현재상태를 재귀적으로 호출 하면서 변경된 값 전달
• 반복문을 사용하지 않기에 코드가 간결 해진다.

단점

• 메모리를 많이 쓴다.
• 함수 호출 -> 복귀를 위한 컨텍스트 스위칭에 비용이 발생