[자료구조와알고리즘with파이썬] Ch.01-5 시스템 스택과 순환 호출

순환 (recursion): 어떤 함수가 자기 자신을 다시 호출하여 문제를 해결하는 프로그래밍 기법

ex) 팩토리얼 계산, 하노이 탑, 이진트리 등

---

Ex1: 팩토리얼 계산

방법1

def factorial(n):
	result+1
    for k in range(2,n+1)
    	result *= k
    return result

k가 숫자가 늘어나면서 result에 곱해지기 때문에 이 코드는 반복구조임

 

방법2

def factorial(n):
	if n==1:
    	return 1
    else:
    	return n*factorial(n-1)

n*(n-1)*(n-2)..... 이렇게 다시 factorial함수를 부르면서 곱해지기 때문에 순환구조임

---

Ex2: 하노이 탑

 

 

 

 

 

 

 

 

 

 

 

 

 

 

def hanoi_tower(n, fr, tmp, to):
	if(n==1):
    	print("원판 1: %s --> %s" %(fr,to))
    else:
    	hanoi_tower(n-1, fr, to ,tmp)
        print("원판 %d: %s --> %s" %(n,fr,to))
        hanoi_tower(n-1,tmp,fr,to)

 

 

시작: (3, a,b,c)

else로 가서 hanoi_tower(2,a,c,b) 호출

hanoi_tower(2,a,c,b)가 else로 가서 honoi_tower(1,a,b,c) 호출

honoi_tower(1,a,b,c)가 if 절로 들어가서 원판1: a --> c 출력됨

hanoi_tower(2,a,c,b)로 돌아감.

원판2: a --> b가 출력됨

그리고 hanoi_tower(1,c,a,b)를 호출

hanoi_tower(1,c,a,b)는 if절로 들어가서 원판1: c-->b를 출력

다시 hanoi_tower(3,a,b,c)로 감

가서 hanoi_tower(2,a,b)를 출력한 다음 줄인 print("원판 %d: %s --> %s" %(n,fr,to))로 간다.

원판3: a--> c 출력

그리고 hanoi_tower(2,b,a,c)를 호출함

hanoi_tower(2,b,a,c)는 else로 가서 hanoi_tower(1,b,c,a)를 호출함

if로 들어가서 원판1: b-->a가 출력됨

다음 줄인 print("원판 %d: %s --> %s" %(n,fr,to))로 간다.

원판2: b-->c 출력

hanoi_tower(1,a,b,c)를 호출함

hanoi_tower(1,a,b,c)는 if로 가서 원판1: a-->c를 출력함