[노베이스, 취준생을 위한 파이썬] - 6강 재귀함수

본 강의 시리즈는 파이썬 입문 및 복습을 위한 강좌입니다. 모든 포스팅은 아래의 링크에서 확인가능합니다!

---

1강 - 변수와 자료형

2강 - 제어구조 ( if else 문)

3강 - 제어구조 ( for 문)

4강 - 제어구조 ( while 문)

5강 - 함수

6강 - 재귀함수

7강 - 람다 (lambda)

8강 - 문자열, 리스트

9강 - 튜플, 딕셔너리, 세트

10강 - 유용한 라이브러리

11강 - 클래스

12강 - 예외처리

---

사실 저는 재귀함수 처음배울때 너무 헷갈렸던 기억이있어요 ㅠ 그래서 조금 자세히 알아봅시다. 일단 재귀함수는 말그대로 함수안에 본인의 함수를 또 넣어주는것을 말해요. 아래처럼요.

def test():
	test()

왜 이렇게 해야되는지 모르겠죠? 사실 재귀함수를 많이 사용하지는 않지만 나중에 알고리즘 할때 필요하니까 배워놓긴 해야되긴한데 조금 쫌 그래요. 하여튼 위와 같이 함수를 만들면 결국 저 두번째 줄에 있는 test안에도 또 test함수가 있고 또있고,, 또있고,, 하니까 안끝나겠죠? 그래서 재귀함수에는 무조건 종료조건이 필요합니다. 

 

자.. 여기서 제가 하고싶었던 것은 n을 입력으로 넣으면 1+2+...+n 값을 리턴해주는 함수를 보여드리고자 했습니다. add(3)을 한번 예시로 들어보죠.

 

add(3) = 3+ add(2) = 3+ (2+add(1)) = 3 + (2 + 1) = 6 

 

결국 add 함수는 끝없이 안에 있는 add 함수를 불러오게 되는데, 이때 종료 조건으로 n이 1일때 1을 return해줌으로써 결과적으로 add(3)의 값을 계산할 수 있는 것이죠. 다른 예제도 살펴봅시다. 

 

https://www.acmicpc.net/problem/2448

2448번: 별 찍기 - 11

 

문제를 읽어보시고 예제를 한번 보시면 반복되는 모양들이 있구나! 재귀로 풀어보자는 생각이 드실겁니다. 가장 먼저 해야할 일은 제일 작은 단위를 찾고 이를 이용해서 그 다음단계를 만드는 것인데, 저는 가장 작은 단계를 다음과 같은 리스트로 표현했습니다. 

a=["  *  ", " * * ", "*****"]

요 세줄의 조그만 세모를 가지고 다음 6줄의 세모를 만들기 위해서는, a를 쌓아야 되는데, 첫줄에는 양쪽에 (n//2)만큼의 공백으로 padding을 해주고, 두번째 줄에는 가운데에 공백만 추가해주면 됩니다. 즉, star(12)를 생각해보면, 

 

star(12) -> (star(6))을 두줄로 쌓을거임 -> (star(3)을 두줄로 쌓을거임)을 두줄로 쌓을거임

 

요런식으로 재귀적으로 작동할 수 있죠. 위의 예제와 아래의 연습문제 리스트들을 차근차근 풀어보시면서 감을 익히시는 기회가 되었으면 좋겠습니다. 재귀는 무엇보다 꼼꼼히 생각해보는것이 좋은 것 같습니다!

 

연습문제 

https://www.acmicpc.net/problem/6603

6603번: 로또

https://www.acmicpc.net/problem/2447

2447번: 별 찍기 - 10

https://www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

https://www.acmicpc.net/problem/3080

3080번: 아름다운 이름