[파이썬][알고리즘] 재귀 함수

재귀 용법 (recursive call)

재귀 용법

• 함수 안에서 동일한 함수를 호출하는 형태이다.

팩토리얼 구하기

• n! = n X (n-1)!
  • n > 1 이면 return n X 함수(n - 1)
  • n == 1이면 return n

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

for num in range(10):
    print(factorial(num))

1
1
2
6
24
120
720
5040
40320
362880

시간 복잡도와 공간 복잡도

• n - 1번 반복문을 호출한 것과 같다.
• 호출할 때마다 지역 변수 num이 생성된다.
• 시간 복잡도, 공간 복잡도 모두 O(n)이다.

재귀 호출은 스택의 예

• 파이썬에서는 재귀 함수를 최대 1,000번까지만 호출할 수 있다.

def factorial(num):
    value = 1
    for i in range(1, num + 1):
        value = value * i
    return value

factorial(10)

3628800

def factorial(num):
    if num <= 1:
        return num
    else:
        return num * factorial(num -1)

factorial(10)

3628800

리스트의 합 계산

def sum(list):
    if len(list) == 1:
        return list[0]
    else:
        return list[0] + sum(list[1:])

import random

num = random.sample(range(100), 10)
print(num)
sum(num)

[90, 9, 19, 66, 58, 6, 15, 38, 88, 89]





478

회문

• 어떤 단어를 거꾸로 해도 같은 단어가 나오는 것 (기러기, 토마토...)

def palindrome(string):
    if len(string) == 1:
        return True

    if string[0] == string[-1]:
        if len(string) == 2:
            return True
        return palindrome(string[1:-1])
    else:
        return False

palindrome('level')

True

palindrome('rumor')

False

1 만들기

• n이 짝수이면 n / 2
• n이 홀수이면 n * 3 + 1
• 이 과정을 반복하여 1이 나올 때까지 반복하는 함수

def one(num):
    print(int(num))
    if num == 1:
        return num
    elif num % 2 == 0:
        return int(one(num / 2))
    else:
        return int(one(num * 3 + 1))

one(10)

10
5
16
8
4
2
1





1

1, 2, 3 합

• 정수 n을 1, 2, 3의 합으로 나타내는 경우의 수 찾기
  • 순서가 다르면 다른 방법으로 취급

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

func(5)

13