재귀함수

 

1. 재귀함수란

 

메소드 혹은 함수의 내부에서 자신의 메소드 혹은 함수를 다시 호출하여 작업을 수행하는 방식의 함수를 의미.

 

다른 말로는 재귀호출, 되부름이라고 부르기도 한다.

 

 

2. 재귀함수의 원리 

 

재귀 함수를 작성할 때는 함수 내에서 다시 자신을 호출한 후

그 함수가 끝날 때까지 함수 호출 이후의 명령문이 수행되지 않는다는 사실과 종료 조건이 꼭 포함되어야 한다.

  = = > 조건문을 활용하여 재귀함수 종료 조건을 삽입해야 함.

 

 

3. 재귀함수 사용 이유

코드의 간결화 및 변수 사용 최소화

 

4. 예시 문제

- 재귀함수를 활용한 완전탐색

 

data = [3, 5, 8] 에서 성분들의 합을 표현할 수 있는 경우의 가지수는?

data = [3,5,8]

def recur(index, value):
    if index == len(data):
        result.add(value)
    else:
        recur(index + 1, value + data[index])
        recur(index +1, value)
        
result = set()
recur(0,0)
print(result)

 

 

- 팩토리얼 

 

def fac(n):
    if n ==1 :
        return 1
    else:
        return n * fac(n-1)
fac(5)

 

 

- 피보나치 수열

 

 

def fibo(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fibo(n-1) + fibo(n-2)
fibo(7)

 

 

5. 재귀함수 깊이

 

파이썬의 최대 깊이 기본값은 1000까지이다. 호출은 기본값으로 1000 번까지 가능하나, 이를 조정할 수 있다.