this.code();

※ procedure 목차

1. 스택의 구조

2. 호출의 관습

  - 제어의 전달

  - 데이터의 전달

  - 지역 데이터의 관리

3. 재귀실행

§ Procedure 소개

프로시저(procedure)는  특정 작업을 수행하는 서브 프로그램으로 자주 사용하기 위해 생성하는 메서드 같은 것이다.

이런 프로시저의 실행에는 3가지 유형이 있다.

§ 프로시저 실행의 유형 (모든 동작은 기계어로 구현된다.)

1. 제어의 전달

  ▷ 프로시저 코드의 시작부분으로 리턴지점으로 돌아간다.

2. 데이터의 전달

  ▷ 프로시저 인자

  ▷ return 값

3. 메모리 관리

  ▷ 프로시저 실행 중 할당하며 return시 반환한다.

※ procedure _ 2. 호출의 관습

§ x86-64 스택

- 메모리 영역으로 register %rsp는 가장 작은 스택주소를 저장.

§ procedure 제어흐름

▶ procedure 호출

stack frame을 이용해 procedure호출과 return을 지원하며 아래와 같은 호출 방법을 사용한다.

call Label

- Step 1: return 주소를 stack에 push

- Step 2: Label로 jump

cf) return 주소란?
call 바로 다음 줄의 명령어 주소로 아래 예시를 들자면, 400549가 바로 return 주소이다.

400544:  callq  400550  <mult2>
400549:  mov  %rax,  (%rbx)

▶ procedure 반환

stack frame을 이용해 procedure반환을 진행하는데, stack에서 return주소의 pop을 진행하며 아래와 같은 방법 사용하며, 이 return 주소로 jump한다는 의미이다.

ret

§ procedure 데이터의 흐름

§ procedure 지역 데이터의 관리

▶ Stack Frame 기반 언어 = 재귀호출을 지원하는 언어로 C, Java와 같은 언어들을 예시로 들 수 있다.

- "Reentrant", 즉 재진입해야하는 코드로 각 실행개체의 상태를 저장할 장소가 필요하기 때문이다.

Ex. Recursion의 Stack Frame

▶ x86-64 / Linux 의 Stack Frame 

Ex-1).  incr 함수

Ex-2).  incr 함수

- incr #1

subq	$16,  %rsp         #rsp-16 = stack이 커진다 = stack frame할당으로 공간확보
movq	$15213,  8(%rsp)   #15213을 v1에 copy

- incr #2

movl	$3000,  %esi         # rsi에 3000을 넣음
leaq	8(%rsp), %rdi        # rdi에 주소 할당

- incr #3  (15213 + 3000을 더해 18213값이 들어감)

- incr #4

addq	8(%rsp),  %rax         # 현재 incr의 return값 rax는 v2에 저장되어 있어서 v1+v2를 다음과 같이 진행
addq	$16, %rsp              # pop을 진행

▶ register 보관관습 => stack frame에 필요한 register를 push해 저장함

- 똑같은 register를 다른 함수에서 사용가능해서 return 후 다시 register를 복원한다.

- 아래 예시를 보면 두 개 모두 %rdx라는 중복된 register를 사용한다.

때문에 compiler에 따라 다음 2가지 방식으로 구현할 수 있다.

§ 재귀 실행

Ex)

/*-----------Recursive popcount-----------*/
long pcount_r (unsigned long x) {
    if (x == 0)
        return 0;
    else
        return (x & 1) + pcount_r(x >> 1);
}

※ Recursion (순환 / 재귀)

흔히들 재귀라 부르는 recursion은 함수가 자기자신을 호출하여 문제를 해결하는 프로그래밍 기법이다.

보통 우리는 이렇게 반복을 요하는 문제에서는 반복문(for, while)을 사용하는 경우가 많다. 또한, 이런 반복문의 효율성은 무시하지 못할 것이다. 일반적으로 재귀보다는 반복문이 더욱 효율적이고 값 도출시간도 빠르다.

§  최대공약수

auto gcd(int A, int B){
    if (B == 0)
        return A;
    else
        return gcd(B, A%B);
}

https://chan4im.tistory.com/58

https://www.acmicpc.net/problem/13241

※ 재귀를 사용하는 이유

이렇게 반복문보다 효율이 떨어지는 재귀를 도대체 우리는 사용하는 이유와 배워야 하는 이유가 무엇일까?

바로 재귀만이 갖는 자기자신의 호출로 특정 문제나 알고리즘에서 매우 강력(powerful)한 경우가 있다.

재귀로 짜면 간단하게 2~3줄로 나올 코드가 반복문으로 몇십줄이 넘어갈 수 도 있으니 말이다.

대표적인 예를 들어보자면 다음과 같다.

- 거듭제곱, 팩토리얼의 계산

백준 10872번: https://www.acmicpc.net/problem/10872

- 피보나치 수열의 계산

백준 2747번: https://www.acmicpc.net/problem/2747

- 하노이탑 문제

백준 1914번: https://www.acmicpc.net/problem/1914

#include <iostream>
using namespace std;

int fac(int num){
    if (num > 1)
        return num * fac(num-1);  // num: 해결된 부분  // fac(num-1): 남은부분
    else
        return 1;
}

int main() {
    int num;
    cin >> num;
    cout << fac(num);
}

이때, 재귀를 멈추는 부분 

if (num > 1)
    return num * fac(num-1);
else
    return 1;

위와 같은 재귀를 멈추는 부분이 없다면 시스템 stack을 모두 사용한 이후 Err가 발생하며 멈출 것이다. (stackoverflow)

이렇게 반복에 비해 알고리즘을 훨씬 명확하고 간결하게 나타낼 수 있다는 장점이 있으나 아래와 같이 수행속도면에서는 현저히 떨어지는 것을 볼 수 있다.

※ Recursion의 시간복잡도

재귀는 작은 동일한 문제들로 분해하여 해결하는 방법인 분할정복 알고리즘의 일종이다.

5! -> 4! -> 3! -> 2! -> 1! 으로 작은 문제 즉, 본래의 problem을 subproblem으로 나누어 최소 size부터 해결하는 방식이다.

최소 subproblem부터 다시 본래의 problem size로 돌아가면서 정복하는, 이런 방식을 분할정복 알고리즘이라 부른다.

그렇다면 이런 재귀함수의 시간복잡도 즉, 성능은 어떻게 될까?

이를 위한 예시는 피보나치 수열문제로 한다.

int fib(int num){
    if (num <= 1)
        return num; 
    else
        return fib(num-1) + fib(num-2);
}

위의 문제에서 피보나치식의 n번째 계산을 위한 연산횟수를 T(n)이라 하자.

T(0) = 1, T(1) = 1이므로 

T(n) = T(n-1) + T(n-2) + 1 > 2 x T(n-2) > 2x2 x T(n-4) > . . . 2 ^ (n/2) x T(0)이므로 

int fib(int num){
    int arr[100] = { 0, 1, };
    if (num < 2 || arr[num] != 0)
        return arr[num];
    else{
        arr[num] = fib(num-1) + fib(num-2);
        return arr[num];
    }
}

그렇다면 다음 예제는 어떨까?

이 기법은 이미 구한 값을 메모리에 저장해두고 다시 사용하는 메모이제이션 (memoization)을 채택한 방법이다.

위 방법의 시간복잡도를 구해보면

T(0) = 1, T(1) = 1이고

T(2) = T(1) + T(0) + 1 = 3

T(3) = T(2) + T(1) + 1 = 5

T(4) = T(3) + T(2) + 1에서 T(2)는 저장한 피보나치 수를 가져오기만 하면 되기 때문에 T(2) = 1이다.

T(3) + T(2) + 1 = 7이고, 같은 이유로 T(5) = T(4) + T(3) + 1에서 T(3) = 1이므로 T(5) = 9이다.

따라서 T(n) = 2n - 1이라고 할 수 이므로

※ 다중 순환 (multiple recursion)

재귀함수는 아래와 같이  3종류로 나눌 수 있다.

- 선형 순환 (linear recursion)

  ex) 팩토리얼계산, 거듭제곱 계산

- 이진 순환 (binary recursion)

  ex) 피보나치수열, 하노이탑 문제

- 다중 순환 (multiple recursion)