재귀 함수 (Recursion)

재귀

• 반복 => 단위 반복 찾기 
• 재귀 => 같은 처리 단위 찾기 
• 하나의 큰 문제를 해결할 수 있는(해결하기 쉬운) 더 작은 문제로 쪼개고, 결과들을 결합
• 재귀 함수로 구현

 

재귀 함수 

• 함수 내부에서 직접 혹은 간접적으로 자기 자신을 호출하는 함수 
• 일반적으로 재귀적 정의를 이용해서 재귀함수 구현
• 기본 부분(Basic part) & 간접 부분(Inductive part)로 구성
• 재귀적 프로그램 작성이 반복 구조에 비해 간결 & 이해가 쉬움
• 함수 호출은 프로그램 메모리 구조에서 STACK(스택) 사용
• 재귀 호출은 반복적인 스택의 사용을 의미, 메모리 및 속도에서 성능 저하 --> stack overflow

 

Factorial (팩토리얼) 재귀 함수 

팩토리얼: 그 수보다 작거나 같은 모든 양의 정수의 곱

팩토리얼의 재귀적 이해를 돕기 위한 식 풀이

 

public class Factorial{

	private static int ans = 1;
    
    public static void main(String[] args){
        fact1(5);
        System.out.println(ans);
        System.out.println(fact2(5));
        
    }
    
    //static 변수에 대한 의존이 있어서 그래 좋은 코드는 아님
    //계속 바뀌는게 매개 변수의 결정 요인 매개체 n을 매개변수로 받아옴
    private static void fact1(int n){
    	//끊어 주는 조건
        if(n == 0)
        	return;
        ans *= n;
        fac1(n-1);
    }
    
    private static int fact2(int n){
    	//끊어주는 부분 생각
        if(n<=1) return 1;
        //return 값을 호출하는 재귀 
        return n * fact2(n-1);
    }
    
}

fact라는 팩토리얼 함수 호출 스택

 

 

반복문으로 나타내 본다면

private static int fact3(int n){
	//누적 곱을 위한 변수
    int res = 1;
    //계속 곱하는 모습을 만들기 위해서 res를 맨 처음에 곱함
    for(int i = n; i>=1; i--){
    	res *= i;
    }
    return res;
}

 

---

출처

https://ko.wikipedia.org/wiki/%EA%B3%84%EC%8A%B9