재귀함수와 자료구조 스택에 대해서 알아보자 (스테픈 2km)
알고리즘 문제를 풀다보면 재귀함수를 사용해야 하는 경우가 발생한다.
물론 그외에 대부분의 경우 (포트폴리오 작업등) 에서는 딱히 재귀함수를 사용할 일이 없었다.
대부분의 경우 반복문 혹은 중첩 반복문만 사용해도 원하는 기능은 전부 구현이 가능했기 때문인데.
재귀함수의 개념도 이해하고 익숙하게 사용하기 위해서 한번 정리해본다.
재귀의 말 그대로 함수에서 자기 자신을 다시 호출해 작업을 수행하는 방식이다
특정 분기까지 자기 자신을 계속해서 호출하는데, 주로 반복문을 구현할 때 사용한다.
우리가 흔히 알고 있는 반복문은 for, while 등이 있는데,
이러한 반복문으로 구현가능한 로직은 모두 재귀함수로도 가능하고 그 반대 역시 가능하다.
일단 몇가지 상황을 반복문과 재귀함수로 작성해서 동일하게 작동하는지를 테스트 해보자
간단하게 1에서 100까지의 합을 구해보는 식을 짜보겠다.
반복문으로 처리하면 보통 이런식으로 작성할것이다.
결과값은 5050이 나오게된다.
반복문이 돌아가는걸 보면
result 변수에 반복문이 1씩 증가하면서 result = result + i(0 -> 100까지 ) 루프가 돌때마다 이 과정이
100번 반복된다.
그럼 이러한 과정을 반복문이 아닌 재귀함수를 사용하면 어떻게 작성할 수 있을까?
재귀함수는 일단 함수 내에서 결과값으로 본인의 함수를 다시 부르는것으로
반드시 탈출조건이 필요하다.
이 조건이 없다면 반복문을 무한하게 돌리는것처럼 무한하게 돌게된다.
함수의 탈출조건을 적어두고 그밑에 반복 계산할 값을 리턴에 재귀함수를 넣어서 반복을 시킨다.
반복문과 재귀함수가 어떻게 값이 증감하는지 확인해보기 위해 콘솔에 찍어보겠다.
반복문의 i 값과
재귀함수의 파라매터의 값 변화를 살펴보자
반복문의 조건 처럼 0부터 100까지 증가한다
재귀함수는
0에서 100까지 증가하도록 짜여져 있어서
반복문과 동일하게 동작한다.
재귀함수에 대해서 이해하려면 스택이라는 자료구조에 대해서 알아야한다.
- 데이터를 집어넣을 수 있는 선형(linear) 자료형이다.
- 나중에 집어넣은 데이터가 먼저 나온다. 이 특징을 줄여서 LIFO(Last In First Out)라고 부른다.
- 데이터를 집어넣는 push, 데이터를 추출하는 pop, 맨 나중에 집어넣은 데이터를 확인하는 peek 등의 작업을 할 수 있다.
앞서 작성했던 재귀함수의 진행과정을 풀어서 한번 적어보자
첫번째 호출
두번째 호출
....
이런식으로 5번째 호출
이 과정이 총 100번 반복
재귀 함수의 핵심은 반환값이다.
계산 결과가 즉시 구해지는 것이 아니라
재귀호출로 (n + 1)을 계속 전달하다가 종료 조건인 n이 100일 때의 값 100을 반환하면서
n과 더하고 다시 결괏값을 반환하는 과정을 반복한다
재귀 함수의 마지막 호출은
if num == 100 종료 조건을 만나서 100을 반환한다.
그 뒤 100과 99를 더해서 199를 반환하고, 199에 98을 더해서 297을 반환하고..
이 과정을 함수가 처음 실행된 num = 0 까지 반환하여 돌아가며
5050의 결과값이 나오게 된다.
재귀 함수에서는 동일한 함수를 계속해서 호출될 때마다 함수를 위한 메모리가 계속해서 할당된다.
함수가 호출될 때마다 사용되는 임시 저장 메모리를 스택이라고 부른다
재귀 함수를 이용하다보면 함수가 종료되지 않고, 함수가 계속해서 호출이 되는데 이 경우 스택 공간이 초과되는 스택 오버플로(stack overfolw)가 발생하여 오류가 생긴다.
그렇기 때문에 재귀를 사용할 떄는 과도하게 스택 메모리가 사용되지 않도록 주의해야 한다.
- 재귀함수 정리
- 코드가 간결해지고 수정이 용이
- 변수를 여러 개 사용할 필요가 없음
- 코드의 흐름을 직관적으로 파악하기 어려움
- 탈출조건등을 꼭 넣어야함
- 반복하여 메서드를 호출하므로 메모리를 많이 사용하게됨
- 스택오버 플로우
- 상황에 따라 반복문보다 속도가 느릴수 있다.
-시간복잡도 문제
스테픈 2km완료했다.
휴우
