재귀는 다른곳에서 언어의 기반이 되기도 하지만

알고리즘에서 재귀는 반복문의 대체제라고 볼 수 있다


이중 삼중포문을 쓰면 효과가 떨어지는 문제가 분명히 존재하고

이때 재귀를 이용하면 간단하게 해결할 수 있는 경우가 있다


재귀함수는 알고리즘에서 스택을 이용한 깊이우선탐색이다



위 예제에서

2를 입력하고


프린트함수를 DFS(x-1)위에 두면

2 1이 출력되고


프린트 함수를 DFS(x-1)아래에 두면

1 2가 출력되는데

이렇게 되는 이유는 재귀함수는 스택을 활용하기 때문이다



재귀함수가 작동하는 방식


ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ


STEP1 - DFS(2)

함수가 실행될때는 코드영역, 데이터영역, 스택영역, 힙영역중

메모리의 스택영역에 스택프레임이라는 이름으로 기록된다

여러 정보가 있지만 세가지 핵심적인 정보를 기록하며 이해해보자


처음에 DFS(2)함수에

매개변수 x가 초기화되고 여기에 3이 할당된 뒤

복귀할 반환주소를 받는데 편의상 main의 19라인이라고 부르자

이런내용이 기록되면서 DFS(2)가 작동한다


스택이 쌓이고난 뒤 DFS(2)에서는

0보다크니까 DFS(1)를 실행하고

DFS(2)는 대기한다


ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ


STEP2 - DFS(1)

DFS(2)의 매개변수와 다른

매개변수 x가 초기화되고 여기에 2가 할당된 뒤

복귀할 반환주소 DFS(2)의 3라인이 기록된다


스택이 쌓이고난 뒤 DFS(1)에서는

0보다 크니까 DFS(0)을 실행하고

DFS(1)는 대기한다


ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ



ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

STEP3 - DFS(0)

DFS(2)와 DFS(1)의 매개변수와 다른

매개변수 x가 초기화되고 여기에 1이 할당된 뒤

복귀할 반환주소 DFS(1)의 3라인이 기록된다


스택이 쌓이고 난 뒤 DFS(0)에서는

0보다 크지않으니까 바로 종료된 이후에

자신의 스택프레임이 지워지고


복귀주소 DFS(1)의 3라인으로 돌아간다

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ


STEP4 - DFS(1)

DFS(1)이 실행되고 자신의 스택프레임이 지워지고


복귀주소 DFS(2)의 3라인으로 돌아간다

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ


STEP5 - DFS(2)

DFS(2)가 실행되고 자신의 스택프레임이 지워지고

복귀주소 main의 19라인으로 복귀한다


ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ


1.프린트문이 재귀함수 앞에 있을때

DFS(x) 재귀함수에 들어가기 전에 프린트를 찍으면

2가 찍힌 뒤 DFS(1)안에서 1이 찍혀서

2 1이 프린트 되고


2.프린트문이 재귀함수 뒤에 있을때

DFS(x) 재귀함수에 들어간 후에 프린트를 찍으면

뒤 DFS(2) DFS(1) DFS(0)에 들어갔다가 나오면서 숫자가 찍히므로

DFS(0)에서는 조건문안에 못들어가서 출력이 안되고


DFS(0)에서 나와 복귀주소 DFS(1)의 4라인에서 1이 출력되고

DFS(1)에서 나와 복귀주소 DFS(2)의 4라인에서 2가 출력되어

1 2가 프린트된다


꿈★은 이루어진다

내일채움공제 되는 중소기업 가자 화이팅!