[알고리즘] 재귀 호출 (recursive call)

1. 재귀 용법 (recursive call, 재귀 호출)

• 함수 안에서 동일한 함수를 호출하는 형태
• 여러 알고리즘 작성시 사용되므로, 익숙해져야 함

2. 재귀 용법 이해

예제를 풀어보며, 재귀 용법을 이해해보기

예제

팩토리얼을 구하는 알고리즘을 Recursive Call 을 활용해서 알고리즘 작성하기

분석하기

• 간단한 경우부터 생각해보기
  - 2! = 1 X 2
  - 3! = 1 X 2 X 3
  - 4! = 1 X 2 X 3 X 4 = 4 X 3!
• 규칙이 보임: n! = n X (n - 1)!
  - 함수를 하나 만든다.
  - 함수(n) 은 n > 1 이면 return n X 함수(n - 1)
  - 함수(n) 은 n = 1 이면 return n

검증 (코드로 검증하지 않고, 직접 간단한 경우부터 대입해서 검증해야 함)

1. 먼저 2! 부터
   - 함수(2) 이면, 2 > 1 이므로 2 X 함수(1)
   - 함수(1) 은 1 이므로, return 2 X 1 = 2 맞다!
2. 먼저 3! 부터
   - 함수(3) 이면, 3 > 1 이므로 3 X 함수(2)
   - 함수(2) 는 결국 1번에 의해 2! 이므로, return 2 X 1 = 2
   - 3 X 함수(2) = 3 X 2 = 3 X 2 X 1 = 6 맞다!
3. 먼저 4! 부터
   - 함수(4) 이면, 4 > 1 이므로 4 X 함수(3)
   - 함수(3) 은 결국 2번에 의해 3 X 2 X 1 = 6
   - 4 X 함수(3) = 4 X 6 = 24 맞다!

코드 레벨로 적어보기

def factorial(n):
    if n > 1:
        return n * factorial(n-1)
    else:
        return n

코드 이미지

테스트

시간 복잡도와 공간 복잡도

• factorial(n) 은 n - 1 번의 factorial() 함수를 호출해서, 곱셈을 함
  - 일종의 n-1번 반복문을 호출한 것과 동일
  - factorial() 함수를 호출할 때마다, 지역변수 n 이 생성됨
• 시간 복잡도/공간 복잡도는 O(n-1) 이므로 결국, 둘 다 O(n)

3. 재귀 호출의 일반적인 형태

일반적인 형태 1

def func(x):
    if x > 일정값:
        return func(x - 1)
    else:
        return 특정값

일반적인 형태 2

def func(x):
    if x <= 일정값:
        return 특정값
    return func(x - 1)

형태 2 - 예시

중요한 건, 입력 값이 특정 값보다 “클” 때와 “작을” 때 두 가지 경우로 나누는 것이다!

재귀 호출은 스택의 전형적인 예

함수는 내부적오르 스택처럼 관리된다.

• 재귀 호출이 이해가 가지 않는다면?
  - 이 사이트를 참고하자!

참고: 파이썬에서 재귀 함수는 깊이가(한번에 호출되는…) 1000회 이하가 되어야 함

4. 재귀 용법을 활용한 프로그래밍 연습

연습 1 - 숫자가 들어있는 리스트가 주어졌을 때, 리스트의 합을 리턴하는 함수

def sumList(dataList):
    if len(dataList) <= 1:
        return dataList[0]
    return dataList[0] + sumList(dataList[1:])

코드 이미지

테스트

연습 2 - 회문인지 판단하는 함수

def check(string):
    if len(string) <= 1:
        return True
    if string[0] == string[-1]:
        return check(string[1:-1]) # 1번째 인덱스부터 "-2"번째 인덱스까지 슬라이싱
    else:
        return False

코드 이미지

테스트

연습 3

1. 정수 n에 대해
2. n이 홀수이면 3*n+1 을 하고
3. n이 짝수이면 n을 2로 나눕니다.
4. 이렇게 계속 진행해서 n이 결국 1이 될 때까지 2와 3의 과정을 반복합니다.
5. 이렇게 정수 n을 입력받아, 위 알고리즘에 의해 1이 되는 과정을 모두 출력하는 함수를 작성하세요.

def func(n):
    print(n)
    if n == 1:
        return True
    if n%2 == 1:
        return func(3*n+1)
    else:
        return func(n//2)

테스트

연습 4

• 정수 n이 입력으로 주어졌을 때, n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 구하시오

def func(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4
    
    return func(n-1) + func(n-2) + func(n-3)

테스트

분석

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기