재귀 함수

guava·2021년 9월 18일
0

알고리즘의 정석

목록 보기
5/13
post-thumbnail

코드잇의 알고리즘의 정석 수업을 수강하고 정리한 글입니다.
정확하지 않거나 빠트린 내용이 있을 수 있기 때문에 강의를 수강하시길 권장합니다.

1. 재귀 함수 개요

재귀 함수 (Recursive Function) : 자기 자신을 호출하는 함수

# 재귀 함수의 예
# 정수 n부터 1까지 출력하는 countdown 함수
def countdown(n):
    if n > 0:
        print(n)
        countdown(n - 1)

countdown(4)

# 콘솔
4
3
2
1

실행 순서

# 실행 순서는 1-, 2-, 3- 이렇게 표현하였다.

# 프로그램 실행
def countdown(n):
    if n > 0:
        print(n)
        countdown(n - 1)
countdown(4) # 1- countdown(4)가 실행된다. 

# countdown(4)
if 4 > 0:
    print(4)  # 2- 4가 출력 된다.
    countdown(4 - 1)  # 3- countdown(3)이 실행된다.

# countdown(3)
if 3 > 0:
    print(3)  # 4- 3이 출력된다.
    countdown(3 - 1)  # 5- countdown(2)이 실행된다.

# countdown(2)
if 2 > 0:
    print(2)  # 6- 2가 출력된다.
    countdown(2 - 1)  # 7- countdown(1)이 실행된다.

# countdown(1)
if 1 > 0:
    print(1)  # 8- 1이 출력된다.
    countdown(1 - 1)  # 9- countdown(0)이 실행된다.

# countdown(0)
if 0 > 0:  # 10- if문을 수행하지 않고 countdown(0)이 끝난다. 
    print(1) # 실행되지 않음
    countdown(0 - 1)  # 실행되지 않음

# 11- countdown(0)이 끝났으므로 countdown(1)이 끝난다.
# 12- countdown(1)이 끝났으므로 countdown(2)가 끝난다.
# 13- countdown(2)기 끝났으므로 countdown(3)이 끝난다.
# 14- countdown(3)이 끝났으므로 countdown(4)가 끝난다.
# 15- countdown(4)가 끝났으므로 프로그램이 종료된다.

2. 재귀 활용 예시

팩토리얼 (Factorial)

팩토리얼

n!=1×2×...×(n1)×nn! = 1 \times 2 \times ... \times (n-1) \times n

팩토리얼 계산

0!=10! = 1
1!=11! = 1
2!=1×2=22! = 1 \times 2 = 2
3!=1×2×3=63! = 1 \times 2 \times 3 = 6
4!=1×2×3×4=244! = 1 \times 2 \times 3 \times 4 = 24
4!=1×2×3×4×5=1204! = 1 \times 2 \times 3 \times 4 \times 5 = 120

재귀함수를 이용한 팩토리얼 계산함수 만들기

재귀적으로 문제를 푼다는 것 = 부분 문제(Subploblem)의 답을 이용해서 기존 문제를 푸는 것

재귀적으로 생각해보기

5!=1×2×3×4×5=1205! = 1 \times 2 \times 3 \times 4 \times 5 = 120
\rightarrow 5!안에는 부분문제 4!(1×2×3×41 \times 2 \times 3 \times 4)이 존재한다.
즉 5!을 풀기 위해서는 4!을 풀어야한다.

4!=1×2×3×4=244! = 1 \times 2 \times 3 \times 4 = 24
\rightarrow 4!안에는 부분문제 3!(1×2×31 \times 2 \times 3)이 존재한다.
즉 4!을 풀기 위해서는 3!을 풀어야한다.

3!=1×2×3=63! = 1 \times 2 \times 3 = 6
\rightarrow 3!안에는 부분문제 2!(1×21 \times 2)이 존재한다.
즉 3!을 풀기 위해서는 2!을 풀어야한다.

이와 같이 재귀적으로 문제를 해결할 수 있으며, 마지막에는 0!이 남게 된다.
우리는 0!이 팩토리얼 정의를 통해 1임을 이미 알고 있다. (0!=10!=1)
0!에 1을 곱하면 1!이 풀리고 마찬가지로 1!에 2를 곱하면 2!이 풀린다. 이를 반복하면 5!문제도 풀 수 있으며 부분 문제를 먼저 풀어서 본연의 문제를 해결 할 수 있다.

재귀적인 접근 방법

재귀적으로 문제를 접근할 때는 base case와 recursive case로 나누어서 생각해야 한다. 우리는 5!의 문제를 재귀적으로 접근해보면서 0!=10!=1임을 이미 알고 있었다. 이것을 base case로 보면 된다. base case, recursive case로 나누어서 문제에 접근하면 재귀적으로 문제에 접근하는데 수월하다.

  • base case : 문제가 작아서 바로 풀 수 있다.
  • recursive case: 재귀적으로 부분 문제를 푸는 경우

base case:
n=0n=0인 경우 n!=1\rightarrow n!=1

recursive case:
n>0n>0인 경우 n!=(n1)!×n\rightarrow n!=(n-1)! \times n

코드로 작성해보자

# 재귀적으로 구현한 factorial 함수
def factorial(n):
    if n == 0:
        return 1
    return factorial(n - 1) * n

print(factorial(4))

실행 순서

# 실행 순서는 1-, 2-, 3- 이렇게 표현하였다.
# @{{number}}는 하단에 있는 주석에서 위치를 표시하기 위해 사용되었다.

def factorial(n):
    if n == 0:
        return 1
    return factorial(n - 1) * n
print(factorial(4)) # 1- factorial(4)가 실행된다. (@5)

# factorial(4)
if 4 == 0:
  return 1
return factorial(4 - 1) * 4  # 2- factorial(3)이 실행된다. (@4)

# factorial(3)
if 3 == 0:
  return 1
return factorial(3 - 1) * 3  # 3- factorial(2)가 실행된다. (@3)

# factorial(2)
if 2 == 0:
  return 1
return factorial(2 - 1) * 2  # 4- factorial(1)이 실행된다. (@2)

# factorial(1)
if 1 == 0:
  return 1
return factorial(1 - 1) * 1  # 5- factorial(0)이 실행된다. (@1)

# factorial(0)
if 0 == 0:
  return 1  # 6- 1이 리턴된다.
return factorial(0 - 1) * 0

# 7- @1에서 factorial(1 - 1)이 1로 대체되고 $1\times1$이 되어 1을 리턴한다.
# 8- @2에서 factorial(2 - 1)이 1로 대체되고 $1\times2$이 되어 2을 리턴한다.
# 9- @3에서 factorial(3 - 1)이 2로 대체되고 $2\times3$이 되어 6을 리턴한다.
# 10- @4에서 factorial(4 - 1)이 6로 대체되고 $6\times4$이 되어 24을 리턴한다.
# 11- @5에서 리턴된 값인 factorial(4)가 24로 대체되고 이를 콘솔에 출력한다.

최종적으로 4!의 값인 24가 콘솔에 출력된다.

3. 재귀 함수 vs 반복문

반복문은 재귀로 풀수 있고, 재귀 함수는 반복문으로 해결이 가능하다.

# 반복문을 이용한 팩토리얼
def factorial(n):
    result = 1
    for i in range(1, n+1):
        result = result * 1
    return result

# 재귀를 이용한 팩토리얼
def factorial(n):
    if n == 0:
        return 1
    return factorial(n - 1) * n

재귀함수의 단점

보통 함수를 실행하면 원래의 위치를 기록해 두었다가 함수가 끝나면 그 위치로 돌아온다.

def say_hello(name)
    print("hello " + name)

my_name = "Young"
say_hello(my_name)  # 위치를 기록해둔다.

이렇게 함수의 위치를 기록해 두는 곳을 call stack이라고 하며, 재귀를 너무 많이 호출하면 call stack이 쌓이게 되고 과부하로 인해 프로그램이 중단될 수 있다.

재귀함수는 언제 쓰는게 좋을까?

  • 반복문이었던 것을 재귀 함수로 수정하면 더 깔끔하거나 효율적일 때가 있다.
  • call stack이 쌓이는게 문제가 될 것 같으면 반복문을 쓰는게 좋다.

0개의 댓글