[알고리즘] 재귀 Recursion

재귀(Recursion)란? 

: 컴퓨터 과학에서 재귀란 자신을 정의할 때 자기 자신을 재참조하는 방법을 의미한다. 

 

재귀 함수(Recursion Function)란? 

함수에서 자기 자신을 다시 호출해 작업을 수행하는 방식

특정 분기까지 자기 자신을 계속해서 호출하는데, 주로 반복문을 구현할 때 사용한다. 

for, while 등의 반복문으로 구현가능한 로직은 모두 재귀함수로도 가능하고 그 반대 역시 가능하다. 

재귀함수의 가장 대표적인 사용 예제는 팩토리얼(Factorial)

 

재귀함수 공식

func 함수이름(매개변수) {
    if 종료조건 {
        return 종료값
    }
    return 점화식  //결과값을 받을 변수 = 함수이름(입력변수)
}

 

재귀함수 사용시 주의할 점

스택 오버플로우(stack overflow)를 주의해야 한다. 

함수가 멈추지 않고 무한대로 실행되는 것을 방지하기 위해 종료 조건을 반드시 명시해주도록 한다. 

 

재귀함수의 장단점

장점

코드가 짧아지고 내용도 직관적으로 파악할 수 있어 가독성이 높아진다는 장점. 

1. 변수를 여럿 만들 필요가 없다. 

현재 상태를 저장하기 위해 변수를 따로 만들기보다 메서드를 재귀적으로 호출하며 변경된 상태를 전달함으로써 변수의 수를 줄일 수 있다. 

2. while, for문 등의 반복문을 사용하지 않아도 되어 코드가 간결해진다.

단점

1. 지속적으로 함수를 호출하면서 지역변수, 입력값(매개변수), 결과값 등이 모두 스택이라는 데이터 저장 공간에 보관된다. 선언한 변수의 값만 사용하는 반복문에 비해 메모리를 더 많이 사용하게 되어 속도 저하가 일어날 수 있다. 무리하게 호출하면 스택 오버플로우가 발생할 수 있다.  

2. 함수 호출 -> 복귀를 위한 context switching 비용이 발생. 

 

따라서 이러한 재귀함수의 단점을 보완하는 방법 중 하나가 바로 '꼬리 재귀'

꼬리재귀 (Tail Recursion)

재귀 호출이 끝나면 아무 일도 하지 않고 결과만 바로 반환되도록 하는 방법

이렇게 하면 이전 함수의 상태를 유지하지도 않고 추가 연산을 하지도 않아서 스택이 넘쳐나는 문제를 해결할 수 있게 된다. 

꼬리 재귀 함수는 이름처럼 항상 함수의 마지막에서 실행되는데, return 되기 전에 값이 정해지며 호출 당한 함수의 결과값이 호출하는 함수의 결과값으로 반환된다. 

 

팩토리얼 풀이 비교

//반복문 사용
func factorial(_ num: Int) -> Int {
    var result = 1
    for i in 2...num {
        result *= i
    }
    return result
}
print(factorial(10)) //3628800

//일반 재귀 방식
func factorial(_ num: Int) {
    if n == 1 {
        return 1
    }
    return n * factorial(n-1)
}
print(factorial(10)) //3628800

//꼬리 재귀 방식
func factorial(_ num: Int, _ total: Int) -> Int {
    if num == 1 {
        return total
    }
    return factorial(num - 1, num * total)
}
print(factorial(10, 1)) //3628800

꼬리 재귀의 핵심은 반환부분에 연산이 없어야 한다는 점!

 

 

백준 - 재귀문제

재귀 단계

 

참고 : Catsbi's DLog-재귀함수, joooing-꼬리재귀,