[알고리즘] 재귀(Recursive)

 재귀(recursive)란, 사전적 의미로 '원래의 자리로 되돌아가거나 되돌아'을 의미한다. 컴퓨터 과학에서는 자신을 정의할 때 자기 자신을 재참조하는 방법을 말한다.

 

 즉, 함수에서 자기 자신을 다시 호출해서 작업을 수행하는 것인데 주로 반복문을 구현할 때 사용한다.

 

 예를 들어, n 이라는 정수를 입력 받아서 0 ~ n 까지의 모든 정수의 합을 구한다면 다음과 같이 코드를 만들 수 있다.

public class Example {
    public int sumTo(int n){
        if (n < 1) {
            return 0;
        }
        return n + sumTo(n - 1);	// 재귀 함수 시작
    }
}

 

 위 코드에서 n이 5라면 if문을 패스하고 5 + sumTo(n - 1)이 실행될 것이다. 여기서 sumTo(n-1)은 다시 4 + sumTo(n-1) ...

1 + sumTo(0)이 되면서 리턴된다. 결국 5 + 4 + 3 + 2 + 1 + 0이 되면서 15라는 값이 나온다.

 

 

 

 

재귀 함수의 장점

 

1. while문이나 for문 같 반복문을 사용하지 않아도 되기 때문에 코드가 간결해지고 수정이 용이하다.
   
   
2. 변수를 여러 개 사용할 필요가 없다.

 

 

 

 

재귀 함수의 단점

 

1. 코드의 흐름을 직관적으로 파악하기 어렵다.
2. 메서드를 호출하고 메서드가 종료된 이후에 복귀를 위한 컨텍스트 스위칭에 비용이 발생하게 된다.
   
   
3. 지속적으로 함수를 호출하게 되면서 지역변수, 매개변수, 반환값을 모두 process stack에 저장해야 한다. 이는 선언한 변수의 값만 사용하는 반복문에 비해 메모리를 더 사용하게 되므로 속도가 저하될 수 있다.

 

 

 

 

StackOverflowError

 만약 위 코드에서 if (n < 1) 이라는 코드가 빠지면 sumTo 함수는 무한대까지 계속해서 실행될 것이다.

0, -1, -2... -9998 -9999 ....

 

 인텔리제이에서 실행시켜보면 아래와 같은 에러가 발생한다.

StackOverflowError

 이는 무한 루프라고도 부르고 일반적으로 프로그램 충돌이 발생하게 된다. 컴퓨터의 메모리는 한계가 있기 때문에 무한대까지 연산은 불가능하기 때문이다.

 

 따라서, 재귀 호출이 종료되는 시점이 존재해야 한다.