재귀 알고리즘 기초

hyuckhoon.ko·2022년 7월 26일
0

프로그래머스

목록 보기
5/15
post-thumbnail

플랫폼: 프로그래머스
강의명: 어서와! 자료구조와 알고리즘은 처음이지?
강사명: 이시윤


1. 재귀 함수란

하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것

많은 문제가 재귀 함수로 해결할 수 있다.
ex) 이진 트리의 순회,



2. 간단한 예제

1) 1부터 N까지의 합 구하기

"""
1부터 N까지의 합을 재귀함수로 구하기
"""
N = 100


def get_sum_recursively(N: int) -> int:
    if N <= 1:
        return N
    else:
        return N + get_sum_recursively(N-1)


res = get_sum_recursively(N)
print(res)

2) 팩토리얼 구현하기

"""
팩토리얼을 재귀함수로 구현
"""
N = 5


def get_factorial_by(N: int) -> int:
    if N <= 1:
        return N
    return N * get_factorial_by(N-1)


res = get_factorial_by(N)
print(res)

3. 재귀 알고리즘의 효율

재귀 호출 방식이든, 반복문 방식이든 N이 커질수록 선형적으로
시간복잡도가 증가한다.

O(N)

하지만, N이 커질수록 호출하고 종료하지 못한 함수의 정보가 메모리에 스택 방식으로 저장이 된다. 따라서, 이 경우에 재귀 호출 방식이 더 비효율적이다.

또는
1부터 N까지의 합을 구하는데, 더 간단한 공식이 있다. O(1)

"""
cf) 재귀 함수보다 더 효율적인 방식이 있는지 항상 고민해야 한다.
- O(1)
"""

==
def get_sum_efficiently(N: int) -> int:
    return N(N+1) // 2


res = get_sum_recursively(N)
print(res)



4. 피보나치 수열

1) 수열 구하기

"""
재귀함수를 활용한 피보나치 수열
Q. N 이하의 피보나치 수열을 구현하기
*피보나치 수열: 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열
"""
from typing import List

N = 55


def get_fibonacci_numbers_under(N: int, res: List) -> List:
    n2 = res[-2] + res[-1]
    if n2 > N:
        return res
    else:
        res.append(n2)
        return get_fibonacci_numbers_under(N, res)


res = get_fibonacci_numbers_under(N, [1, 1])
print(res)

2) N번째 항의 피보나치 수 구하기

"""
인자로 0 또는 양의 정수인 x 가 주어질 때,
피보나치 수열의 해당 값을 구하여 반환하는 함수 solution() 을 완성하세요.
"""


def get_fibo_of(N: int) -> int:
    if N <= 1:
        return 1
    return get_fibo_of(N-1) + get_fibo_of(N-2)


res = get_fibo_of(N)
print(res)

0개의 댓글