[알고리즘] 재귀함수에 관하여

• DFS 와 BFS를 구현하려면 재귀 함수의 이해가 필요
• 영어로는 recursive function이라고 한다
• 재귀함수란 자기 자신을 다시 호출하는 함수를 의미

function recursiveFunction() {
  console.log("This is a recursive function");
  return recursiveFunction();
}

• 재귀함수 종료 조건이 없으면 다음의 에러가 나타난다

Maximum call stack size exceeded

• 재귀함수는 stack 자료구조를 이용한다
  • 가장 마지막에 호출한 함수가 끝나야 그 앞의 호출이 종료된다

재귀 함수 종료 조건

• 재귀함수를 사용할때는 종료 조건이 꼭 필요
• 종료 조건이 없으면 에러 뜰때까지 무한 호출 
• 종료할때 if 문 안에 return을 사용한다

function recursiveFunction(i) {
  console.log(`on ${i}th step`);
  if (i === 10) return;
  recursiveFunction(i+1);
}

재귀 함수 장점

• 코드가 간결해진다

재귀 함수 단점

• Stack 자료구조를 사용하므로 메모리 과도화에 취약하다

비재귀 함수 장점

• Maximum call stack exceeded 에러로부터 보다 자유로워진다

비재귀 함수 단점

• 코드가 읽기 어렵다

재귀 함수를 비재귀 함수로

• 유형 1 - 실제로 작업하는 부분이 앞에 있는 경우

recursive(인자 리스트)
{
    if (종료 조건)
    {
        종료 처리
    }
    else
    {
        process(인자 리스트)
        recursive(변경된 인자 1)
        recursive(변경된 인자 2)
    }
}

출처: https://steadyandslow.tistory.com/117 [더디지만... 꾸준히...]

를 다음으로 변경:

non_recursive(인자 리스트)
{
    /* 스택의 초기화 */
    init_stack()
    push(인자 리스트)
    /* 스택이 비면 끝 */
    while(!is_stack_empty())
    {
        인자 리스트 = pop()
        if(!종료 조건)
        {
            process(인자 리스트)
            push(변경된 인자 1)
            push(변경된 인자 2)
        }
        /* 종료 조건이면 */
        else
        {
            종료 처리
        }
}


출처: https://steadyandslow.tistory.com/117 [더디지만... 꾸준히...]

•  유형 2 - 실제로 작업하는 부분이 중간에 있는 경우

recursive(인자 리스트)
{
    지역 변수들
    if (종료 조건)
    {
        종료 처리
    }
    else
    {
        recursive(변경된 인자 1)
        process(인자 리스트)
        recursive(변경된 인자 2)
    }
}


출처: https://steadyandslow.tistory.com/117 [더디지만... 꾸준히...]

를 다음으로 변경:

non_recursive(인자 리스트)
{
    /* 작업을 완료 했은지를 확인하기 위한 Flag */
    let done = false;
    /* 스택의 초기화 */
    init_stack()
    while(!done)
    {
        while(!종료 조건)
        {
            push(인자 리스트)
            인자 리스트 = 변화된 인자 1
        }
        종료 처리
        if(!is_stack_empty())
        {
            인자 리스트 = pop()
            process(인자 리스트)
            인자 리스트 = 변화된 인자 2
        }
        else
        {
            done = true
        }
}


출처: https://steadyandslow.tistory.com/117 [더디지만... 꾸준히...]

•  유형 3 - 실제로 작업하는 부분이 아래에 있는 경우

recursive(인자 리스트)
{
    지역 변수들
    if (종료 조건)
    {
        종료 처리
    }
    else
    {
        recursive(변경된 인자 1)
        recursive(변경된 인자 2)
        process(인자 리스트)
    }
}


출처: https://steadyandslow.tistory.com/117 [더디지만... 꾸준히...]

를 다음으로 변경:

non_recursive(인자 리스트)
{
    /* 작업을 완료 했은지를 확인하기 위한 Flag */
    let done = false;
    /* 무한 루프를 방지하기 위한 방책 */
    인자 리스트의 복사본
    /* 스택의 초기화 */
    init_stack()
    while(!done)
    {
        while(!종료 조건)
        {
            push(인자 리스트)
            인자 리스트 = 변화된 인자 1
        }
        종료 처리
        if(!is_stack_empty())
        {
            인자 리스트 복사본 = 인자 리스트
            인자 리스트 = pop()
            if (인자 2로의 변화가 종료 조건이 아니면)
            {
                if(인자 2로의 변화 == 인자 리스트의 복사본)
                {
                    process(인자 리스트)
                }
                else
                {
                    push(인자 리스트)
                    인자 리스트 = 변화된 인자 2
                    break
                }
            }
        }
        else
        {
            process(인자 리스트)
        }
        if(is_stack_empty)
        {
            done = true
        }
}


출처: https://steadyandslow.tistory.com/117 [더디지만... 꾸준히...]

참고

1. 재귀 호출 - 재귀 함수를 비재귀 함수로, 더디지만... 꾸준히...: https://steadyandslow.tistory.com/11
   
2. 이것이 취업을 위한 코딩 테스트다 with 파이썬, 나동빈: https://books.google.ca/books?id=vBz-DwAAQBAJ&source=gbs_book_other_versions