[Python] 19. 재귀함수

일반적인 함수 호출

• '함수 a'가 호출되어 실행되던 코드 중간에 '함수b'를 호출하면서 코드 진행이  '함수b'의 코드로 옮겨갑니다.
• '함수 b'가 호출되어 실행되던 코드 중간에 '함수c'를 호출하면서 코드 진행이  '함수c'의 코드로 옮겨갑니다.
• '함수 c'의 모든 실행이 종료되어 return한 값을 반환하고, '함수 b'의 '함수 c'를 호출했던 코드 다음 줄로 옮겨갑니다.
• '함수 b'의 모든 실행이 종료되어 return한 값을 반환하고, '함수 a'의 '함수 b'를 호출했던 코드 다음 줄로 옮겨갑니다.
• '함수 a'의 모든 실행이 종료되면 최종 값을 return합니다. 

 

 

재귀함수

- 함수 내에서 자기 자신 함수를 다시 호출하여 작업을 수행하는 방식

- 함수 내에서 같은 이름의 함수를 다시 호출하여 작업을 수행하는 방식

- 재귀함수는 반드시 탈출 조건이 있어야  stack overflow를 방지할 수 있다.

def fun(n):
    if n == 1:
        return(print('finish1'))
    else:
        print(n)
        fun(n - 1)
        return (print('finish2'))

fun(3)

#출력
#3
#2
#finish1
#finish2
#finish2

• fun(3) 함수가 실행되고, 조건식의 n ==1이 아니기 때문에 print(3)을 출력하고 fun(2)함수를 호출한다.
• fun(2) 함수가 실행되고, 조건식의 n ==1이 아니기 때문에 print(2)을 출력하고 fun(1)함수를 호출한다.
• fun(1)이 실행되면 "n == 1" 조건이 만족되어 print('finish1')을 리턴하고, fun(2) 함수에서 함수 fun(1)함수를 호출 했던 다음 코드 print('finish2')를 리턴한다.
• fun(3) 함수에서 함수 fun(2)함수를 호출했던 다음 코드 print('finish2')를 리턴하고 함수를 마친다.

function = []
def fun(n):
    global function
    if n == 1:
        return function.append('finish1')
    else:
        function.append(n)
        fun(n - 1)
        return function.append('finish2')
fun(3)
print(function)

#[3, 2, 'finish1', 'finish2', 'finish2']

function = []
def fun(n):
    global function
    if n == 1:
        return function.append('finish')
    else:
        function.append(n)
        fun(n - 1)
        return function.append(fun(n - 1))
fun(3)
print(function)

#[3, 2, 'finish', 'finish', None, 2, 'finish', 'finish', None, None]

*** append를 리턴하는 경우 특정값이 없을 때 None를 리턴한다.