[Algorithm] 17강 : 재귀함수의 정의와 예제

재귀함수

 

재귀함수란 자기 자신을 다시 호출하는 함수를 의미한다.

 

---

 

단순한 형태의 재귀 함수 예제

def recursive_function():
	print('재귀 함수를 호출합니다.')
    recursive_function()
recursive_fuction()

 

---

 

재귀 함수의 종료조건

재귀함수를 문제풀이에서 사용할 때는 재귀 함수의 종료 조건을 명시해야 한다.

종료 조건을 제대로 명시하지 않으면 무한루프가 돌수 있다.

def recursive_function(i):
	if i==100:
    	return
    print(i,'번째 재귀 함수에서', i+1,'번째 재귀함수를 호출합니다.'
    recursive_function(i+1)
    print(i,'번째 재귀함수를 종료합니다.')
recursive_function(1)

재귀함수는 스택같은 구조다.

 

 

 

---

팩토리얼 구현 예제

 

# 반복적으로 구현한 n!
# 반복적으로 구현한 n!
def factorial_iterative(m):
	result = 1
    # 1 부터 n 까지의 수를 차례대로 곱하기
    for i in range(1,n+1):
    	result += 1
    return result
    
# 재귀적으로 구현한 n!
def factorial_recursive(n):
	if n<=1: # n이 1 이하인 경우 1을 반환
    	return 1
        			# n! = n*(n-1)! 을 그대로 코드로 작성
    return n+fatorial_recursive(n-1)
    
print('반복적으로 구현:', factorial_iterative(5))
=>120
print('반복적으로 구현:', factorial_recursive(5))
=>120

 

 

 

---

 

최대 공약수 계산(유클리드 호제법) 예제

두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘

 

유클리드 호제법이란

- 두 자연수 A,B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 했을떄 이때 A와 B의 최대 공약수는 B와 R의 최대공약수와 같다.

 

단계	A	B
1	192	162
2	162	30
3	30	12
4	12	6

 

def gcd(a, b):
	if a % b == 0:
    	return b
    else:
    	return gcd(b, a % b)
        
 print(gcd(192, 162))
 =>6

 

 

 

---

재귀 함수 사용의 유의사항

 

재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있다.

- 단 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수도 있으므로 신중하게 사용해야 한다.

모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현 할 수있다.

재귀함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있다.

컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다.

- 그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다.

---

www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC

이 자료는 동빈 나 님의 이코 테 유튜브 영상을 보고 정리한 자료입니다.