티스토리 뷰

알고리즘

재귀 함수에 관하여

YG - 96년생 , 강아지 있음, 개발자 희망 2022. 3. 24. 03:38

재귀 함수란?

함수가 직접 또는 간접적으로 자신을 호출하는 프로세스를 재귀함수라고 합니다

재귀 알고리즘을 이용하면 복잡한 문제들도 간단하게 해결할 수 있습니다

반복문도 마찬가지지만 재귀함수도 종료지점을 제대로 생각하지 않고 구현을 하면 스택 오버 플로우가 발생할 수 있으니 항시 주의해서 구현을 해줘야합니다.

 

재귀 함수 예제

 

function solution(n) {
  function DFS(L) {
    if (L === 0) return;
    else {
      console.log(L);
      DFS(L - 1);
    }
  }
  DFS(n);
}

console.log(solution(3));

3 , 2 ,1 을 출력합니다

 

반대로 콘솔로그를 DFS 밑에 위치시키게 된다면

 

function solution(n) {
  function DFS(L) {
    if (L === 0) return;
    else {
      DFS(L - 1);
      console.log(L);
    }
  }
  DFS(n);
}

console.log(solution(3));

이러한 이유를 알기 위해서는 스택에 대하여 알아야 합니다.

 

스택이란?

- 메모리의 스택 영역은 함수의 호출과 관계되는 지역변수, 매개변수, 리턴 값등의 임시데이터를 저장합니다.

- 스택이란 단어는 차곡 차곡 쌓여진 더미를 의미합니다.

- LIFO(Last In First Out, 후입선출) 구조라고도 합니다.

 

 

이러한 스택의 정보에는 매개변수 L, 지역변수 , 복귀 주소 등 다양한 정보들이 담겨 있는데요.

 

여기에서 재귀 함수가 실행 될 때

 

function solution(n) {
  function DFS(L) {
    if (L === 0) return;
    else {
      DFS(L - 1);
      console.log(L);
    }
  }
  DFS(n);
}

console.log(solution(3));

이렇게 스택이 쌓이게 되고요

스택이 쌓인 것마다 자신이 어디에서 호출되었는지 정보를 가지고 하나씩 빠져나와서 다시 자신이 진행했던 곳을 기억하고 그 이후로부터 진행하는 방식입니다.

스택 pop으로 빠져 나가는 모습

 

알고리즘을 푸는 데 재귀함수를 이용한 DFS 나 BFS를 잘 사용하고 싶어서 공부하게 되었습니다.

 

 

댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/12   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
글 보관함