재귀함수

서정한·2023년 6월 2일

꼬리 재귀 알고리듬 재귀

알고리듬 공부

목록 보기

3/15

재귀란?

재귀(Recursion)란 큰 문제를 반복 적용가능한 작은 문제로 쪼개서 해결하는 것.

알고리듬에서의 재귀함수 위치

재귀함수는 대부분의 알고리듬문제에서 사용된다. 그리고 재귀함수는 컴퓨터적 사고를 배우는데 필요하다.

재귀함수의 예

피보나치 수열

fun fibonacci(number: Int) : Int {
	if(number <= 1) return number
    
    return fibonacci(number - 2) + fibonacci(number - 1)
}

팩토리얼

fun factorial(number: Int) : Int {
	if(number == 0) return 1
    return number * factorial(number - 1)
}

하노이의 탑 등..

재귀함수의 사용

재귀함수는 탈출조건이 있는 경우에만 사용할 수 있습니다.
탈출조건이란 문제를 아주 작게 쪼갰을 때 한번에 답이 나오는 것 을 탈출조건이라고 합니다.
만약 탈출조건을 찾을 수 없다면 당연한 이야기이지만 재귀함수는 무한루프에 빠지게 됩니다.
탈출조건을 작성하면 그 다음으로 재귀 조건을 정합니다.
재귀 조건은 다른 값에 대한 같은 함수를 계산하는것 을 말합니다.

재귀함수의 연산과정

fibonacci(4) 를 계산한다고 했을 때

fibonacci(4) = fibonacci(2)+fibonacci(3)
fibonacci(3) = fibonacci(1)+fibonacci(2)
fibonacci(2) = fibonacci(0)+fibonacci(1)

의 과정을 수행한다. fibonacci(0) = 0 이고, fibonacci(1)은 1이기때문에
fibonacci(2) = 0+1 = 1 이 된다.
이어서

fibonacci(3) = 1( fibonacci(1) ) + 1( fibonacci(2) ) = 2
fibonacci(4) = 1( fibonacci(2) ) + 2( fibonacci(3) ) = 3

의 과정을 거쳐 결론을 도출하게 된다.

재귀함수의 장단점

장점

가독성이 좋다.
코드가 짧아짐.
각 단계의 변수상태가 자동저장됨(함수의 스택프레임 덕분 스택프레임이란?)
코드 검증도 쉬움

단점

재귀적 문제 분석/설계가 직관적이지 않음.
맹목적인 믿음이 필요.(수학적 귀납법을 이해하면 믿음이 생김..!)
스택오버플로우 발생가능(재귀함수 호출이 너무 깊을경우)
함수호출에 따른 과부하
- 가령 A함수에서 B함수를 호출한다면 스택프레임에 B함수를 추가해야한다. 그리고 A함수의 정보를 저장도 해야하고 B함수의 매개변수등도 저장해야한다. B함수가 동작 후 return 할 때에는 위에서 설명한 역순으로 진행된다.(함수호출시 어셈블리어로 어떻게 진행되는지 제가 대략적으로 이해된 내용을 간략히 정리해보았습니다..! 자세한 내용은 함수호출과 메모리반환 개념)

꼬리 재귀

꼬리 호출(tail call)

함수 코드 제일 마지막에서 다른 함수를 호출하는 경우
그 후 실행하는 명령어가 없음.
스택프레임의 존재목적은 다른 함수에서 사용중인 변수값을 유지하기 위해서임.
but, 꼬리호출의 경우 다른 함수로부터 반환 후 더이상 연산이 없기에 스택프레임을 유지할 이유가 없다.
컴파일러가 스택프레임을 만들지않는 최적화를 하기도 한다.
- 꼬리 호출 제거(tail call elimination)
- 꼬리 호출 최적화(tail call optimization)

꼬리 재귀(tail recursion)

호출하는 함수가 내 자신인 경우 꼬리호출과 똑같은 최적화가 적용됨.
예시- 팩토리얼 재귀함수.

fun factorial(number: Int) : Int {
	if(number == 0) return 1
    return number * factorial(number - 1)
}

위의 팩토리얼은 꼬리 재귀가 아니다. 왜냐하면 마지막 함수호출 후 프로그램이 종료되지 않고 최종적으로 number과 곱해야하기때문이다. 이 말은 최종계산에서 number가 무엇인지를 알고있어야하기에 stack에 저장되어있어야 한다는 것이다.

fun factorial(number: Int): Int{
	return factorialRecursive(number, 1)
}

fun factorialRecursive(number: Int, fac: Int): Int{
	if(number <= 1) return fac
    
    return factorialRecursive(number-1, number * fac)
}

재귀함수와 꼬리재귀의 차이는 무엇일까? 바로 마지막 명령어로 함수가 끝난다는 것이다. 위의 코드를 살펴보면 factorialRecursive에서 fac이라는 매개변수를 새로 만들어주고 1을 넣어줬다. 이를 통해 원래 재귀함수에서 마지막에 알고있어야할 number를 더이상 다른곳에 저장할 필요가 없게되었다.
factorial(5)를 실행하면.
factorial(5) = factorialRecursive(5, 1)
factorialRecursive(5, 1) = factorialRecursive(4, 5)
factorialRecursive(4, 5) = factorialRecursive(3, 20)
factorialRecursive(3, 20) = factorialRecursive(2, 60)
factorialRecursive(2, 60) = factorialRecursive(1, 120)
factorialRecursive(1, 120) = 120
이 된다.
위 실행과정을 살펴볼 때 호출한 함수는 그 즉시 실행후 결과를 리턴한다. 즉, 굳이 스택에 다른 함수의 매개변수등을 저장할 필요가 없어져버린 것이다.

본 내용은 Udemy의 알고리듬 및 자료구조(Java)강의를 듣고 정리한 내용입니다.