4강: 재귀 알고리즘 기초

---

재귀함수란?

• 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것
  • 생각보다 많은 종류의 문제가 재귀적으로(Recursively) 해결가능

예 : 이진트리 (Binary Trees)

• 왼쪽 서브트리의 원소들은 모두 작거나 같을 것
• 오른쪽 서브트리의 원소들은 모두 클것
  -> 이 원칙을 모든 노드에 대해서 적용

예 : 자연수의 합 구하기

문제 : 1부터 n까지 모든 자연수의 합을 구하시오

코드

def sum(n):
	if n <= 1:
    	return n
    else:
    	return n + sum(n - 1)

재귀 호출의 종결조건

• 알고리즘의 종결조건에 반드시 필요

---

재귀 알고리즘의 효율

반복문과 재귀 알고리즘의 시간 복잡도

• 두 알고리즘의 복잡도는 O(N)으로 같으나, 효율성 측면에서 보면 재귀 알고리즘의 경우 n의 크기에 따라 함수를 호출하고 반환하는데 부가적인 작업이 필요하기 때문에 반복문이 더 효율적이다.

---

예제

1. 펙토리얼 (n!)

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

2. 연습문제 - 피보나치 수열

코드

def solution(x):
    def fibonacci(n):
        if n < 2:
            return n
        else:
            return fibonacci(n-1) + fibonacci(n-2)
    
    return fibonacci(x)

---