재귀함수

정의

재귀함수는 함수 안에 함수를 호출하는 함수 (자기 자신을 호출하는 형태)

함수 내에서 그 함수를 다시 사용하는 것

⚠ return : 함수를 실행했던 위치로 돌아가라, 함수를 여기서 끝내라는 의미

 

---

주의할점

재귀함수는 자기 자신을 호출하기 때문에, 잘못하면 무한히 호출할 수 있다. 따라서 탈출 조건이 필수이다. 

 

 

 

 

 

---

예제

간단한 예제

def recursion(n) :
    # n이 0이면 빠져나오기
    if n == 0 :
    	return 0
        
    # n 출력
    print(n)
    
    # 다시 recursion 함수에 n-1 입력
    return recursion(n-1)
----------------------------------------------------------------------------------    
recursion(10)
"""
10
9
8
7
6
5
4
3
2
1
0
"""

def recursion(n):
    if n == 0: 
    	return 0
    a = recursion(n-1)
    print('return',a)
    return a + 1
------------------------------------------------------------------------------
recursion(10)
"""
return 0
return 1
return 2
return 3
return 4
return 5
return 6
return 7
return 8
return 9
10
"""

💡 위의 코드 설명

✔ 예를 들어 recursion(10)을 받게 되면, a = recursion(9)가 되고, 또 recursion(9)를 받게 되면, a = recursion(8)이 되는 규칙이 반복된다.

✔ 이렇게 해서 recursion(1)을 받으면 a = recursion(0) = 0 (n = 0이면 0을 리턴하므로)이 된다.

✔ 그러면 이제 자연수 a가 나왔으므로 print('return', a) -> return 0 출력

✔ recursion(1)은 a+1 = 1을 리턴하고 이 함수는 끝난다.

-----------------------------------------------------------------------------------------------------------------------------------

점점 위로 올라가면서 출력하는 형태

recursion(2)를 받으면 a = recursion(1) = 1이므로 return 1을 출력하고, a+1 = 2를 return

recursion(3)을 받으면 a = recursion(2) = 2이므로 return 2를 출력하고, a+1 = 3을 return 

...

...

recursion(10)을 받으면 a = recursion(9) = 9이므로 return 9를 출력하고, a+1 = 10을 return

마지막으로 return한 10까지 출력 후, 끝 !

 

 

def recursion(n):
    print("start",n)
    if n == 0: 
    	return 0
    a = recursion(n-1)
    print('return',a)
    return a + 1
---------------------------------------------------------------------------------
recursion(10)
"""
start 10
start 9
start 8
start 7
start 6
start 5
start 4
start 3
start 2
start 1
start 0
return 0
return 1
return 2
return 3
return 4
return 5
return 6
return 7
return 8
return 9
10
"""

✔ a = recursion(n-1) 이 코드 때문에 recursion 함수가 1씩 작아지면서 반복적으로 호출되어, start를 모두 출력한다.

✔ 그 후에 recursion(0)이 0으로 return되면서 a값이 구해지고 다시 a+1로 리턴하는 값이 생겨 recursion(1), recursion(2), ... 까지 구할 수 있게 된다. 

 

 

---

팩토리얼 함수

n = int(input())
def recursion(n) : 
    if n <= 1 :
    	return 1
    return n*recursion(n-1)
    
print(recursion(n))

 

 

 

 

---

유클리드 호제법

• 두 값 A, B의 최대공약수를 구하기 위해 사용되는 방법

# 반복문
def recursion(a, b) :
    while a % b != 0 : 
        a, b = b, a % b


# 재귀함수
def recursion(a, b) :
    if a % b == b :
        return b
    return recursion(b, a % b)
    
    
# 파이썬 함수 사용
from math import gcd
gcd(a, b)

 

 

 

 

 

---

피보나치 수열

• n번째 값이 (n-2)번째 값 + (n-1)번째 값과 같음을 만족하는 수열
• 즉, 1, 1, 2, 3, 5, 8, 13, 21, ...

# 반복문 함수 (n번째 항의 값 출력)
def fib(n) :
    p = 0
    c = 1
    for i in range(n-1) :
        t = p
        p = c
        c = p + t
    return c
-----------------------------------------------------------------------
# 재귀함수 (n번째 항의 값 출력)
def recursion(n) :
    if n <= 2 :
        return 1
    return recursion(n-1) + recursion(n-2)
    
for i in range(1, 11) :
    print(recursion(i))