Post

시스템 스택과 순환호출(재귀함수)

Posted
By devHmmi 6 min read

시스템 스택

  • 운영체제가 관리하는 메모리 공간에 스택이라는 영역이 존재한다.
  • 이 영역은 함수의 호출과 반환에 사용된다.
  • 스택에는 함수가 끝나고 돌아갈 복귀 주소, 호출된 함수에서 사용할 매개변수, 지역변수를 스택에 저장한다.
  • 함수가 끝나면, 끝나고 돌아갈 복귀 주소로 돌아간다.
  • main()에서 func()를 호출하고 func()에서 sub()를 호출한다면, sub()가 끝나면 func()로 돌아가고, func()가 끝나면 main()으로 돌아간다.
  • 이 내용을 가지고 순환 호출로 넘어가자.

순환 호출(재귀함수)

  • 순환 호출은 어떤 함수가 자기 자신을 호출하는 프로그래밍 기법이다.
  • 자기 자신을 호출한다는 것이 이상하게 느껴질 수 있지만, 함수A가 함수B를 호출하는 것과 함수A가 함수A를 호출하는 것은 같은 원리이다.
  • 함수A의 돌아갈 주소에 함수A를 두는 것 뿐이다.
  • 문제를 축소시켜가는 것과, 일반화된 규칙을 코드에 대입하는 것이 중요하다.

순환 호출로 팩토리얼 문제 해결하기

  • 팩토리얼 문제는 반복문으로 해결할 수도 있지만, 순환 호출로 해결할 수도 있다.

반복 구조로 해결한 팩토리얼

1
2
3
4
5
6
7
8

def factorial_iter(n): # 반복 구조로 구현한 팩토리얼
    result = 1
    for k in range(2, n+1): # k:2, ..., n
        result = result * k # result에 k를 곱함.
    return result

print("반복 구조 팩토리얼 : ", end='')
print(factorial_iter(5))

순환 호출로 해결한 팩토리얼

  • 팩토리얼을 순환 호출로 해결하는 것은 가장 기본적인 순환 호출 방법이다.
  • 팩토리얼은 1부터 n까지 차례로 곱하는데, 결국 (n-1)*n이 n!이라는 것을 그대로 옮기기만 해도 해결된다.
  • 즉, 일반화된 규칙을 이해한 후 일반화된 규칙을 코드에 대입해주기만 하면 된다. 이게 재귀 함수의 장점이다.
1
2
3
4
5
6
7
8

def factorial(n): # 순환구조(재귀호출)로 구현한 팩토리얼.
    if n == 1:
        return 1 # 순환 호출을 멈추는 부분. n이 1이면 답을 알고 있음.
    else:
        return n * factorial(n-1) # 자신을 순환적으로 호출하는 부분. 문제의 크기는 작아져야 함.
    
print("순환 구조 팩토리얼 : ", end='')
print(factorial(5))

순환 호출로 해결한 하노이의 탑

  • 복잡한 코드여서 스택을 따라가면서 이해하려고 하니 이해하기가 어려웠다.
  • 팩토리얼에서 이해한 일반화된 규칙을 이해한 후 일반화된 규칙을 코드에 대입해주기만 하면 된다는 식으로 하는 편이 낫다.
  • 하노이의 탑 문제에서는, A가 출발, B가 임시, C가 목표 막대일때, 세 가지 규칙을 따른다.
    1. A에 있는 n-1개의 원판을 C를 임시 막대로 삼아 B로 이동
    2. A에 하나 남은 원판을 C로 이동
    3. B에 있는 n-1개의 원판을 A를 임시 막대로 삼아 C로 이동
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

def hanoi_tower(n, fr, tmp, to):
    """
    하노이 탑 문제를 해결하는 함수

    Parameters:
    - n (int): 원판의 수
    - fr (str): 시작 막대
    - tmp (str): 임시 막대
    - to (str): 목표 막대
    """
    
    if(n==1):
        print("원판 1: %s --> %s" % (fr,to)) # 순환 호출을 멈추는 부분. 원판이 하나라면 바로 이동.
    else:
        hanoi_tower(n-1, fr, to, tmp) # 1단계 : fr막대에 있는 n-1개의 원판을 to 막대를 이용해 tmp로 옮김
        print("원판 %d: %s --> %s" % (n,fr,to)) # 2단계 : fr에 있는 하나의 원판을 바로 to로 옮김.
        hanoi_tower(n-1, tmp, fr, to) # 3단계 : 마지막으로 tmp에 있는 n-1개의 원판을 fr을 이용해 to로 옮김

hanoi_tower(4, 'A', 'B', 'C')

순환 호출로 문자열 뒤집기

  • 이 문제 또한 공통된 규칙을 적용하며 문제를 줄여나간다.
  • 현재 마지막 단어를 출력한다라는 규칙을 적용하며 msg와 len을 줄여나간다.
1
2
3
4
5
6
7
8

def printReverse(msg, len):
    if len>0:
        print(msg[len-1])
        printReverse(msg, len-1)

instr = "자료구조"
printReverse(instr, len(instr))
print()

참고 자료

자료구조, 스택
python stack
This post is licensed under CC BY 4.0 by the author.