알고리즘 특강 Week6: 재귀함수 + [Baekjoon] # 10872 팩토리얼 변환

코딩테스트에서 정말 자주 활용되는 재귀함수에 대하여 정리하고자 한다.

실무적으로는 스택 오버플로우의 위험성이 존재하여 재귀함수는 잘 쓰지 않는다고 한다.

그러나 여전히 코딩테스트 풀이에선 유용하게 쓰일 때가 많다.

특히 반복문이 여러번 사용되는 상황에서 반복문 대신 재귀함수 방식을 채택하는 경우가 많다.

여러모로 재귀함수가 우월한 부분이 있기 때문이다. 이는 아래에 설명하겠다.

재귀함수

정의

• 메서드 or 함수 내부에서 자기 자신의 메서드 혹은 함수를 다시 호출(반환)하는 함수

원리

• 함수 내에서 어떤 조건에 의하여 다시 함수 자신을 호출한다.
• 위의 과정을 반복하다가 마지막에 종료 조건에 의하여 마지막 함수가 종료된다.
• 마지막 함수가 종료됨에 따라 역순으로 차례차례 함수들이 종료된다.

재귀함수의 유용성

• 코드의 간결화
• 변수 사용의 최소화

유의점

• 반드시 종료조건을 포함해야 한다.(안그러면 무한히 재귀, 스택 오버플로우 발생)
• 재귀함수가 실행되는 동안 함수 호출 이후의 명령문은 수행되지 않는다.

재귀함수를 이용한 예제 풀이

문제

data는 자연수로 이루어진 배열이다. data의 숫자들을 임의로 꺼내어 합칠 때, 가능한 경우의 수를 모두 구하라.

풀이

data = [3,5,8,10,12,15,20]

def recur(idx, val):
    if idx == len(data): # 재귀함수 종료구문
        result.add(val)
    else: # 재귀함수 본문
        recur(idx+1, val+data[idx]) # 다음 값으로 넘어가면서 지금 값을 val에 더해줌
        recur(idx+1, val) # 다음 값으로 넘어가기만 함(지금 값은 더해주지 않음)
        
result = set() 
recur(0,0)
print(result)

참고: 재귀함수를 활용한 팩토리얼 및 피보나치수열 구현

# Baekjoon #10872 팩토리얼 문항 풀이
def facto(n):
    if n==1:
        return 1
    else:
        return n*facto(n-1)
    
n = int(input())
print(facto(n))

# 피보나치 수열 구현
def fibo(n):
    if n<2:
        return 1
    else:
        return fibo(n-1)+fibo(n-2)