재귀 함수는 언제 써야 할까?

문제제기

• 학원 수업 중 재귀적 호출이라는 개념이 나왔습니다.

  //사용된 코드
   Scanner in = new Scanner(System.in);
   char startChar;
   public void keyboardInputNameRecursive() {
      //Scanner in = new Scanner(System.in);
      System.out.print("이름?"); name=in.nextLine();
      startChar = name.charAt(0);
      
      if(startChar >= '0' &&  startChar <='9'  ) {
         System.out.println("다시입력해");
         keyboardInputNameRecursive();
      }
   }

• 재귀적 호출(Recursive call)란 일정 조건을 만족할 경우 자기 자신을 호출하는 것을 말합니다. 이를 구현한 것을 재귀 함수라고 하지요. 마치 반복문을 쓰는 듯한 느낌이 드는데, 반복문을 쓰는 것보다 효율이 더 좋아서 쓰는 것인가 하는 의문이 생겼습니다. 왜 쓰고, 언제 쓰면 좋을까요?

재귀 함수의 장점

• 먼저, 알고리즘 자체가 재귀적인 표현이 자연스러운 경우에는 재귀 함수를 쓰는 것이 큰 도움이 됩니다. 예를 들어 피보나치 수열과 같은 경우, 알고리즘을 기술한 그대로 코드로 표현할 수 있게 됩니다. 또한 점화식 스타일이나 분할정복 같은 경우도 마찬가지입니다.
• 두번째로, '변수 사용'을 줄여주어 mutable state가 취할 수 있는 경우의 수를 줄여주게 됩니다. 이는 변수의 수를 줄이는 것과 더불어 변수가 가질 수 있는 값의 종류 또는 범위를 정확히 제한하는 것입니다. 변수의 수를 줄이는 것은 재귀 호출이 도와주고, 변수가 가질 수 있는 값의 종류 또는 범위를 정확히 제한하는 것은 type system이 도와줍니다. 이로써 사이드 이펙트(side effect,부작용)가 없어지게 됩니다.
• 이는 함수를 단순하게 만들고, 불변적으로 유지될 수 있도록 만듭니다.

이럴 때는 쓰면 안된다

• 그러나 두번째 조건을 충족시키지 못한다면, 재귀 함수의 단점이 드러나게 됩니다. 다음의 재귀 함수를 함께 보겠습니다.

public class RecursiveCall2{
    
    public static void main(String [] args){
        int result = recursiveCall(5);
 		System.out.println(result);
    }
    
    public static int recursiveCall(int n) {
    	if(n == 1) {
            return n;
        } else {
            return n + recursiveCall(n-1);
        }
    }
}

• 위의 함수를 실행할 경우 결과는 나오게 되겠지만, 계속 함수를 호출 할 경우 함수의 매개변수, 지역변수, 리턴 값, 그리고 함수 종료 후 돌아가는 위치가 스택 메모리에 저장되면서 stack이 쌓이게 되는 문제가 발생할 수 있습니다. 이는 메모리를 많이 차지하며 스택오버플로우가 발생할 수도 있습니다. 또한 스택 프레임을 구성하고 해제하는 과정에서 반복문보다 오버헤드가 들어 성능도 느려지게 됩니다.

"입력값의 변화가 없거나 입력값의 변화가 특정 패턴을 반복하게 되면 그 재귀함수는 영원히 반복되다가 콜스택 초과로 프로그램이 뻗어 버린다. 꼬리 재귀 최적화가 적용된 알고리즘은 그냥 영원히 돌면서 프로그램이 멈춰 버린다. 따라서 재귀함수 설계 시에는 입력값이 종료 조건으로 수렴하는지를 꼭 검증해야 한다."

(출처: 나무 위키)

꼬리 재귀 최적화

• 두번째 조건을 충족시키기 위해서는 고려해야할 것은, 바로적절한 꼬리 재귀 최적화(TCO, tail call optimization)를 해야한다는 것입니다. 그렇다면 꼬리 재귀 최적화란 어떻게 하는 것일까요? 다음의 코드를 보겠습니다.

public class RecursiveCall2{
    
	public static void main(String [] args){
        int result = tailRecursive(5, 0);
 		System.out.println(result);
    }
    
	public static int tailRecursive(int n, int acc)
	{
 		if(n==1) {
        	return acc;
    	} 
 		return tailRecursive(n-1, n + acc );        
    }
}

• 함수에 인자를 하나 더 추가해서 최적화를 진행했습니다.
• 이 경우 stack frame을 재사용할 수 있고, 컴파일러가 이를 파악하여 반복문 형태로 만듭니다.(컴파일러에 따라 다를 수 있습니다.)
• 따라서 재귀함수를 사용해야 할 경우라면, 꼬리재귀 최적화를 해서 하는 것이 좋습니다. 그게 아니라면 반복문을 사용하는 것이 더 나은 선택이 될 수 있을 듯 합니다.

"반복문으로 변수를 바꿔가는 형식의 명령형 계산은 항상 재귀적인 형식으로 똑같이 구현할 수 있으며 그 반대도 마찬가지지만, 현재 산업에서의 언어 패러다임은 대부분 명령형이기 때문에 대개 반복문으로 구현하는게 훨씬 익숙할 것이다. 무엇보다 함수가 호출될 때마다 호출 스택 메모리를 잡아먹는 경우 퍼포먼스 측면에서 반복문이 낫다.

다만 구현체에 꼬리재귀(Tail Recursion) 최적화가 되어있는 경우 꼬리재귀 요청이 스택에 걸리는 대신 이전 실행지점으로의 점프로 작동 하므로 실질적으로 루프문과 유의미한 성능 차이는 없게 된다.꼬리재귀 최적화의 경우 함수형 언어 구현체에는 필수적으로 들어가며, 명령형 언어 컴파일러에도 구현되어 있는 경우가 있다"

(출처: 나무위키)

• 기타 관련 내용(나무위키)

  "대부분의 명령형 언어 구현체에서는 간단한 재귀함수를 몇 줄 차이뿐인 반복문으로 쓰는 것이 더 좋은 관계로 절차적 언어에서의 재귀를 써야하는 경우는 매우 적다. 더불어 명령형 언어 사용자들이 재귀를 꺼리게 되는 추가적인 이유는 이게 반복을 하는 놈인지 아닌지 알기 어렵다는 점에 있다. 반복문이 대놓고 문장 한가운데서 '이 블록은 반복될 것임'하고 알려주는 것과 다르게 재귀는 별다른 표시없이 혼자 돌게 되므로 코드 내에서 가독성이 떨어지게 된다. 추가적으로, 흐름을 추적하기 어렵다는 이유도 한몫한다."

  "그렇지만 명령형 언어에서도 재귀가 필요할 때가 있는데, 반복문으로 구현했다가는 코드가 심하게 복잡해지거나, 프로그래머가 만들다가 로직이 꼬여 안드로메다로 가는 상황이 발생하는 문제들도 있기 때문. 이 경우 재귀함수로 구현하는 것이 간단하고 훨씬 더 이해하기 쉬운 경우가 있다. 예를 들어 XML이나 JSON을 파싱한다거나 퀵 정렬을 만든다면 반복문보다 재귀를 쓰는 것이 더 쉽다. 이런 알고리즘을 생 루프문으로 처리하려면 스택을 따로 구현해야 한다."

  "하지만 소프트웨어 위기와 병렬 컴퓨팅에 대두에 따라, 함수를 최대한 단순하게, 불변적으로 유지하는 것이 새로운 패러다임으로 떠올랐다. 수많은 함수형 언어들이 등장하는 것과 관련이 있다. 그에 따라 재귀함수 등의 함수형 사고를 통해 프로그래밍을 하는 것이 중요한 덕목 중 하나로 떠올랐다."

  "혹 명령형 언어에서 재귀함수를 퍼포먼스가 떨어진다고 안 쓰는 게 좋다고 가르치기도 한다. 그러나 꼬리재귀 호출을 할 수 없으면서 스택 깊이 이상을 뚫어버리는 경우가 아니면 굳이 거부할 필요는 없다. 오히려 의미상 더 명료하다면 신용하는 게 나을 수 있다. 요즘 컴파일러들은 아주 똑똑해서 재귀 호출 최적화를 잘한다."

  "그러나 아무리 꼬리재귀 최적화가 완벽히 되더라도 정말 특수한 경우가 아니라면 콜스택 문제가 아예 없어지는 것은 또 아니고, 캐쉬 지역성 문제로 인해 성능이 떨어지는 것은 맞다. 단지 그 차이가 유의미하지 않을 뿐. 이런 식의 유연성과 성능의 trade-off는 프로그래밍에서는 일상이고, 개발 목적에 맞는가, 허용 범위 내인가가 더 중요하다. 성능을 극한까지 쥐어짜는 게 목적이라면 재귀를 멀리하고, 아니라면 필요할 때 쓰면 되는 것이다.

• 출처
  • https://kldp.org/node/134556
  • https://ggodong.tistory.com/115
  • https://medium.com/sjk5766/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98%EB%A5%BC-%EC%93%B0%EB%8A%94-%EC%9D%B4%EC%9C%A0-ed7c37d01ee0
  • https://namu.wiki/w/재귀함수#rfn-1
  • 컴파일러를 통해 재귀 함수를 분석한 글도 있습니다. https://bozeury.tistory.com/entry/%EA%BC%AC%EB%A6%AC-%EC%9E%AC%EA%B7%80-%EC%B5%9C%EC%A0%81%ED%99%94Tail-Recursion?category=826469