스택을 사용하여 재귀를 반복으로 변환: 실용 가이드-JS 튜토리얼-php.cn

Converting Recursion to Iteration Using a Stack: A Practical Guide

재귀는 컴퓨터 과학의 강력한 기술로, 트리 순회, 깊이 우선 검색, 역추적 알고리즘과 같은 작업에 자주 사용됩니다. 그러나 재귀는 함수 호출의 오버헤드와 호출 스택 유지로 인해 시간과 공간 측면에서 효율성이 떨어질 수 있습니다. 어떤 경우에는 재귀 호출을 시뮬레이션하기 위해 명시적 스택을 사용하여 재귀를 반복 접근 방식으로 변환하는 것이 좋습니다. 이 문서에서는 JavaScript의 스택을 사용하여 재귀 알고리즘을 반복 알고리즘으로 변환하는 방법에 대한 단계별 가이드를 제공합니다.

재귀를 반복으로 변환하는 이유는 무엇입니까?

재귀를 반복으로 변환하려는 데에는 여러 가지 이유가 있습니다.

스택 오버플로: 심층 재귀 호출은 호출 스택을 소진시켜 스택 오버플로로 이어질 수 있습니다. 명시적 스택을 사용하면 이 문제를 피할 수 있습니다.
효율성: 반복 솔루션은 호출 스택을 유지 관리하는 데 드는 오버헤드가 필요하지 않으므로 일반적으로 메모리 효율성이 더 높습니다.
더 나은 제어: 명시적 스택을 사용하면 특히 역추적과 관련된 경우 알고리즘 실행을 더 효과적으로 제어할 수 있습니다.

스택을 사용하여 재귀를 반복으로 변환하기 위한 템플릿

스택을 사용하여 재귀 함수를 반복 함수로 변환할 때 일반적인 접근 방식은 다양한 유형의 알고리즘(예: 트리 순회, 역추적 문제 또는 그래프 순회)에서 유사하게 유지됩니다. 다음은 다양한 시나리오에 적용할 수 있는 유연한 템플릿입니다.

일반 템플릿

1. 재귀함수(예시)

function recursiveFunction(args) {
    // Base case
    if (baseCondition) {
        // Handle the base case
        return;
    }

    // Recursive calls
    for (let i = 0; i < someLimit; i++) {
        recursiveFunction(newArgs);
    }
}

로그인 후 복사

2. 스택을 이용한 반복 함수

위의 재귀 함수를 반복 함수로 변환하려면 다음 단계를 따르세요.

function iterativeFunction(args) {
    // Initialize the stack
    let stack = [initialState];

    // Loop until the stack is empty
    while (stack.length > 0) {
        // Pop the current state from the stack
        let currentState = stack.pop();

        // Handle the base case (optional, since we can check on each iteration)
        if (baseCondition) {
            continue;  // Skip or handle the base case
        }

        // Process the current state
        processState(currentState);

        // Push next states onto the stack
        for (let i = 0; i < someLimit; i++) {
            let newState = generateNewState(currentState, i);
            stack.push(newState);
        }
    }
}

로그인 후 복사

템플릿 분석

스택 초기화:

스택은 시작 상태로 초기화되어야 하며, 이는 초기 인수 또는 순회의 첫 번째 노드일 수 있습니다.
스택을 통한 루프:

스택에 원래 함수에서 수행된 재귀 호출을 나타내는 항목이 있는 한 루프는 계속됩니다.
기본 조건 처리:

재귀에서 기본 조건은 추가 재귀가 필요한지 확인합니다. 반복 접근 방식에서는 루프 내에서 동일한 검사를 수행할 수 있습니다. 기본 조건이 충족되면 계속해서 추가 처리를 건너뛰어도 됩니다.
현재 상태 처리:

현재 반복의 상태를 처리합니다(현재 재귀 호출에서 발생하는 처리와 동일).
다음 상태 푸시:

재귀 함수가 새로운 재귀 함수를 호출하는 것처럼 여기에서는 다음 상태(예: 처리할 함수 인수 또는 노드)를 스택에 푸시합니다.

변환 예: 순서대로 트리 순회

재귀 버전:

function recursiveFunction(args) {
    // Base case
    if (baseCondition) {
        // Handle the base case
        return;
    }

    // Recursive calls
    for (let i = 0; i < someLimit; i++) {
        recursiveFunction(newArgs);
    }
}

로그인 후 복사

스택을 사용한 반복 버전:

function iterativeFunction(args) {
    // Initialize the stack
    let stack = [initialState];

    // Loop until the stack is empty
    while (stack.length > 0) {
        // Pop the current state from the stack
        let currentState = stack.pop();

        // Handle the base case (optional, since we can check on each iteration)
        if (baseCondition) {
            continue;  // Skip or handle the base case
        }

        // Process the current state
        processState(currentState);

        // Push next states onto the stack
        for (let i = 0; i < someLimit; i++) {
            let newState = generateNewState(currentState, i);
            stack.push(newState);
        }
    }
}

로그인 후 복사

재귀를 반복으로 변환하는 예

예제 1: 그래프의 깊이 우선 검색(DFS)

깊이 우선 검색(DFS)은 일반적으로 재귀를 사용하여 구현됩니다. 재귀 DFS 알고리즘은 다음과 같습니다.

function inorderTraversal(root) {
    if (root === null) return;
    inorderTraversal(root.left);
    console.log(root.value);
    inorderTraversal(root.right);
}

로그인 후 복사

스택을 사용한 반복 버전:

function inorderTraversalIterative(root) {
    let stack = [];
    let current = root;

    while (stack.length > 0 || current !== null) {
        // Reach the leftmost node
        while (current !== null) {
            stack.push(current);
            current = current.left;
        }

        // Visit the node
        current = stack.pop();
        console.log(current.value);

        // Move to the right node
        current = current.right;
    }
}

로그인 후 복사

이 예에서는 스택이 방문할 노드를 명시적으로 보유하고 있으며 루프를 사용하여 재귀 호출을 시뮬레이션합니다.

예 2: 순서대로 트리 순회(반복)

이진 트리의 순차 순회는 일반적으로 재귀적으로 수행됩니다. 재귀 버전은 다음과 같습니다.

function dfs(graph, node, visited = new Set()) {
    if (visited.has(node)) return;
    console.log(node);
    visited.add(node);

    for (let neighbor of graph[node]) {
        dfs(graph, neighbor, visited);
    }
}

로그인 후 복사

스택을 사용한 반복 버전:

function dfsIterative(graph, startNode) {
    let stack = [startNode];
    let visited = new Set();

    while (stack.length > 0) {
        let node = stack.pop();

        if (visited.has(node)) continue;

        console.log(node);
        visited.add(node);

        // Add neighbors to the stack in reverse order to maintain DFS order
        for (let neighbor of graph[node].reverse()) {
            if (!visited.has(neighbor)) {
                stack.push(neighbor);
            }
        }
    }
}

로그인 후 복사

이 경우 스택은 방문할 노드를 추적하는 데 도움이 되며 내부 루프는 가장 왼쪽 노드에 도달할 때까지 트리의 왼쪽을 따라 이동합니다.

예 3: 하위 집합 생성(역추적)

세트의 하위 세트를 생성하기 위한 역추적 접근 방식은 다음과 같이 재귀적으로 구현할 수 있습니다.

function inorderTraversal(root) {
    if (root === null) return;
    inorderTraversal(root.left);
    console.log(root.value);
    inorderTraversal(root.right);
}

로그인 후 복사

스택을 사용한 반복 버전:

function inorderTraversalIterative(root) {
    let stack = [];
    let current = root;

    while (stack.length > 0 || current !== null) {
        // Reach the leftmost node
        while (current !== null) {
            stack.push(current);
            current = current.left;
        }

        // Visit the node
        current = stack.pop();
        console.log(current.value);

        // Move to the right node
        current = current.right;
    }
}

로그인 후 복사

반복 버전은 스택을 사용하여 재귀 함수 호출을 시뮬레이션합니다. currentSubset은 내부에서 수정되고 스택은 새 상태를 푸시하여 역추적을 처리합니다.

예 4: 순열 생성

세트의 모든 순열을 생성하려면 일반적으로 재귀가 사용됩니다.

function subsets(nums) {
    let result = [];
    function backtrack(start, currentSubset) {
        result.push([...currentSubset]);
        for (let i = start; i < nums.length; i++) {
            currentSubset.push(nums[i]);
            backtrack(i + 1, currentSubset);
            currentSubset.pop();
        }
    }
    backtrack(0, []);
    return result;
}

로그인 후 복사

스택을 사용한 반복 버전:

function subsetsIterative(nums) {
    let stack = [{start: 0, currentSubset: []}];
    let result = [];

    while (stack.length > 0) {
        let { start, currentSubset } = stack.pop();
        result.push([...currentSubset]);

        // Explore subsets by including elements from `start` onwards
        for (let i = start; i < nums.length; i++) {
            currentSubset.push(nums[i]);
            stack.push({ start: i + 1, currentSubset: [...currentSubset] });
            currentSubset.pop(); // backtrack
        }
    }

    return result;
}

로그인 후 복사

이 반복 버전은 스택을 사용하여 순열의 현재 상태를 저장합니다. 역추적은 스택에서 상태를 푸시하고 팝하여 처리됩니다.

예제 5: N-Queens 문제(역추적)

N-Queens 문제는 재귀 역추적을 사용하여 해결되는 경우가 많습니다.

function permute(nums) {
    let result = [];
    function backtrack(start) {
        if (start === nums.length) {
            result.push([...nums]);
            return;
        }
        for (let i = start; i < nums.length; i++) {
            [nums[start], nums[i]] = [nums[i], nums[start]];  // swap
            backtrack(start + 1);
            [nums[start], nums[i]] = [nums[i], nums[start]];  // backtrack (swap back)
        }
    }
    backtrack(0);
    return result;
}

로그인 후 복사

스택을 사용한 반복 버전:

function recursiveFunction(args) {
    // Base case
    if (baseCondition) {
        // Handle the base case
        return;
    }

    // Recursive calls
    for (let i = 0; i < someLimit; i++) {
        recursiveFunction(newArgs);
    }
}

로그인 후 복사

결론

스택을 사용하여 재귀를 반복으로 변환하는 것은 많은 알고리즘, 특히 역추적 또는 트리/그래프 순회와 관련된 알고리즘에 유용한 기술입니다. 명시적 스택을 사용하면 깊은 재귀를 방지하고 함수 상태를 수동으로 관리하며 알고리즘 실행을 더 효과적으로 제어할 수 있습니다. 이러한 예는 자신의 코드에서 유사한 문제를 해결하는 데 도움이 되는 가이드 역할을 합니다.

위 내용은 스택을 사용하여 재귀를 반복으로 변환: 실용 가이드의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!