[Python] 재귀 함수란 ? (Recursive Function)

▶  재귀 함수

def hello():
    print("Hello world!")
    hello()               # 자기 자신 호출
    
hello()

: 함수 안에 함수가 또 있어서 자기 자신을 반복적으로 호출할 수 있는 형태의 함수.

: 자기 자신을 반복적으로 호출하는 만큼 종료 조건이 있어야 된다.

: 문제를 해결하기 위해 자신을 호출하여 문제를 더 작은 하위 문제로 나누는 함수이다.

 

 

 

▷  팩토리얼 구하기로 재귀 함수 이해하기

     - 팩토리얼 : 그 수보다 작거나 같은 모든 양의 정수의 곱

        ex)  5! = 5 x 4 x 3 x 2 x 1 = 120

# 팩토리얼 - 재귀 함수
def factorial(n):
    if n == 1:
    	return 1
    else:
    	return n * (n-1)
        
print(factorial(5))

팩토리얼 계산에서 베이스 케이스와 재귀 케이스 정하기.

 

 

 

▷  재귀 함수 구현하기

재귀 함수 사용법

 

→  먼저, 하위 문제를 찾고 베이스 케이스와 재귀 케이스를 정한다. 이를 토대로 재귀 함수를 작성한다.

→  피보나치 수열, 리스트 뒤집기, 자릿수 합 등 대표적인 알고리즘 문제들을 재귀 함수와 함께 해결가능하다.

 

---

 

 

▷  피보나치 수열 구하기

 

 

 

ex) 피보나치 수 : 1, 1, 2, 3, 5 ,8, 13, 21, ...

# 피보나치 수열 함수
def fib(n):
    if n==1 or n==2:
        return 1
    else:
        return fib(n-1) + fib(n-2)
    
for i in range(1, 100):
    print(fib(i), end=",")

 

실행 결과

 

실행해 보면 실행 시간이 엄청나게 오래 걸리는 것을 확인할 수 있었다.

그 이유는 n-1과 n-2를 구하기 위해 이전 계산을 계속적으로 반복을 해서 시간이 엄청나게 오래 걸린 것이다.

시간을 단축시키기 위해서는 memoization을 사용해서 결과를 저장해 주면서 계산을 하면 시간을 크게 단축시킬 수 있다 !

# 메모이제이션
memory = { 
    1 : 1,
    2 : 1
}
count = 0
def fibo_memoization(n):
    global count
    count += 1
    if n in memory:
        number = memory[n]
    else:
       number = fibo_memoization(n-1) + fibo_memoization(n-2)
       memory[n] = number
    return number

fibo_memoization(100)

 

 

 

 

※ 재귀 함수의 스택 오버플로우 에러 !

재귀 함수를 사용하면 반복적인 작업으로 스택 오버플로우 에러를 신경 써야 되는데 파이썬은 쌓여있는 함수 호출을 1000개로 제한해두고 있다. 그래서 factorial(2000)을 하게 되면 Recursion Error가 발생하기도 한다.

 

※ 재귀 함수 어려운데 왜 이해해야 하는가 ?

: 재귀 함수를 사용하면 원래 수십 줄이었어야 할 코드도 단 몇 줄로 깔끔하게 줄일 수 있다.

: 문제를 재귀적인 접근 방식으로 해결책을 찾을 수 있다 !  새로운 사고방식과 문제 해결법이 생기기 때문에 유리하다.

 

 

 

처음에는 반복문으로 할 수 있는 코드를 왜 재귀 함수를 사용해서 써야 하는가 의문이었는데, 재귀 함수의 개념을 잘 이해해 보니 재귀적인 접근 방식으로 해결책을 찾을 수 있음을 배웠다.  재귀 함수의 이해가 문제 해결방식에서 유용하게 사용될 것 같다 !