[개념정리]재귀_nabi

기록용

3줄 TMI

알고리즘 공부는 1학기 때 학교에서 의미와 구조를 살짝 배운 이후로 처음이다. 그냥 아예 처음이라고 생각해도 무방하다. 보안의 기초는 코딩이고 개발에 대해서도 잘 아는 정보보안전문가가 좋은 인재라고 생각한다. 그리고 나의 소소한(?) 코딩 실력을 높이려면 알고리즘 공부는 필수라고 생각한다.

 

---

컴퓨터 과학에 있어서 재귀(再歸, Recursion)는 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻하며, 이를 프로그래밍에 적용한 재귀 호출(Recursive call)의 형태로 많이 사용된다. 또 사진이나 그림 등에서 재귀의 형태를 사용하는 경우도 있다. - 위키백과

쉽게 말하면 자기 자신이라는 문제에 자신(조금 더 작은 경우의 수)을 불러와서 원래보다 더 간단하게 문제를 풀 수 있도록 하는 방법이다. 

사물을 예로 들자면 러시아 인형, 마트료시카를 말할 수 있을 것 같다.

 

이러한 재귀를 코딩에서 어떻게 활용하면 되는 것일까?

재귀의 의미와 같은 방식으로 활용하면 된다. 재귀를 쓰고자 할 때 자신의 함수 실행문을 넣어 계속 반복되게 하면 된다.

 

이렇게 설명을 하면 당연한 의문이 든다. 과연 어디에서 반복문을 멈춰야 할까?

자신의 하위 경우의 수가 base case에 도달했을 때 반복문을 끝내야 한다. base case 란 닶을 찾아 더 이상 자신을 호출할 필요가 없는 종료 case 라고 생각하면 된다. => 함수를 끝내는 조건

 

재귀를 사용하게 되면 주의해야 할 점이 있다. 이 점을 유의해서 코딩하도록 하자.

1. 재귀의 호출은 같은 문제 내에서 더 범위가 작은 값에 대해 이루어져야 한다.
2. 답을 얻었을 때는 반드시 base case를 걸어 재귀 함수를 끝낼 수 있어야 한다.

반복문(for)과 재귀는 반복을 한다는 점에서 비슷한것 같은데 무슨 차이가 있는거지?

반복문을 사용할 때 작성자(?)는 자신이 반복할 횟수를 알고 지정해서 사용한다. 반면 재귀 함수는 답이 나올 조건에 따라 반복 횟수가 달라지기 때문에 작성자도 반복 횟수를 알 수 없다.

 

반복문과 재귀는 반복을 한다는 점에서 같은 역할을 한다. 그럼 굳이 재귀를 써야 하는 이유가 있을까?

1. 알고리즘 자체가 재귀와 같이 자신을 반복해서 호출 할 경우
2. 변수 사용을 줄일 수 있다.
3. 가독성이 향상된다. (코드 길이를 줄일 수 있다.)

재귀의 위험성

재귀를 사용하면 함수를 반복해서 호출하게 된다. 이때의 입력값(매개변수), 결과값(리턴값), 다시 돌아갈 위치 등이 스택에 저장된다. 이렇게 매번 함수를 호출할 때마다 스택에 값을 저장한다. 함수를 단순 여러번에 걸쳐 호출하지 않고 무리하게 호출을 하게 되면 스택이 다 차버리는 '스택 오버플로우' 현상을 겪을 수 있다.

 

꼬리 재귀

위에 생긴 스택 오버플로우를 사전에 방지할 수 있는 재귀가 있다. 바로 '꼬리 재귀'. 
꼬리재귀란 재귀 호출이 끝나면 결과만 바로 반환되도록 하는 방법이다. 

 

꼬리 재귀에 대해 정말 잘 설명해놓은 블로그가 있어 같이 업로드하겠다.

https://joooing.tistory.com/entry/%EC%9E%AC%EA%B7%80-%E2%86%92-%EA%BC%AC%EB%A6%AC-%EC%9E%AC%EA%B7%80-Tail-Recursion

꼬리 재귀 (Tail Recursion)

 

---

 

끝인사 및 느낀점

오늘 학교에서 C언어 inclass 수업을 처음 했다. 녹강 복습만 하고 간단한 문제들로 공부를 하지 않은 상태에서 참여를 했다. 교수님께서 주신 문제에 대해서 학생 한분 한분을 발표시키셨는데 나도 발표하라고 하실까봐 너무 불안했다. 근데 다행히도 교수님께서 주신 문제들이 기초적인 문제들이여서 쉽게 풀 수 있었다. 그래서 제법 재밌게(?) 문제들을 풀었다. 오늘 느꼈던 식은땀들을 다시 느끼지 않기 위해 알고리즘 문제들을 빨리 공부해야겠다고 생각했다. 원래 오늘은 codeengn 9번 문제풀이를 올리려고 했지만 알고리즘 공부와 순서를 바꿔 내일 올릴 예정이다.

 

재귀를 공부하며 '아 정말 간단한 알고리즘인데 왜 이렇게 어렵게 느껴질까' 이 생각 밖에 안들었다. 문제는 이제 풀어야하는데 막막하다. 일단 해보고 문제 풀이 느낀점에 후기를 써야겠다. 그동안 백준에서 단계별 문제 중 초반 단계 문제 위주로만 풀었어서 재귀 알고리즘이 제대로된 첫 알고리즘 문제이다... 

 

 

대표 이미지 출처 : <a href="https://pixabay.com/ko/?utm_source=link-attribution&amp;utm_medium=referral&amp;utm_campaign=image&amp;utm_content=1653351">Pixabay</a>로부터 입수된 <a href="https://pixabay.com/ko/users/200degrees-2051452/?utm_source=link-attribution&amp;utm_medium=referral&amp;utm_campaign=image&amp;utm_content=1653351">200 Degrees</a>님의 이미지 입니다.