Python : 반복(Iteration)과 재귀(Recursion) Review

알고리즘 풀면서 가장 많이하는 두가지 인 것 같다. 반복문을 사용하느냐, 함수의 재귀 호출을 사용하는가를 선택하는 것은 중요하다. 개인적을 재귀 호출을 잘 사용하지 못하다 보니 반복문을 사용하는데, 이렇게 되면 코드가 쓸 때 없이 길어지며 재귀를 사용하지 않고는 문제를 해결할 수 없는 문제가 생긴다. 재귀는 어려운 개념이지만, 간단하고 깔끔하게 함수식을 통해 풀 수 있다는 장점이있다. 가장 큰 단점으로 느껴지는 것은 함수 재귀 호출 시 디버깅이 어렵다는 단점이 있는 것 같다. (아직 안익숙해서 그런 것일지도..) 

아무튼 중요하다보니 한번 이해하고 정리할 겸 짚어보려고 한다.

---

반복(Iteration)

: 수행하는 작업이 완료될 때 까지 계속 반복한다

• 루프 (for, while 구조)
• 반복문은 코드를 n 번 반복시킬수 있다

예를들어, 1 1 ~ 3 3 까지 출력하는 프로그램(중복 순열)을 작성한다고 가정하자. 당장은 이중 반복문을 통해 간단하게 구현이 가능하다. 

for i in range(1, 4):
    for j in range(1, 4):
        print(i, j)
'''
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
'''

 

출력값은 위와 같다. 이는 중복을 허용했기 때문에 1 1 , 2 2, 3 3과 같은 출력값도 확인 할 수 있다. 하지만 2개의 순열이아니라 4개라면?

for i in range(1,4):
    for j in range(1, 4):
        for k in range(1, 4):
            for l in range(1, 4):
                print(i, j, k, l)
'''
1 1 1 1
1 1 1 2
1 1 1 3
1 1 2 1
...
3 3 2 3
3 3 3 1
3 3 3 2
3 3 3 3
'''

 

위와 같이 가능하다. 2개일때 2중 반복문, 4개일 때 4중 반복문이었다면.. 변수가 9개라면? 20개라면? 그럴때마다 9중 반복문, 20중 반복문을 모두 쓸 수 없을 것이다.

• N 입력 후 111 112 ... 332 333 을 출력하는 문제는 for문으로 구현에 한계가 있다
• 재귀 호출(함수)를 사용해 손쉽게 구현할 수 있다

이럴 때 재귀 함수가 사용될 수 있다.

---

반드시 알아야 할 함수의 특징

항상 새로운 함수의 특징을 기억해보자

• 함수를 호출할 때, int() type의 객체를 전달하면 값만 복사한다
• 함수가 끝나면, Main으로 되돌아오는 것이 아니라, 해당 함수를 호출했던 곳으로 돌아온다

 

호출과 return 하는 위치가 중요하다

 

1번 print(x) = 8

2번 print(x) = 6

3번 print(x) = 5

4번 print(x) = 3

 

출력 값이 헷갈리겠지만, 위에 말했던 함수의 특징중에 1번을 생각해보면서 차근차근 풀어나가면 된다. 함수 호출을 넘어가면 그 안에서만 가지고 활용되고, 돌아올 때는 다시 자신으로 탈바꿈 된다고 생각하면 쉽다.

 

그럼 파이썬 코드로 살펴보자.

def Hyo(x):
    x += 10
    print('answer1:', x)

def Jin(x):
    print('answer2:', x)
    x += 3
    Hyo(x + 2)
    print('answer3:', x)

x = 3
Jin(x + 1)
print('answer4:', x)

'''
answer2: 4
answer1: 19
answer3: 7
answer4: 3
'''

 

눈으로 확인하기 쉽게 answer의 위에서부터 아래로 코드 print() 넘버링를 넣었다. 그랬을 때 어디부터 호출 및 출력되는지 확인 할 수 있고, 순서와 해당하는 함수 내에서 출력되는 값을 확인할 수 있다.

 

---

재귀(Recursion)

: 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용하는 방법. 이는 재귀 관련하여 피보나치 수열을 다루면서 설명을 한 적이 있다. 작은 문제로 만들어서 작은 것들을 해결하고 점점 큰 문제를 해결해 나가는 방식.

• 재귀 호출은 n 중 반복문을 만들어낼 수 있다.
• 반복문을 통해 수행하기 어려운 작업을 반복할 수 있다.

: 파이썬 내에서 재귀의 최대 횟수(깊이 제한)는 1000회로, 넘어가게 된다면  RecursionError 를 맛볼 수 있다. 따라서 상황에 따라 잘 사용해줘야 하고, 무한 호출을 하지 않도록 '기저조건'(base case)은 반드시 필요한 부분이다.

 

반복문을 사용하지 않고 재귀를 이용하여 0 1 2 3 4 5 5 4 3 2 1 0 을 출력해보자.

어떻게 함수를 작성할지 먼저 살펴봐야할 것은 제일 처음 출력되는 값, 재귀될 때마다의 규칙, 기저조건 3가지이다. 함수명은 plus로 간단하게 만들고, 0부터 출력되고 1씩 증가하며 5를 두번출력하고 다시 작아진다. 이후 0을 출력하고 종료한다. 따라서 기저조건은 n = 6일때는 return이다.

def plus(n):
    if n == 6:
        return
    print(n, end = ' ')
    plus(n+1)
    print(n, end = ' ')

plus(0)
'''
0 1 2 3 4 5 5 4 3 2 1 0 
'''

 

그림으로 어떻게 진행되는지 확인해보자

결국 실행되는 print()문은 2개밖에 없다

1번 print(n) = 1

2번 print(n) = 0 임을 이제 이해할 수 있을 것이다!

 

이번에는 좀 더 확장된 재귀를 확인해보자

파란색 화살표 : 함수 호출, 초록색 화살표 : return

과정은 복잡해보이지만, 결국 3개만 출력된다.

6번 print(n) = 1

12번 print(n) = 1

13번 print(n) = 0

def plus(n):
    if n == 2:
        return
    plus(n+1)
    plus(n+1)
    print(n)

plus(0)

'''
1
1
0
'''

 

코드로도 해당 재귀를 확인할 수 있다.

 

근데 재귀 호출이 2개인 형태를 오른쪽으로 90도만 돌려보면?

 

이제는 트리까지 다루었기 때문에 이전과 다른 시각을 확인할 수 있다. 

branch: 2 / level : 2

 

그렇다면 동일한 함수 내부에 재귀 호출 코드가 세개라면??

def plus(n):
    if n == 2:
        return
    plus(n+1)
    plus(n+1)
    plus(n+1)
    print(n)

plus(0)

branch : 3 / level : 2

 

깊이를 level, 나뭇가지 branch라고 할 때 branch는 3, level은 2라고 할 수 있다. 하지만 항상 함수 호출을 횟수세어서 복사 할 순 없으니 반복문을 사용할 수 있다.

def plus(n):
    if n == 3:
        return
    plus(n+1)
    plus(n+1)
    plus(n+1)
    plus(n+1)
    print(n)

plus(0)

def plus(n):
    if n == 3:
        return
    for i in range(4):
        plus(n+1)
    print(n)

plus(0)

 

반복문을 사용하여 나타낸 재귀 호출형식은 아래와 같다. 코드가 훨씬 간결하고 알아보기 쉽게 되었다. 여기서 기저조건인 n == 3은 level임을 알 수 있고, branch는 반복문 회수 4라는 것을 알 수 있다.

이를 통해 본문처음에 나온 순열을 재귀를 통해 만들 수 있는 능력을 얻게 되었다.