재귀함수 (Recursive Function) 이해하기

- 목차

 

 

관련된 글

Call Stack 이해하기

Call Stack 이해하기

 

소개.

재귀함수란 어떤 함수가 자기 자신을 호출하는 형태의 함수입니다.
왜 자기 자신의 호출할까요?
재귀함수 형태로 해결할 수 있는 문제들이 있는데요.
대표적인 문제가
- 팩토리얼 구현하기
- 피보나치 수열의 합구하기
- binary tree search
등이 있습니다.
 
이 모두 공통점이 있는데요.
List 를 활용하는 문제라는 점입니다.
필요충분조건은 아니지만 List 자료구조를 사용하는 알고리즘의 경우에는 Recursive Function 형태로 해결이 가능합니다.
예를 들어 수열의 사칙연산이나 정렬 문제 등이 이에 해당합니다.
 
List 자료구조에 대한 문제를 해결하는데에 Recursive Function 이 적용 가능한 이유는 Recursive Function 은 Stack 자료구조를 활용하기 때문입니다.
Recursive Function 은 자체적인 Call Stack 을 활용하며, Thread 별로 하나의 Call Stack 이 생성됩니다.
그래서 List 와 Stack 의 호환되는 특성 아래에서 해결할 수 있는 문제라면 Recursive Function 으로 해당 문제들을 해결할 수 있습니다.
 
자세한 이야기는 충분한 예시와 함께 진행하도록 하겠습니다.
 

Assembly Code.

먼저 Recursive Function 의 Assembly Code 형태를 한번 보겠습니다.
Chat-GPT 에서 가져온 코드인데요.
주목할 점은 factorial 내부에서 call factorial 을 실행한다는 점입니다.
이전에 작성한 글인 Call Stack 이해하기 을 한번 읽어보시면 이해에 도움이 될 수 있어 첨부하겠습니다.
 

section .text
global factorial   ; Entry point for the program

_start:
    mov ebx, 10
    jmp factorial	

factorial:
    ; Function prologue
    push ebp         ; Save the current base pointer
    mov ebp, esp     ; Set up a new base pointer
    push ebx         ; Save ebx, which is a callee-saved register

    ; Function body
    mov eax, [ebp+8] ; Load the argument (n) into eax

    ; Base case: if n <= 1, return 1
    cmp eax, 1
    jle .base_case

    ; Recursive case: calculate factorial(n-1)
    dec eax
    push eax        ; Push (n-1) onto the stack
    call factorial  ; Recursive call
    add esp, 4      ; Clean up the stack after the call

    ; Multiply the result of factorial(n-1) by n
    imul eax, [ebp+8]

    ; Function epilogue
    pop ebx         ; Restore ebx
    pop ebp         ; Restore the previous base pointer
    ret

.base_case:
    mov eax, 1      ; Return 1 for the base case
    jmp .done

.done:
    pop ebx         ; Restore ebx (in case we reached here directly)
    pop ebp         ; Restore the previous base pointer
    ret

위 Assembly Code 를 한번 풀어서 해석해보겠습니다.
 

push ebp;

factorial 함수 내부로 진입하면서 ebp 를 Call Stack 에 push 합니다.
이때의 ebp 는 main function 의 base pointer 로
main function 에 해당하는 Stack Frame 의 base pointer 입니다.
참고로 base pointer 는 함수의 Call Stack 의 가장 아래 위치입니다.
 

mov ebp, esp;

esp 레지스터의 값을 ebp 레지스터에 저장합니다.
이 행위의 문맥상 의미는 새로운 Stack Frame 을 생성하는 것인데요.
factorial 함수의 Stack Frame 을 만들기 위해서 ebp 는 새로운 값으로 설정합니다.
esp 는 Stack Pointer 로 Call Stack 에 값이 push, pop 될때마다 자동으로 Stack Pointer 는 1 씩 오르거나 내려갑니다.
ebp 에 esp 값을 저장한다는 말은 새로운 Base Pointer 를 만들고 factorial 함수의 새로운 Stack Frame 의 생성을 뜻합니다.
 

push ebx;

ebx 레지스터는 CPU 의 관점에서 일시적으로 사용되는 레지스터라기보다
오랜 기간동안 저장해야한 값들을 담는 레지스터입니다.
Recursive Function 의 경우, 여러 Stack Frame 에 걸쳐 유지되어야하는 값이 존재하기 때문에 ebx 레지스터를 사용합니다.
예를 들어, 1부터 1000까지 값을 Sum 하는 문제의 경우에는 Sum 의 결과값을 유지할 필요가 있습니다.
이러한 경우에 ebx 레지스터가 사용됩니다.
 

mov eax, [ebp+8];

ebp 레지스터는 Stack Frame 의 Base Pointer 입니다.
그리고 Call Stack 에 push 된 값에 접근할 때에는 ebp + 8 과 같은 형식으로 접근합니다.
4 bytes 시스템의 경우에는 ebp + 4, ebp + 8 와 같이 접근할 수 있습니다.
보통 Call Stack 은 이전 함수의 Base Pointer 를 push ebp 와 같은 형식으로 저장하기 때문에
함수의 첫번째 값은 ebp + 8 입니다.
 
factorial 함수의 시그니처는 "int factorial(int n)" 이므로 첫번째 인자인 n 은 ebp + 8 의 값을 가집니다.
그리고 n 을 eax 에 저장합니다.
 

Call Stack.

 

Pseudo code 로 1부터 N 까지의 순차적인 수열을 Sum 하는 함수를 구현해보았습니다.

function int sum_loop (int totalCount) {
	int counter = 0;
    int result = 0;
	while (counter <= totalCount) {
        result += counter;
        counter += 1;
    }
    
    return result;
}

function int sum_recursive(int n) {
	
    if (n == 0) {
    	return 0;
    }
	
    return n + sum_recursive(n - 1)
}

 

이를 Call Stack 과 레지스터 관점에서 이해해보겠습니다.

함수가 호출될 때, 함수의 인자는

mov eax, 1

push eax

와 같은 형식으로 Call Stack 에 쌓이게 됩니다.

 

sum_recursive(1).

Call Stack 
[

    1

] // 첫번째 Stack Frame

 

sum_recursive(2).

Call Stack 
[

    [
    
    	2
    
    ] // 두번째 Stack Frame

    1

] // 첫번째 Stack Frame

 

sum_recursive(3).

Call Stack 
[

    [
    
        [
    
            3
    
        ] // 세번째 Stack Frame    
    
    
    	2
    
    ] // 두번째 Stack Frame

    1

] // 첫번째 Stack Frame

 

Recursive 함수는 종료조건이 되기 전까지 Call Stack 에 모든 함수의 인자들이 쌓이게 됩니다.

그래서 sum_recursive(4) 인 경우의 Call Stack 은 아래와 같이 됩니다.

Call Stack
[
    4,
    3,
    2,
    1
]

 

그리고 종료조건이 후에 Call Stack 을 Pop 하면서 Sum, Multiply 등의 연산을 수행하여 함수의 실행이 완료됩니다.

예시.

 

Factorial 예시.

1 ~ N 인 수열에 대하여 Factorial 연산을 수행하는 것은 Recursive Function 으로 구현할 수 있습니다.

그 이유는 1 ~ N 인 수열 은 List 와 Stack 으로 구현가능하기때문입니다.

function factorial_loop(n) {

    var counter = n;
    var result = 1;
    while (counter >= 1) {
        result = result * counter;
        counter = counter - 1;
    }

    return result;
    
}

function factorial_recursive(n) {

    if (n <= 1) return 1;

    return n * factorial(n - 1);
    
}

var result1 = factorial_loop(3);
var result2 = factorial_recursive(3);
console.log(result1)
console.log(result2)

 

factorial_recursive(10) 의 경우에 Call Stack 에 1 부터 10까지 값이 push 되며,

종료조건 이후에 하나씩 pop 되어 개별적인 곱셈 연산이 수행됩니다.

Call Stack 
[
    1,
    2,
    3,
    4,
    5,
    6,
    7,
    8,
    9,
    10

]

 

Fibonacci 예시.

피보나치 수열 또한 Recursive Function 으로 구현할 수 있습니다.

function fibonacci_loop(num) {
    
  var x = 0;
  var y = 1;
  var z;
  var i = 0;
  for (i = 2; i <= num; i++) {
    z = x + y;
    x = y;
    y = z;
  }
  return y;
}

function fibonacci_recursive(num) {

    if(num == 0) return 0;
    if(num == 1) return 1;

    return fibonacci_recursive(num - 1) + fibonacci_recursive(num - 2);
    
}


var result1 = fibonacci_loop(15);
var result2 = fibonacci_recursive(15);
console.log(result1);
console.log(result2);

// 1, 1, 2, 3, 5

 

fibonacci_recursive(5) 내부에서 실행되는 재귀함수들을 나열해보면 ,

 

fibonacci_recursive(5) =

fibonacci_recursive(4) + fibonacci_recursive(3) =

fibonacci_recursive(3) + fibonacci_recursive(2) + fibonacci_recursive(2) + fibonacci_recursive(1) =

fibonacci_recursive(2) + fibonacci_recursive(1) + fibonacci_recursive(1) + fibonacci_recursive(0) =

fibonacci_recursive(1) + fibonacci_recursive(0) + fibonacci_recursive(1) + fibonacci_recursive(1) + fibonacci_recursive(0)

 

이며 종료조건인 1 인 값들이 Call Stack 에 push 됩니다.

그리고 pop 되어 덧셈 연산이 수행됩니다.

 

Call Stack 

[
    1,
    1,
    1,
    1,
    1

]