<div id="readability-page-1" class="page"><div role="banner"> <div> <h2>재귀와 꼬리 재귀</h2> <h4>28 May 2024</h4> Reading time ~2 minutes  </div> <h2 id="재귀-와-꼬리-재귀">재귀 와 꼬리 재귀</h2> <h2 id="재귀recursion">재귀(Recursion)</h2> 재귀(Recursion)는 함수가 자기 자신을 호출하는 프로그래밍 기법입니다. 이는 함수가 자신을 호출할 때마다 새로운 인스턴스가 생성되어 실행됩니다. 재귀를 사용하면 문제를 더 작은 부분 문제로 나누어 해결할 수 있습니다. 일반적으로 재귀 함수는 기본 사례(base case)에 도달할 때까지 자기 자신을 호출하며, 이를 통해 문제를 해결합니다. 예를 들어, 팩토리얼 함수를 재귀적으로 구현할 수 있습니다. n의 팩토리얼은 n이 1일 때까지 n과 n-1의 팩토리얼의 곱입니다. 따라서 다음과 같이 함수를 정의할 수 있습니다: <div><pre><code>
function factorial(n) {
 if (n === 0) {
 return 1;
 } else {
 return n * factorial(n - 1);
 }
}

console.log(factorial(5)); // Output: 120
</code></pre></div> 이 함수는 자기 자신을 호출하여 n과 n-1의 팩토리얼을 곱하고, n이 0이 될 때까지 이 과정을 반복합니다. <h3 id="일반적인-재귀-함수">일반적인 재귀 함수</h3> <ol> <li>함수 호출 스택이 생성됩니다.</li> <li>재귀 호출이 발생할 때마다 호출 스택에 새로운 프레임이 추가됩니다.</li> <li>각 프레임은 해당 호출에 필요한 인수와 지역 변수를 저장합니다.</li> <li>재귀 호출이 종료될 때마다 호출 스택에서 해당 프레임이 제거됩니다.</li> </ol> <h2 id="꼬리-재귀-tail-recursion">꼬리 재귀 (Tail Recursion)</h2> 반면, 꼬리 재귀(Tail Recursion)는 함수의 마지막 부분에서 자신을 호출하는 형태의 재귀를 말합니다. 이때 재귀 호출이 함수의 마지막 작업으로 이루어지며, 이를 통해 스택 오버플로우(Stack Overflow)를 방지할 수 있습니다. 일부 언어 및 런타임은 꼬리 재귀를 인식하여 스택을 재사용하거나 최적화하는 경우가 있습니다. 꼬리 재귀의 예제는 이전에 제공된 팩토리얼 함수입니다. 이를 꼬리 재귀로 수정하면 다음과 같습니다: <div><pre><code>
function factorial(n, result = 1) {
 if (n === 0) {
 return result;
 } else {
 return factorial(n - 1, n * result);
 }
}

console.log(factorial(5)); // Output: 120
</code></pre></div> 이 함수에서 재귀 호출은 마지막 작업으로 이루어지므로 꼬리 재귀로 간주됩니다. 이러한 형태의 재귀는 스택 오버플로우를 방지할 수 있도록 최적화될 수 있습니다. <h3 id="꼬리-재귀-함수">꼬리 재귀 함수</h3> <ol> <li>함수 호출 스택이 생성됩니다.</li> <li>꼬리 재귀 함수의 경우, 재귀 호출은 마지막 작업으로 수행되므로 스택에 새로운 프레임이 추가되지 않습니다.</li> <li>대신에 현재 프레임이 재사용되어 인수와 지역 변수가 업데이트됩니다.</li> <li>재귀 호출이 반복될 때마다 현재 프레임이 업데이트되어 이전 프레임이 제거되는 것은 마찬가지입니다.</li> </ol> <h2 id="참고-자료">참고 자료</h2> <ul> <li><a href="https://wonit.tistory.com/483">[배워보자 Spring Data JPA] JPA 에서 Pageable 을 이용한 페이징과 정렬</a></li> </ul> </div></div>

lahuman

Daniel Lim

재귀 와 꼬리 재귀
재귀(Recursion)
재귀(Recursion)는 함수가 자기 자신을 호출하는 프로그래밍 기법입니다. 이는 함수가 자신을 호출할 때마다 새로운 인스턴스가 생성되어 실행됩니다. 재귀를 사용하면 문제를 더 작은 부분 문제로 나누어 해결할 수 있습니다. 일반적으로 재귀 함수는 기본 사례(base case)에 도달할 때까지 자기 자신을 호출하며, 이를 통해 문제를 해결합니다.
예를 들어, 팩토리얼 함수를 재귀적으로 구현할 수 있습니다. n의 팩토리얼은 n이 1일 때까지 n과 n-1의 팩토리얼의 곱입니다. 따라서 다음과 같이 함수를 정의할 수 있습니다:
function factorial(n) {
    if (n === 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}
console.log(factorial(5)); // Output: 120
이 함수는 자기 자신을 호출하여 n과 n-1의 팩토리얼을 곱하고, n이 0이 될 때까지 이 과정을 반복합니다.
일반적인 재귀 함수
함수 호출 스택이 생성됩니다.
재귀 호출이 발생할 때마다 호출 스택에 새로운 프레임이 추가됩니다.
각 프레임은 해당 호출에 필요한 인수와 지역 변수를 저장합니다.
재귀 호출이 종료될 때마다 호출 스택에서 해당 프레임이 제거됩니다.
꼬리 재귀 (Tail Recursion)
반면, 꼬리 재귀(Tail Recursion)는 함수의 마지막 부분에서 자신을 호출하는 형태의 재귀를 말합니다. 이때 재귀 호출이 함수의 마지막 작업으로 이루어지며, 이를 통해 스택 오버플로우(Stack Overflow)를 방지할 수 있습니다. 일부 언어 및 런타임은 꼬리 재귀를 인식하여 스택을 재사용하거나 최적화하는 경우가 있습니다.
꼬리 재귀의 예제는 이전에 제공된 팩토리얼 함수입니다. 이를 꼬리 재귀로 수정하면 다음과 같습니다:
function factorial(n, result = 1) {
    if (n === 0) {
        return result;
    } else {
        return factorial(n - 1, n * result);
    }
}
console.log(factorial(5)); // Output: 120
이 함수에서 재귀 호출은 마지막 작업으로 이루어지므로 꼬리 재귀로 간주됩니다. 이러한 형태의 재귀는 스택 오버플로우를 방지할 수 있도록 최적화될 수 있습니다.
꼬리 재귀 함수
함수 호출 스택이 생성됩니다.
꼬리 재귀 함수의 경우, 재귀 호출은 마지막 작업으로 수행되므로 스택에 새로운 프레임이 추가되지 않습니다.
대신에 현재 프레임이 재사용되어 인수와 지역 변수가 업데이트됩니다.
재귀 호출이 반복될 때마다 현재 프레임이 업데이트되어 이전 프레임이 제거되는 것은 마찬가지입니다.
참고 자료
[배워보자 Spring Data JPA] JPA 에서 Pageable 을 이용한 페이징과 정렬

재귀와 꼬리 재귀

댓글