파이썬 - 재귀함수(recursion)

목차

-재귀함수?

-간단한 재귀함수 동작

-피보나치 재귀함수 동작

-정리

재귀함수

재귀함수는 함수 안에 함수를 호출하는 함수를 말합니다.

예를 들면. 아래와 같은 코드가 재귀함수입니다.

def go_to_zero(n):
    if n == 0: 
    	return 0
    print(n)
    return go_to_zero(n-1)

재귀함수는 자기 자신을 호출하기 때문에 실수하면.

무한히 자기 자신을 호출하게 됩니다.

그래서 탈출 조건이 필수입니다.

위의 코드의 경우 함수의 파라매터가 호출될 때마다 1식 감소하고.

만약 0이 되면 탈출하는 조건을 포함하고 있습니다.

그러면 이 함수가 잘 동작하는지 확인해 봅시다.

인풋을 10을 넣으면 -1씩 감소하면서 함수를 호출하다.

0이 되면 빠져나오는 것을 확인할 수 있습니다.

 

간단한 재귀함수 동작

재귀함수의 형태까지 알아봤습니다.

재귀함수는 자기 자신을 호출하는 형태이고.

탈출 조건이 없으면 무한이 호출되기 때문에 탈출 조건이 있어야 합니다.

 

재귀함수의 대략적인 정의를 알았다면.

명확한 재귀함수의 동작에 대해서 알아야 합니다.

재귀함수는 다양한 알고리즘에서 응용됩니다.

그런데 재귀함수 동작에 대해 명확하게 하지 않는다면.

나중에 알고리즘을 대충 이해하고 넘어가 거게 되어.

지식 부채가 생깁니다.

그러니 확실하게 하고 넘어가야 합니다.

 

그러면 이전에 작성했던 go_to_zero함수에 대해서 분석해 봅시다.

go_to_zero함수는 파라매터 n을 받고 n을 프린트하고 n-1을 파라매터로 가지는 함수를

n이 0이 될 때 까지 호출합니다.

그래서 프린트해서 출력되는 값은 n부터 시작해 0까지 출력이 되었습니다.

 

만약 go_to_zero를 아래와 같이 변경하면 어떻게 될까요?

상상해 봅시다.

def go_to_zero(n):
    if n == 0: 
    	return 0
    a = go_to_zero(n-1)
    print('return',a)
    return a + 1

이 함수를 실행하면.

이전과는 다르게 0부터 10까지 출력이 됩니다.

오류인가 ㅋ???

그러면 아래에 코드에 대해서 다시 생각해 봅시다.

go_to_zero시작 시 print(n)이 추가되었습니다.

def go_to_zero(n):
    print("start",n)
    if n == 0: 
    	return 0
    a = go_to_zero(n-1)
    print('return',a)
    return a + 1

go_to_zero(10)을 출력해 봅시다.

go_to_zero의 첫째줄에 해당하는 print("start", n)은 10부터 0까지 출력되고.

그다음으로 print('return', a)는 0부터 10까지 출력되는 것을 볼 수 있습니다.

 

처음 보면 뇌 정지가 올 수도 있습니다.

하지만 배우고 나면 아무것도 아닙니다. 

재귀함수의 동작 과정을 명확하게 이해하기 위해 그림을 그려봅시다.

5번부터 시작하여 화살표를 따라

아래로 이동하며 함수를 호출한다.

 

0이 되어 함수의 탈출 조건에 도달하면.

0번 함수가 종료되면서 0을 리턴한다.

 

1번 함수가 0에서 리턴한 결괏값 0을 리턴 받고.

이에 더하기 1을 하여 값을 리턴한다.

 

2번은 1번 함수가 리턴한 결과 1을 전달받고.

여기에 더하기 1을 하여 3번으로 전달한다.

...

...

...

5번은 4번으로부터 값을 받고.

더하기 1을 하여 값을 리턴한다.

 

정리해 보면.

실행은 역순으로 들어가고.

함수가 종료되면 그 값을 이전의 노드로 값을 전달합니다.

 

그러면 프린트했던 내용을 정리해 봅시다.

print('start', n)가 나타내는 것은 함수의 실행 부분이며.

그림에서 화살표 아래 방향입니다.

print('return', a)는 함수의 종료 부분이며.

그림에서 화살표 위 방향을 나타냅니다.

 

재귀함수를 보면.

자동적으로 위의 그림이 생각이 날 정도로 연습이 되어야 합니다.

이해했다고 끝내지 말고 다시 구현해 봅시다.

 

피보나치 재귀함수 동작

 

이전 내용을 확실히 익혔다면.

좀 더 어려운 피보나치수열을 재귀함수로 구현해 보고이에 대해 분석해 봅시다.

피보나치 수열 아래와 같은 관계를 가지고 있습니다.

fib(i) = fib(i-1) + fib(i-2) , i = 2, 3, 4 - - - - , fib(0) = 1, fib(1) = 1

이 관계를 이용하여 fib(7)까지 구해보면.

fib[0]	fib[1]	fib[2]	fib[3]	fib[4]	fib[5]	fib[6]	fib[7]
0	1	1	2	3	5	8	13

위처럼 나오는 것을 확인할 수 있습니다.

 

그러면 파라매터 n을 받았을 때 fib(n)의 값을 리턴하는 재귀함수를 구현해 봅시다.

def fib(n):
    if n == 0: return 0
    if n == 1: reutrn 1
    a = fib(n-1) + fib(n-2)
    return a

잘 구현했는지 확인해 보기 위해 7과 6을 넣어 확인합시다.

잘되는군요.

 

그럼 최종 목표인 피보나치 동작 과정 분석에 들어가지 전에.

어떻게 동작을 할지 그림을 그려 확인해봅시다.

자신이 맞다고 생각한 내용이 틀렸을 때 기억에 훨씬 잘 남으니.

힘들지만 꼭 그려봅시다.

 

자 그럼 print() 함수를 추가하여 동작이 어떤지 확인해 봅시다.

간단히 보기 위해 fib(4)를 해보았습니다.

생각보다 복잡하죠?

아까 전에는 start가 먼저 있었고 return이 마지막에 있었는데.

fib의 경우 섞여서 출력되고 있습니다.

출력되는 값들이 어떤 패턴을 가지고 있는지 분석하기 위해 그림을 그려봅시다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

fib(4)부터 시작한다.

fib(4)은 fib(3)을 호출한다.

fib(3)은 fib(2)을 호출한다.

fib(2)은 fib(1)을 호출한다.

fib(1)은 결괏값 1을 fib(2)으로 전달하고 종료한다.

fib(2)은 fib(0)을 호출한다.

fib(0)은 결과값 0을 fib(2)으로 전달하고 종료한다.

fib(2)은 fib(1)과 fib(0)의 결과를 합하고 fib(3)으로 전달하고 종료한다.

fib(3)은 fib(1)을 호출한다.

fib(1)은 결과값 1을 fib(3)을 전달하고 종료한다.

fib(3)은 fib(2)와 fib(1)의 결과를 합하여 fib(4)로 전달하고 종료한다.

fib(4)는 fib(2)를 호출한다.

fib(2)는 fib(1)을 호출한다.

fib(1)은 결과를 fib(2)에 전달하고 종료한다.

fib(2)는 fib(0)를 호출한다.

fib(0)는 결과를 fib(2)로 전달하고 종료한다.

fib(2)는 fib(1)과 fib(0)에서 받은 결과를 합하여 fib(4)에 전달한다.

fib(4)는 fib(3)과 fib(2)에서 받은 결과를 합하여 리턴한다.

 

이처럼 tree의 왼쪽부터 깊은곳 까지 탐색하며 오른쪽으로 이동하며 탐색합니다.

만약 처음 상상한 내용과 다르다면.

한번더 해봅시다.

 

정리

재귀함수를 처음 공부하면.

동작과정을 익히는데 뇌에 부하가 있습니다.

스트레스를 받더라도 피보나치와 고투제로 함수를

구현해 보고.

프린트도 해보고.

그림도 그려가며.

익혀야 합니다.

재귀함수를 잘 정리하고 익히게 되면.

나중에 알고리즘을 학습할 때 지식 부채 없이 깔끔하게 갈 수 있습니다.

 

재귀함수 최적화

참고로 마지막 피보나치 그림에서 fib(2)가 두번 반복하는 것을 볼 수 있습니다.

이를 호출 될떄마다 계산하는 것이 아니라.

처음 계산할 때 저장하였다가 나중에 사용하면.보다 효율적인 코드를 작성할 수 있습니다.이에 대한 내용을 다이나믹-프로그래밍-1에 있습니다.궁금하시다면 클릭해 주세요. 클릭!