재귀함수 (Recursion)

재귀함수

再歸函數
정의 단계에서 자신을 재참조하는 함수

어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 함
함수를 만들고 실행하면 함수가 실행이 완료되기 전까지 호출 스택(CallStack) 이라는 곳에 담김

- 재귀 함수의 요소
1. 종료 조건 = [ if (n == 4) return None ]
2. 실행 로직
3. 재귀 호출 = [ def recursive(n) : recursive(n+1) ]

스택

• 탐색과 처리 중 탐색을 만나면 우선적으로 탐색을 마치는 것을 우선, 이러한 성질 때문에 컨테이너에 자료들이 보관되는 양과 기간이 긴 편
• 탐색이 필요한 계층 구조를 가지는 자료에 사용
• CallStack 같은 경우, 내부에 존재하는 함수를 먼저 모두 탐색하는 방식으로 동작하고 그 동안의 상위 호출은 스택에 계속해서 저장

[ 예시 코드 ]

def A()
def B()

def C():
	B() 		# B가 실행되는 동안 C는 여전히 실행중이다.
	return None 
				# C함수 종료

def D() {
	A() 		# A가 실행되는 동안 D는 여전히 실행 중(스택에 담겨있는 중)이다.
	C(); 		# C가 실행되는 동안 D는 여전히 실행 중이다.
	return None
				# D함수 종료
}

: 자식의 탐색이 우선이고 부모의 상태는 매번 저장되었다가 자식의 실행이 마치는 대로 부모의 실행이 진행

예제

##### 별 그리기
def recursive(n):
   if(n == 4) 
   	return None
		
	for i in range(n)
      print("*")
   
   print("\n")

   recursive(n + 1)

recursive(1);

# < Result >
# *
# **
# ***

##### 별 역순으로 그리기
def recursive(n):
   if(n == 4) 
   	return None
    
   recursive(n + 1)					# 탐색을 먼저 호출하여 n = 3일 때까지 모든 함수 호출

									# 위 문장 실행 후 Callstack :
                                    # [ recursive(1), recursive(2) ]

	for i in range(n)				# 탐색이 끝난 뒤 그리기 시작
      print("*")
   
   print("\n")

recursive(1);

# < Result >
# ***
# **
# *

본문 출처
썸네일