< IT > 코딩을 지탱하는 기술_5장_함수, 재귀호출

함수는 왜 생겨났을까?
함수 발명으로 가능해진 '재귀 호출' 이 어떤 동작을 하는지, 언제 사용할 필요가 있는지 알아본다.

📌 함수

함수	코드의 일부를 한 덩어리로 잘라내어 그것에 이름을 붙이는 기능.

함수 없이 짤 수 있는 프로그램이 있을까? 있기는 하지만, 함수를 사용하는게 보다 편하다.

---

이해시켜줘

코드가 함수로 나눠져 있는 것은 큰 조직이 부서로 나눠져 있는 것과 비슷하다.

작은 프로그램에서 함수를 쓰는 이점을 잘 모르는 것은 몇 명의 친한 사람끼리 부서를 만들 필요성을 못 느끼는 것과 같다.

문제는 사람 수가 늘었을 때다. 이렇게 되면 몇 명을 하나의 그룹으로 묶어서 이름을 붙인다. ( 인사팀 등 )

 

프로그래밍도 동일하다.

소스 코드의 행수가 많아지면 전체를 파악하기 어렵게 된다. 그래서 몇 개의 행을 하나의 그룹으로 묶어서 이름을 붙인다.

이것이 함수다.

---

함수를 만드는 것은 작은 부품을 조립해서 큰 부품을 만드는 것과 비슷하다.

예)

무선 조정 자동차에는 알칼리전지나 모터가 들어있다.

알칼리전지나 모터를 특정 위치에 설치해야 무선 조정 자동차가 완성된다.

그런데?

알칼리전지 안에는 이산화 망간, 아연 등이 들어있다. 이를 위해선 전지 안에서는 어떤 화확반응이 일어나서 전력이 발생하는지를 이해해야 한다. ( 현실에서는 구매하면 되지만 )

 

함수도 동일하다. 여러 행의 코드가 함수로 정리되어 제공되기 때문에 그 함수를 호출해서 사용하면 된다.

또한 전지라는 이름으로 인해, 전지를 사용한 시스템을 간단히 이해할 수 있다. 그래서 무선 조정 자동차가 느려진다면 

'전지가 약해졌다.' 고 생각할 수 있다.

이것은 함수가 이해를 도와주는 것과 비슷하다.

---

재사용의 특징

프로그램으로 데이터를 어떤 함수로 처리하고 싶을 때, 데이터가 100개 있으면 그 함수를 100회 부르면 된다.

그러나 함수는 1개만 만들면 된다. 몇 번이고 사용할 수 있는 처리를 함수로 정리해서 호출하면 소스 코드를 간결하게 유지 가능하다.

---

🤍 돌아가는 명령

'원래 위치로 돌아가'는 명령이 가능하면 코드를 재사용할 수 있게 된다.

'몇 번이고 반복해서 사용하는 명령을 한 곳에 모아두어 재사용하기' 필요성은 오래전부터 있었다.

 

1949년 EDSAC에도 이런 기술이 사용되고 있었다.

당시 프로그램 명령, 데이터는 컴퓨터 메모리에 동일한 형태로 기록되어 있었다.

함수를 호출한 후 원래 위치로 돌아오는 것을 점프 명령의 목적지를 변경해서 구현했었다.

1: 110의 점프 명령의 점프 목적지를 3으로 바꾼다.
2. 함수를 호출한다. ( 100으로 점프 )
3: 다음 명령
...
51: 110의 점프 명령의 점프 목적지를 53으로 바꾼다.
52: 함수 호출 ( 100으로 점프 )
53: 다음 명령
...
100: 함수 처리
...
110: 돌아간다. ( 0으로 점프 )

이런 식으로 함수가 탄생했다.

---

전용 메모리의 필요성

함수 호출 전으로 돌아가도록 하는 명령의 점프 목적지를 변경하기 위해, 함수를 호출하는 사람이 '점프 목적지가 어딘지', '돌아가는 명령이 있는 곳은 어디인지'를 파악해야만 했다.

이렇기에 돌아갈 목적지를 기록해두는 전용 메모리를 만들어 돌아갈 목적지 메모리에 적어둔 번지로 점프하는 명령을 준비하였다.

1: 돌아갈 목적지 메모리에 3을 넣는다.
2: 함수 호출 ( 100으로 점프 )
3: 다음 명령
...
100: 함수 처리
...
110: 돌아갈 목적지 메모리에 써있는 지번으로 돌아간다.

하지만 문제가 있다.

함수 X를 호출하고 있는 도중 다른 함수 Y를 호출하면, 돌아갈 목적지 메모리에 덮어 씌워져서 함수 X가 돌아갈 목적지를 잊어버리게 된다.

함수 처리를 할 때 왜 이름을 붙여야 하나?

함수를 사용한 처리에 이름을 붙이는 행위는 '처리가 시작되는 메모리상의 위치'를 수치로 표현하는 대신, 알기 쉬운 문자열로 표현하는 행위다. 

이것은 변수도 마찬가지이다.

변수도 '값이 기록된 메모리 위치'를 수치가 아닌 문자열로 표현하기 위해 만들어졌다.

---

🤍 전용 메모리를 위한 스택

스택 ( Stack )

복수의 값을 저장해두는 데이터 구조. 마지막에 넣은 것을 가장 먼저 꺼내는 경우에 적합하다.

스택은 구체적으로 어떻게 구현되어 있는 걸까?

우선 '마지막에 넣은 데이터가 어딘지' 를 기록해두는 메모리 위치를 정한다. ( 예시에서는 42번지 )

새로운 데이터를 기록할 때는 42의 값을 1 증가시킨 후, 거기에 적혀있는 번지에 데이터를 기록한다.

- 최초 상태 -
42: 스택의 선두는 어디인가 ( 현재값: 100 )
100:

- 함수 X로부터 돌아갈 목적지를 스택에 기록한 후의 상태 -
42: 스택의 선두는 어디인가 ( 현재값: 101 )
100:
101: 함수 X가 돌아갈 목적지

- 새로운 함수 Y가 돌아갈 목적지 기록 -
42: 스택 선두는 어디인가 ( 현재값: 102 )
100:
101:
102: 함수 Y가 돌아갈 목적지

스택에서 데이터 꺼내기

데이터를 꺼낼 때는 42번지에 쓰여있는 번지의 데이터를 읽어서, 42번지의 값을 1 감소시킨다.

42; 스택 선두가 어디인가 ( 현재값: 101 )
100:
101: 함수 X가 돌아갈 목적지
102: 함수 Y가 돌아갈 목적지

---

🤍 재귀 호출

재귀 호출

함수 X안에서 자신을 호출하는 것이다.

 

재귀 호출은 꼭 필요한 걸까?

그렇지 않다.

하지만, 어떤 처리를 재귀 호출을 사용해 만들면 편하게 구현할 수 있기 때문이다.

내포 ( nesting ) 형태의 처리

어떤 처리를 하고 있는 도중에 동일한 처리를 다른 대상에 대해 실행한다.

 

내포 구조를 다루는 방법

내포된 처리를 예로 해서, 내포된 리스트의 수치를 전부 합산하는 문제를 생각해보자.

 

예) [1,2,[3,4],5]  리스트가 있다. 이 내포 리스트에 있는 숫자를 전부 합산하려면 어떻게 해야 할까?

 

Python 코드에서는 for 문으로 리스트에서 하나씩 꺼내, 그것이 정수이면 합산하는 처리를 한다.

def total(xs):
    result = 0
    for x in xs:
    	# 리스트 xs에서 요소를 하나씩 꺼내서 x라고 칭한다.
        if is_integer(x):
        	# x가 정수이면 더한다.
        	result += x
        else:
        	# x가 정수가 아니면 어떻게 할까?
    return result
    
#코드 출처
#http://www.yes24.com/Product/Goods/11101558

 

1과 2가 나오면 정수이기 때문에 result ( 결과 ) 에 더한다. 여기까지의 합은 3이다.

다음엔 정수가 아닌 [3,4] 가 나온다. 어떻게 하면 될까?

 

for로 구현할 수 없다.

리스트이기 때문에 for 문을 써서 안에 있는 값을 별도로 합산하면 안되나? 생각하지만 3중 내포의 리스트가 입력되면 어떻게 될까?

def total(xs):
    result = 0
    for x in xs:
    	if is_integer(x):
        	result += x
        else:
        	# x가 리스트이기 때문에 for문으로 돌려볼까?
            for y in x:
            	if is_integer(y):
                	result += y
                else
                	# 추가로 리스트가 나오면 어떻게 해야 할까?
     return result
     
#코드 출처
#http://www.yes24.com/Product/Goods/11101558

여기에 추가로 for문을 써도 3중 내포까지만 처리가 된다. 

만약 데이터가 4중, 5중 내포 관게가 된다면 처리할 수 없댜ㅏ.

 

HTML에서는 태그가 수십 개의 내포 관계로 되어 있다.

이런 데이터 구조를 다루기 위해선 다중 내포 관계에서도 사용할 수 있는 코드여야 된다.

---

이로 인해 재귀 호출을 사용한다.

재귀 호출로 total 함수를 완성하자.

def total(xs):
    result = 0
    for x in xs:
    	if is_integer(x):
            result += x
        else:
            # x는 내포 리스트이기 때문에 total로 안에 든 값을 합산한다.
            result += total(x) # total의 result를 호출처 result의 반환값으로 전달.
     return result
     
#코드 출처
#http://www.yes24.com/Product/Goods/11101558

함수 total은 몇 중으로 된 내포 리스트가 전달되어도 안에 있는 모든 수를 합산할 수 있도록 되었다.

적은 계산법

---

요약해줘

전체적인 구조를 파악하고 싶을 때, 비슷한 처리를 몇 번이고 반복해서 쓰고 싶어질 때.

함수는 이 문제를 해결하기 위해 탄생했다.

한 그룹인 코드를 빼내어 의미 있는 이름을 붙이고, 그 코드가 무엇을 하고 있는지 파악하기 쉬워진다.

그리고 그 함수를 다른 장소에서 호출하여 사용함으로 재사용도 가능해진다.

 

재귀 호출은 내포된 처리 구조로 된 데이터를 다루기에 적합한 기법이다.

---

- < 도서 > 코딩을 지탱하는 기술

http://www.yes24.com/

코딩을 지탱하는 기술 - YES24