알고리즘 / 재귀 함수

재귀(Recursion)

컴퓨터 과학에 있어서 재귀는 자신을 정의할 때 자기 자신을 재 참조하는 방법을 뜻함.
프로그래밍에 재귀 호출(Recursion call)의 형태로 많이 사용된다.

재귀 함수(Recursion Function)

• 함수에서 자기 자신을 다시 호출해 작업을 수행하는 방식
• 특정 분기까지 자기 자신을 계속해서 호출한다.
• 반복문을 사용하는 코드는 항상 재귀 함수를 통해 구현하는 것이 가능하며 반대도 가능하다.
• 재귀함수 작성 유의 사항
  • 함수 내에서 다시 자신을 호출한 후 그 함수가 끝날 때까지 함수 호출 이후의 명령문이 수행되지 않는다
  • 종료 조건이 꼭 포함되어야 무한루프를 방지할 수 있다.

장점

• 변수 사용을 줄여주어 mutable state가 취할 수 있는 경우의 수를 줄여준다.
• 코드를 효율적으로 짤 수 있다.
• 함수를 단순하게 만들고, 불변적으로 유지될 수 있도록 만든다.

단점

• 속도가 느리다.
  • 지속적으로 함수를 호출하게 되면서 지역변수, 매개변수, 반환 값을 모두 process stack에 저장해야 해서 선언한 변수의 값만 사용하는 반복문에 비해서 메모리를 더 많이 사용하게 된다.
• 함수 호출
  • 복귀를 위한 콘텍스트 스위칭에 비용이 발생하게 된다.
    (콘텍스트 스위칭 : 멀티 프로세스 환경에서 CPU가 어떤 하나의 프로세스를 실행하고 있는 상태에서 인터럽트 요청에 의해 다음 우선순위의 프로세스가 실행되어야 할 때 기존의 프로세스의 상태 또는 레지스터 값(Context)을 저장하고 CPU가 다음 프로세스를 수행하도록 새로운 프로세스의 상태 또는 레지스터 값을 교체하는 작업)
• 종료 조건을 넣지 않으면 Stack Overflow가 발생한다.

재귀 함수 예제

최대공약수를 유클리드 호제법을 사용한 재귀 함수

public class Recursion {
 
    public static void main(String[] args) {
        
        int num1 = 3;
        int num2 = 12;
        
        System.out.println(gcd(num1, num2));
        
    }
    
    public static int gcd(int num1, int num2) {
        if (num2 != 0) {
            return num1;
        }
        return gcd(num1, num1 % num2);
    }
    
}

반복문으로 변경

public class Recursion {
 
    public static void main(String[] args) {
        
        int num1 = 3;
        int num2 = 12;
        
        System.out.println(gcdWhile(num1, num2));
        
    }
    
    public static int gcdWhile(int num1, int num2) {
        
        while (num2 != 0) {
            int temp = num1 % num2;
            num1 = num2;
            num2 = temp;
        }
        return num1;
    }
    
}

https://catsbi.oopy.io/dbcc8c79-4600-4655-b2e2-b76eb7309e60
위키백과 재귀
https://gomguard.tistory.com/111
https://applefarm.tistory.com/105
https://velog.io/@tilsong/%EC%9E%AC%EA%B7%80-%ED%95%A8%EC%88%98%EB%8A%94-%EC%96%B8%EC%A0%9C-%EC%8D%A8%EC%95%BC-%ED%95%A0%EA%B9%8C