[알고리즘] 재귀함수 - (팩토리얼(Factorial) / 피보나치 수열(Fibonacci))

재귀 함수란?

• 메서드/함수의 내부에서 자기 자신의 메서드/함수를 다시 호출하는 함수
• Fractal 구조. Sierpinski Triangle

재귀 함수의 특징

• 재귀 함수 초반에 등장하는 조건문이 종료 조건 역할을 수행
• 재귀 함수는 내부적으로 스택 자료구조와 동일함
• 재귀 함수는 최대 1000번까지 가능
• 코드의 간결화 및 변수 사용 최소화를 위해 사용함

 

재귀 함수의 예

[인덱스의 모든 합]

• 성분들의 합으로 표현할 수 있는 숫자의 경우의 수는? #8
  → 부분집합의 개수 2en
  → 3,5,8이 선택이 되느냐 안되느냐니까 각 수마다 2가지 경우가 있다
  → 단, 3+5 = 8이므로 중복됨

#반복문
data = [3,5,8]

result = set()
for i in range(2):
	for j in range(2):
		for k in range(2):
			result.add(data[0]*i + data[1]*j + data[2]*k)
print(result)

#재귀함수
data = [3,5,8]

def recur(index, value):
	if index==len(data):   #종료구문
		result.add(value)
	else:
		recur(index+1, value+data[index])
		recur(index+1, value)

result = set()
recur(0,0)
print(result)

 

[Factorial 문제]

• n! = 1*2*3*... * (n-1) * n
• 점화식(재귀식) : 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것
• 시간 복잡도/공간 복잡도는 O(n)

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

 

[피보나치수열]

#그냥 함수
data = [1,1,2,3,5,8,13,21]

def fibo(data):
	if data==[]:
		return result
	result += data[0]+data[1]
	data.pop()
	data.pop()
	return result + fibo(data)

fibo(data)

#재귀 함수
def fibonacci(n):
	if n==0 or n==1:
		return 1
	else:
		return fibonacci(n-1) + fibonacci(n-2)