[알고리즘] 재귀 함수 ( Recursive Function ) ( + 팩토리얼과 피보나치수열)

이전글 : )

[알고리즘] 파이썬 기본 문법 - set (집합)

 

 재귀 함수 Recursive Function 

재귀 함수란 함수 자기 자신 로직 내부에서 자신을 호출하는 함수입니다. 이 행위를 재귀 호출이라 합니다.

이러한 재귀를 사용해서 팩토리얼이나 피보나치수열 등 반복적으로 하위의 해답을 이용해 원래의 문제를 해결하는 수학적 문제에 두루 사용합니다.

또한 이론적으로는 for문과 while문 등과 같은 반복문을 모두 대체 가능하다고 합니다.

 

# 재귀함수 기본 형태

def recursive(num):
	print(num)
    num+= 1
    recursive(num)	# 자기 자신을 다시 호출
    
recursive(1)

'''

출력
1
2
3
4
5
6
...

'''

 

재귀 함수가 실행될 때 메모리 내에서는 stack에 쌓고 해결 후 pop으로 삭제하는 형식으로 작동합니다.

무한 loop의 재귀로 인한 stack overflow를 막기 위해 파이썬에서는 재귀 깊이를 두고 있으며 재한을 두지 않으면 예외를 발생시킵니다.

>>> RecursionError: maximum recursion depth exceeded in comparison

예외를 발생시키거나 stack overflow를 방지하기 위해서는 반복문을 사용하거나 또는 조건문을 이용해 제어를 하면 됩니다.

# 조건문을 이용한 재귀함수 탈출

def countdown(n):
	print(n)
	if n == 0:
		return             # 재귀 종료
	else:
		countdown(n - 1)   # 자기 자신 호출
        
countdown(5)

'''

출력
5
4
3
2
1
0

'''

 

 대표 예제 

 

 팩토리얼 

 

팩토리얼이란 n! 의 형태로 수학적으로 표현하며 1부터 n까지의 자연수를 모두 곱합니다. (n은 양수이며 0! = 1)

 

일반 반복문을 이용한 예제를 본 후 재귀 호출을 이용한 예제 코드를 확인해보겠습니다.

 

아래는 for반복문을 이용한 팩토리얼 구현 코드입니다.

#for반복문을 이용한 팩토리얼

a = int(input())		# 팩토리얼을 구할 숫자 입력

result = 1

for item in range(1, a+1, 1):
	result *= item	
    
print(result)

'''

입력
4

출력
24

'''

아래는 재귀호출을 이용한 팩토리얼 구현 코드입니다.

# 재귀 호출을 이용한 팩토리얼

def factorial(n):
	if(n > 1):
		return n * factorial(n - 1)		# 자기 자신 호출
	else:
		return 1

a = int(input())				# 팩토리얼을 구할 숫자 입력
print(factorial(a))

'''

입력
4

출력
24

'''

https://www.cs.rice.edu/~ogilvie/comp571/2018/08/28/recursion.html ( factorial() 함수 동작 원리 )

 

 

 피보나치수열 

 

피보나치 수열이란 앞의 두 수의 합이 바로 뒤의 수가 되는 수의 배열을 말합니다.

https://news.samsungdisplay.com/23402/

 

아래는 for반복문을 이용한 피보나치수열을 구현 코드입니다.

# for 반복문을 이용한 피보나치의 수 구하기

n = int(input())			# 피보나치의 수를 구할 수 입력

a,b = 1,1
if n==1 or n==2:
	print(1)

for i in range(1,n):
	a,b = b, a+b

print(a)

'''
입력
5

출력
5
'''

아래는 재귀 호출을 이용한 피보나치수열 구현 코드입니다.

# 재귀호출을 이용한 피보나치의 수 구하기

def fibo(a):
    if a==1 or a==2:
        return 1
    else:
        return fibo(a-1) + fibo(a-2)

n = int(input())
print(fib(n))

'''
입력
5

출력
5
'''

 

https://medium.com/launch-school/recursive-fibonnaci-method-explained-d82215c5498e       ( fibo() 함수의 동작 원리 ) 복잡;;

 

---

 마무리 

재귀 함수 또는 재귀 호출은 코드를 간결하게 만들어주는 장점이 있습니다. 하지만 단점으로는 코드의 가독성을 매우 떨어트리며 이로 인해 디버그도 어렵고 실수를 한다면 쉽게 무한 loop에 빠지기도 하는 부분이 있습니다. 또한 메모리도 상당히 차지한다고 합니다. 이러한 단점들 때문에 재귀 호출의 사용을 좋아하지 않는 개발자들이 많이 존재한다고 합니다. 

 

 

---

 

 

[알고리즘] 완전 탐색 • 브루트 포스 (Brute Force)