220713_부트캠프시작_python_2주_3일차 (복기)

재귀함수

 

 

정의 단계에서 자신을 재참조하는 함수를 뜻한다. 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 한다

자기 자신을 호출하는 함수를 `재귀함수` 혹은 `재귀호출` 이라고 합니다. 

 

 

 

예시

어금니가 영어로 뭐야?

몰라

- 어금니가 영어로 뭐야?

- 몰라

-- 어금니가 영어로 뭐야?

-- 몰라

 

예시2

사과는 무슨색이지?

빨간색

빨가면 사과

- 사과는 무슨색이지?

- 빨간색

- 빨가면 사과

 

뭐 대충 특정한 구역을 계속 반복한다고 보면된다 like 이중for문

 

사용법을 들어가기 전

# 3중 LIST example에 있는 값들을 출력값으로 재귀함수를 사용해서 나오게 만들어라

example = [[1,2,3], [4,[5,6]],7,[8,[9]]]

출력 : [1,2,3,4,5,6,7,8,9]

 

1) for와 if를 이용한 극단적인 노가다로 우선 풀어보았다.

li = []
example = [[1,2,3], [4,[5,6]],7,[8,[9]]]
for i in range(0, len(example)) :                       # example의 len 값은 3
    if type(example[i]) == int :                        # example list 내부의 값이 정수이면
        li.append(example[i])                           # li 리스트 안에 추가하고
    elif type(example[i]) == list :                     # example list 내부의 값이 list 이면
        for j in range(0, len(example[i])) :            # example list 내부의 내부 값이 정수인지 판단
            if type(example[i][j]) == int :             # 이런 구조로 3중 list까지 해부하여 정수값만 li 안에 차곡차곡 쌓고
                li.append(example[i][j])
            elif type(example[i][j]) == list :
                for k in range(0, len(example[i][j])) :
                    if type(example[i][j][k]) == int :
                        li.append(example[i][j][k])
li = sorted(li)                                         #li를 정렬하여 출력
li

 

example 이란 3중 리스트안에는 정수값도 있고 리스트도 있고

example 안 리스트 안에는 정수값도 있고 리스트도 있다.

정수값은 len으로 글자수 세는 것이 안되고 append를 이용해서 리스트 값은 바로 li안에 집어넣는 것이 안되니

for와 if를 경우의 수 만큼 사용하여 결과를 도출하였다.

자고로 좋은 코드는 짧은 코드 (연산속도가 빠른 코드) 라고 했던가

 

2) 재귀함수를 이용해 압축해보았다.

def jghs(list_3):                          # jghs 라는 함수는 1개의 값을 입력 받는다.
    a = []                                 # a라는 비어있는 리스트를 만들어 놓고
    for b in list_3 :                      # 입력받은 값안에 b가 있다면 반복 실행
        if type(b) == int :                # b의 타입이 정수라면
            a.append(b)                    # a 리스트에 b를 추가한다.
        else:                              # b의 타입이 정수가 아니라면 (b의 타입이 list라면)
            a.extend(jghs(b))              # a 리스트에 jghs 함수에 b를 넣고 함수를 다시 돌려 추가한다.
    return sorted(a)                       

example = [[1,2,3], [4,[5,6]],7,[8,[9]]]

print(jghs(example))

 

주목해야 할 점은 크게 2가지다.

정수가 아니라면 아닌 값을 넣고 함수를 다시 돌린다.

ex )
example = [[1,2,3], [4,[5,6]],7,[8,[9]]] 의 경우
example[0] = [1,2,3]        # list 타입
재귀함수를 다시 쓴다      # a.extend(jghs(b))
example[0][0] = 1             # int 타입
a.append(example[0][0])  # 리스트 a에 1을 추가했다.
# 똑같은 방식으로 
example[0][1]
example[0][2] 까지 리스트에 추가 후 다시
example[1] = [4,[5,6]] 에 대한 판단을 한다.

구조상 이런 구조를 갖게 된다.

 

빠른 이해를 위해 for와 if로 코드가 아닌 풀이로 다시 써보자

 

# jghs(값1개) 값 1개 입력하는 함수 만들게
# 함수 안에 a라는 빈 리스트 만들게 지역변수라 쓰고 버릴거야 걱정마
# list_3 안에 있는걸 b에다 1개씩 넣고 반복해줘
# 첫번째 b 는 list_3의 첫번째겠지? b가 혹시 정수라면..
# a리스트에 추가해주지 않을래?
# 아니면 함수 다시 쓸게 대신 처음에 입력한 값 대신 b를 쓸거야
# b는 이미 list_3 안에있는 친구자나? 순서대로라고 하면 example[0] = [1,2,3] 이니까
# 정수가 아니라 list네 그럼 example[0] = [1,2,3] 가지고 함수 다시 돌려보자.
# [1,2,3] 의 첫번째 값을 b에 넣으면 1 어? 정수네?
# a리스트에 1추가할거야 그리고 a 리턴해서 밖으로 빼야지!
# 밖으로 뺀 값은 첫번째 jghs 함수 안에 첫번째 a리스트에 차곡차곡 리턴해야지!

막상 말로 풀자니 조금 풀이에 어려운 부분이 있지만

결국 int 조건에 맞지않는건 함수를 한번 더 돌려 list를 int형으로 바꾸어 a에 차곡차곡 쌓는다고 생각하면된다.

a는 함수가 가동 될 때마다 초기화 될테지만 그 함수에서만 쓰는 지역변수 값으로 결과값 리턴 후에는 사라지고 첫 함수에 있는 a에 append와 extend를 이용하여 차곡차곡 쌓이게된다.