재귀함수, 꼬리재귀

안녕하세요. KataRN입니다.

 

재귀함수.gif

여러분 재귀함수를 아시나요?

재귀함수... 어렵게 생겼지만 어렵지 않습니다.

 

재귀함수에 대한 이해를 돕기위해 우선 나무위키에서 퍼온 내용을 보시죠

어떻습니까? 멀티탭을 사용하기위해 멀티탭에 멀티탭코드를 꽂아서 사용하는... 멀티탭을 쓰기위해 멀티탭을 통해 전기를 가져오고 그 전기는 멀티탭에서 그 멀티탭의 전기는 멀티탭에서... 도르마무... 거래를 하러왔다...

 

하하..다시 이야기로 돌아가서 멀티탭을 사용하기 위해.. 도르마무...

죄송합니다.

 

다른 내용을 보도록하죠.

결과를 얻기위해 함수속에 함수(자신)을 넣는 것입니다.

 

가장 쉬운 예제는 팩토리얼입니다.

함수로 예를 들겠습니다.

import Foundation

func factorial(_ n : Int) -> Int {
    guard n > 0 else { return 1 }
    return n * factorial(n - 1)
}

factorial(3)
//6

<factorial> 함수 안에 <factorial>이 있죠?

n이 1이 될때까지 <factorial>의 함수를 계속 호출합니다.

 

이렇게 계속 호출하다보면 메모리를 많이 차지하게 됩니다. 그래서 성능이 반복문에 비해 느립니다.

(함수를 호출 시 함수의 매개변수, 지역변수, 리턴 값 그리고 함수 종료 후 돌아가는 위치가 스택 메모리에 저장된다.)

재귀 함수를 사용하면 함수를 반복적으로 호출하므로 스택 메모리가 커지고, 호출하는 횟수가 많아지므로 스택오버플로가 발생할 수 있습니다.

코테에서도 반복문으로 작성하면 통과되는데 비해 재귀함수를 사용하면 대부분 시간초과가 뜹니다. 코드가 상대적으로 깔끔할지라도 성능적으로 효율성이 떨어진다는 이야기죠.

 

그래서 등장한 방법이 있습니다.

그것은 바로 꼬리재귀입니다.

 

꼬리 재귀는 기존의 재귀 함수의 문제를 해결할 수 있는 방법입니다.

1. 프로그래머가 재귀 함수를 꼬리 재귀 방식으로 만들어야 한다.
2. 컴파일러가 꼬리 재귀 최적화를 지원해야 한다.

즉 컴파일러가 꼬리 재귀 최적화를 지원하지 않으면, 개발자가 꼬리 재귀 방식으로 개발해도 성능 및 메모리의 이점을 얻을 수 없습니다.

(컴파일러가 꼬리 재귀를 최적화할 수 있으면 최적화하는 과정에서 꼬리 재귀를 반복문으로 변경하기 때문에 성능에 대한 이슈가 해결됩니다.)

참고로 swift는 꼬리재귀 최적화를 지원합니다.

 

일반적인 재귀 함수는 return연산이 필요하지만 꼬리 재귀는 return 연산이 필요 없습니다. 매개변수로 필요한 연산을 전달합니다.

꼬리재귀를 사용한 팩토리얼을 확인해보겠습니다.

func factorial(_ n: Int) -> Int {
    func factorial(_ index: Int, _ answer : Int) -> Int {
        if index == 1 {
            return answer
        }
        return factorial(index - 1, answer * index)
    }
    return factorial(n, 1)
}

코드가 같은느낌이 들지만 다릅니다.

그럼 이번엔 피보나치 수열로 예를 들어보겠습니다.

.앞의 두 항을 더한 것을 다음 항으로 하는 수열입니다.

func fib(_ n: Int) -> Int {
    if n == 0 { return 0 }
    if n == 1 { return 1 }
    return fib(n-1) + fib(n-2)
}

fib(6)
//8

 

피보나치 5를 부르면 4, 3을, 숫자가 줄어들수록 중복된 호출이 늘어납니다.

실제로 피보나치에 100을 넣으면 실행 속도가 매우 늘어나므로 꼬리재귀로 바꿔보겠습니다.

 

func fib(_ n: Int) -> Int {
    func fib(_ a: Int, _ b: Int, _ n: Int) -> Int {
        if n == 0 { return a }
        return fib(b, a+b, n-1)
    }
    return fib(0,1,n)
}

fib(6)
//8

3개 인자를 받아서 n이 0이면 a를, 아니면 피보나치에 b, a+b, n-1을 넣어서 하나씩 줄여나가면서 값을 더합니다.

이 경우 3번째 인자의 숫자는 계속 줄어들고, 이것이 0이 되면 반환하도록 했습니다.

100을 넣더라도 100번만 실행되므로 스택 오버플로가 발생할 위험이 없습니다.

 

꼬리재귀 머리속에 넣어둡시다.

오늘도 읽어주셔서 감사합니다.

 

점화식을 풀때 기억시키는 아래 방법도 참고하세요.

func solution(_ n:Int) -> Int {
    var save: [Int: Int] = [:]
    save[0] = 0
    save[1] = 1
    save[2] = 2
    func check(_ n:Int) -> Int {
        if save.keys.contains(n) {
            return save[n]!
        }
        save[n] = (check(n-2) + check(n-1)) % 1234567
        return save[n]!
    }
    let result = check(n)
    return result
}

 

참고 : https://academy.realm.io/kr/posts/swift-tail-recursion/