그림으로 개념을 이해하는 알고리즘 - Ch 03

 

CH 03. 재귀

 

- 재귀 : 자기 자신을 호출하는 것

** 주의해야할 점 : 무한 반복하는 함수 주의
→ 언제 재귀를 멈출 지 정확하게 명시

def look_for_key(box):
  for item in box:
    if item.is_a_box():
      look_for_key(item)
    elif item.is_a_key():
      print "열쇠를 찾았습니다"

 

 

- 재귀 함수 구조
① 기본 단계 (함수가 자기 자신을 다시 호출하지 않는 부분)
② 재귀 단계 (함수가 자기 자신을 호출하는 부분)

def countdown(i):
  print i 
  if i <= 1:  ## 기본 단계 (i<=1이면 종료한다)
    return
  else:       ## 재귀 단계 (i>1이면 i-1로 countdown 함수를 호출한다)
    countdown(i-1)
    
 countdown(5)

 

 

- 호출 스택 : 여러 개의 함수를 호출하면서 함수에 사용되는 변수를 저장하는 스택
→ 푸시 : 가장 위에 새 항목 추가
→ 팝 : 가장 위의 항목 제거 및 읽기

 

** 스택 : 후입선출 (나중에 들어온 것이 먼저 나감)

** 주의해야할 점 : 모든 정보를 저장해야하므로 메모리를 많이 사용함
     → 해소 방법 : 반복문으로 대체 or 꼬리 재귀 사용

 

## 두개의 함수를 호출하는 greet 함수
def greet(name):
  print "hello,  " + name + "!"
  greet2(name)
  print "getting ready to say bye..."
  bye()

def greet2(name):
  print "how are you,  " + name + "?"
  
def bye():
  print "ok bye!"

greet('A')

 

① greet(”a”) 명령
② greet2(”a”) 실행 → 함수 반환 후 pop연산으로 삭제, greet 함수로 돌아옴
③ bye() 실행 → greet 함수로 돌아옴

 

 

 

 

 

- 재귀함수에서 호출 스택을 사용하는 예시

def fact(x):
  if x == 1:
    return 1
  else:
    return x * fact(x-1)

fact(3)

 

 

---

참고자료

Hello Coding 그림으로 개념을 이해하는 알고리