플랫폼: 프로그래머스
강의명: 어서와! 자료구조와 알고리즘은 처음이지?
강사명: 이시윤
하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것
많은 문제가 재귀 함수로 해결할 수 있다.
ex) 이진 트리의 순회,
"""
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)
"""
팩토리얼을 재귀함수로 구현
"""
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)
재귀 호출 방식이든, 반복문 방식이든 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)
"""
재귀함수를 활용한 피보나치 수열
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)
"""
인자로 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)