[컴퓨터 과학] 재귀 함수란?

재귀 함수란?

재귀 함수란 함수가 직접 또는 간접적으로 자신을 호출하는 프로세스이다.재귀 알고리즘을 사용하면 탐색, GCD (최대공약수) 등 복잡한 문제들도 간단하게 해결할 수 있다.

 

단, 반복문과 같이 재귀함수도 종료지점을 제대로 정하지 않고 구현을 하면 스택 오버플로우가 발생하므로 항시 주의해서 구현을 해야 한다.

 

재귀함수는 보통 피보나치수열, 팩토리얼 연산과 같이 재귀적 사용이 자연스러울 때 사용한다.

---

재귀 함수 예제 1

public class PlusFunction {
	public static void main(String[] args)  {
		HelloWorld(5); // HelloWorld 출력 메서드 호출
	}
	
	// HelloWorld 출력 메서드 선언
	public static void HelloWorld(int n)
	{
		// n이 0인 경우 return
		if(n == 0)
			return;
		
		System.out.println("HelloWorld"); // HelloWorld 출력
		HelloWorld(n-1); // 재귀함수 시작
	}
}

 

"Hello World"를 반복출력하는 재귀함수이다. n이 0이 될 때 메서드를 끝내고, 함수를 호출 할 때마다 n-1을 해서 재귀함수를 종료하게 만든다.

---

재귀 함수 예제 2

public class FibonacciFunction {
	public static void main(String[] args)  {
		int n = 10;
		
		for(int i = 0; i < n; i++) // 피보나치 수열 출력
			System.out.print(Fibonacci(i) + " ");
	}
	
	// 피보나치 수열의 결과를 구하는 메서드 선언
	public static int Fibonacci(int n)
	{
		if(n == 0)
			return 0;
		
		if(n == 1 || n == 2)
			return 1;
		
		else 
			return Fibonacci(n - 1) + Fibonacci(n - 2);
	}
}

 

피보나치 수열은 1, 1, 2, 3 , 5, 8, 13 ... 처럼 N = (N - 1) + (N -2) 가 계속해서 나오도록 하는 수열이다.

---

스택 오버플로우 발생 예제

int factorial(int n) { 
    if (n === 1) { 
        return 1; 
    } 
    return n * factorial(n-1);
}

 

재귀함수의 대표적인 사용예제, 팩토리얼이다. 인자로 5를 넣는다면 5 * 4 * 3 * 2 * 1 이 실행된다.

 

 

위에서 작성한 예제에서 factorial에서 if(n===1)이 빠진다면 아래와 같은 코드가 나온다.

int factorial(int n) { 
    return n * factorial(n-1);
}

n이 1일 경우 멈춰야 하는 해당 함수는 이제 멈추지 않고 -1, -2, -3, .... n까지 무한대로 실행되게 되는데, 사실상 컴퓨터의 메모리에는 한계가 있으니 무한대는 불가능하고 스택 오버플로우 문제가 발생하게 된다.

---

스택 오버플로우 발생하는 이유

재귀 호출에 의한 스택 프레임의 쌓임

재귀 호출이 무한히 반복되면, 재귀 호출에 의한 스택 프레임이 계속해서 쌓여간다.

이렇게 스택의 모든 공간을 다 차지하고 난 후, 더 이상의 여유 공간이 없을 때 또 다시 스택프레임을 저장하게 되면 해당 데이터는 스택 영역을 넘어가서 저장되게 된다.

해당 스택 영역을 넘어가도 데이터가 저장될 수 있으면 해당 프로그램은 오동작을 하게 되거나 보안상의 크나큰 취약점을 가지게 된다. (예: 스택 버퍼 오버플로우)

 

따라서 C언어에서는 실행 중인 프로그램에서 스택 오버플로우가 발생하면 에러를 발생하고 곧바로 강제종료시킨다.

---

재귀의 장점과 단점

장점

1. 변수를 여럿 만들 필요가 없다. 현재 상태를 저장해야 할 경우, tmp 변수를 만들기보다 메서드를 재귀적으로 호출하면서 변경된 상태를 전달하여 변수의 수를 줄일 수 있다.
2. while문,  for문 같은 반복문을 사용하지 않아도 되므로 코드가 간결해진다. (예: 하노이의 탑)
3. 이해하기 쉽다.

단점

1. 지속적으로 함수를 호출하게 되면서 지역변수, 매개변수, 반환값을 모두 process stack에 저장해야 한다. 그리고 이런 과정은 선언한 변수의 값만 사용하는 반복문에 비해서 메모리를 더 많이 사용하게 되고, 이는 속도 저하로 이어진다.
2. 함수 호출 -> 복귀를 위한 컨텍스트 스위칭에 비용이 발생하게 된다.
3. 시간 복잡도가 반복문에 비해 계산이 어렵다.
4. 함수 호출을 많이 하기에 스택오버플로우의 가능성이 있다.

 

---

꼬리 재귀

일반 재귀함수의 단점을 개선한 꼬리재귀가 있다. 꼬리 재귀는 재귀 호출 이후 추가적인 연산을 요구하지 않도록 구현한다.

이런 꼬리 재귀 함수는 콜 스택이 추가로 생성되지 않는다. (원래라면 함수를 호출할 시 콜스택이 생성된다.)

 

그러나, 컴파일러가 꼬리재귀최적화 (TCO, Tail Call Optimization)를 지원해줘야 한다. 컴파일러가 지원하지 않는다면 꼬리 재귀같이 보이게 설계하더라도 일반 재귀처럼 돌아간다.

C++, C#, Kotlin, Swift, JavaScript(ES6 스펙), Scala 에서는 꼬리재귀최적화를 지원하지만, java는 직접적으로 꼬리재귀최적화를 지원하지 않는다고 한다.

 

---

출처

1. https://crazykim2.tistory.com/591 - [JAVA] 재귀함수(Recursion Function) 개념 및 예제
2. https://catsbi.oopy.io/dbcc8c79-4600-4655-b2e2-b76eb7309e60 - 재귀함수의 장점과 단점 그리고 해결책
3. https://velog.io/@osk3856/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98-%EC%9E%A5-%EB%8B%A8%EC%A0%90-%EB%B0%8F-%EA%BC%AC%EB%A6%AC%EC%9E%AC%EA%B7%80 - 재귀함수 장, 단점 및 꼬리재귀