재귀함수

A함수 내부에서 A함수 자신을 다시 호출하여 작업을 수행한다. 재귀 호출 또는 되부름이라고도 한다.

반복문을 사용하는 코드는 항상 재귀 함수를 통해 구현이 가능하며 그 반대도 가능하다.

재귀 함수는 계속적으로 호출이 가능하여 종료 조건이 필요하다.

---

재귀함수 예시

1부터 n까지의 합 구하기

def solution(n):
    # 재귀함수 종료 조건 지정
    if n == 1:
        return 1
    
    # 재귀함수 호출
    return n + solution(n-1)

print(solution(5))

[Output]
15

1. 조건문을 사용하여 n이 1이되면 종료되고 1을 반환한다.

2. n이 1이 아닌경우 n + solution(n-1)을 해준다.
   <n + solution(n-1) 설명>
   solution(n)의 값은 5이므로 return 5 + solution(5-1)이 된다.
   solution(5-1)은 solution(4)를 재귀 호출하여 n값이 4가 된다.
   따라서

# n + solution(n-1)이 계산되는 모습
return 5 
return 5 + 4
return 5 + 4 + 3
return 5 + 4 + 3 + 2     # n-1의 값들이 누적된다.
return 5 + 4 + 3 + 2 + 1 # 종료조건에 맞아 1을 반환 받음
return 5 + 4 + 3 + 3     # 누적된 값의 반대로 계산을 하게된다.
return 5 + 4 + 6
return 5 + 10 
return 15

3. 재귀 호출로 값이 n에서 -1을 해주므로 값이 하나씩 누적이되고 재귀 호출이 종료조건에 맞아 종료가 되면 마지막 숫자부터 하나씩 계산을 하여 결과 값을 return한다.

---

1부터 n까지의 곱 구하기 (Factorial)

def solution(n):
    # 재귀함수 종료 조건 지정
    if n == 1:
        return 1
    
    # 재귀함수 호출
    return n * solution(n-1)

print(solution(5))

[Output]
120

1. Factorial(!)로 표기하기

# n * solution(n-1)이 계산되는 모습 
return 5 * 4!
return 5 * 4 * 3!
return 5 * 4 * 3 * 2!     # n-1의 값들이 누적된다.
return 5 * 4 * 3 * 2 * 1! # 종료조건에 맞아 1을 반환 받음
return 5 * 4 * 3 * 2  # 누적된 값의 반대로 계산을 하게된다.
return 5 * 4 * 6   
return 5 * 24
return 120

---

재귀함수를 사용하여 최댓값 구하기

def find_max(a, n):
    if n == 1:                         # 3번
        return a[0] 
        
    max_n = find_max(a, n-1)           # 4번
    
    if max_n > a[n-1]:                 # 5번
        return max_n
    else:
        return a[n-1]

v = [17, 92, 18, 33, 58, 7, 33, 42]    # 1번
print(find_max(v, len(v)))             # 2번

[Output]
92

1. [17, 92, 18, 33, 58, 7, 33, 42] 리스트를 v에 담아 저장한다.

2. 변수 v를 함수의 인자값으로 넣어준다.

3. v의 길이(n)가 1이면 a[0]을 반환한다.

4. n이 1이 아닌 경우 변수 max_n을 생성하여 find_max를 재귀 호출한다.
   이때 n에 8부터 1까지 수가 거꾸로 누적이 된다.

# find_max에 리스트 a와 n의 숫자 8부터 1까지 거꾸로 누적되어 있다. 
max_n = find_max(a, 8)    # 처음 실행한 함수
max_n = find_max(a, 7)    # 재귀 함수 호출 (n-1)
max_n = find_max(a, 6)
max_n = find_max(a, 5)
max_n = find_max(a, 4)
max_n = find_max(a, 3)
max_n = find_max(a, 2)
max_n = find_max(a, 1)    # 종료 조건으로 a[0]을 반환 후 종료

# 재귀함수가 종료조건에 의해 끝나면 n의 숫자인 8부터 1까지 인덱스로 사용되고 a에서 인덱스n에 해당하는 값을 max_n에 저장한다.
max_n = 42 33 7 58 33 18 92 17 # 여기선 누적만 되어있음

토끼굴

[ ] 사용하지 않고 인덱스 역할을 어떻게 하는거지?

5. max_n의 값을 마지막부터 하나씩 가져온다.
   따라서 현재 목적은 최대값을 구하는 식이므로 조건문을 지정하여 값을 비교한다.

...
    if max_n > a[n-1]:
        return max_n
    else:
        return a[n-1]
...

# 17 > a[1-1] == 17 > 17 => return a[n-1] => 17
# 17 > a[2-1] == 17 > 92 => return a[n-1] => 92
# 92 > a[3-1] == 92 > 18 => return max_n => 92
# 92 > a[4-1] == 92 > 33 => return max_n => 92
# 92 > a[5-1] == 92 > 58 => return max_n => 92
# 92 > a[6-1] == 92 > 7 => return max_n => 92
# 92 > a[7-1] == 92 > 33 => return max_n => 92
# 92 > a[8-1] == 92 > 42 => return max_n => 92

6. 위 조건문에 따라 최종적으로 큰 수는 92로 반환한다.

참고

• 6. 재귀함수 - SKKU 기초SW 과목
• 재귀함수란? 간단하게 알아보자. - lygggg