재귀함수(recursive functions)

하나의 함수에서 **자신을 다시 호출**하여 작업을 수행하는 것.

예시 : 자연수의 합 구하기

  • 1 부터 n까지 모든 자연수의 합을 구하시오.

*<코드 1> 종료조건 없는 재귀함수*

def sum(n) :  
return n + sum(n-1)

위 함수는 n에 대한 종료 조건이 정해져있지 않아 maximum recursion 런타임 에러가 발생한다. 따라서 종료 조건을 추가한다.

*<코드 2> 종료조건을 추가한 재귀함수*

def sum(n) :  
if(n<=1) :  
return n

return n + sum(n-1)

재귀 알고리즘의 효율

*<표 1> 재귀와 반복 함수의 상대적 효율성 비교*

  Recursive version Iterative version
시간복잡도 O(N) O(N)
상대적 효율 낮다(함수 호출 비용) 재귀보다 높을 수 있다.

예시 2 : 피보나치 순열

*<코드 3> 재귀를 이용한 피보나치 순열 구현*

def fi(x):


if(x>=2):  
    return fi((x-1)) + fi((x-2))  

return x      



def solution(x):  
return fi(x)

*<그림 4> 피보나치 재귀 알고리즘의 함수 호출 중복*

<그림 4>와 같이 재귀 알고리즘을 이용하면 같은 계산을 하는 함수가 중복되어 실행되기 때문에 효율성이 높지는 않다.

*<코드 4> 반복문을 이용한 피도나치 순열 구현*

def solution1(x):  
F0 = 0  
F1 = 1  
newF = 0  
n = 0  
#1칸 떨어져 있는 값 F1  
#2칸 떨어져 있는 값 F0


if(x==1):  
    return 1  

while(n<x-1):  
    newF = F1 + F0  
    F0 = F1  
    F1 = newF  
    n += 1   

return newF  

def solution2(x):  
answer = 0  
fa = 0  
fb = 1  
while x > 0:  
x -= 1  
fa, fb = fb, fa+fb  
answer = fa


return answer

재귀 알고리즘 응용

조합의 수 계산

  • n개의 서로 다른 원소에서 m 개를 택하는 경우의 수

*<그림 3> 조합을 계산하는 수학 공식*

Untitled 1

*<그림 4> 조합을 계산하는 수학 공식 분할*

Untitled 2

<그림 3>은 특정한 하나의 원소의 입장에서, 그 원소를 포함하는 경우, 포함하지 않는 경우를 따로 계산해서 더한다. → 재귀적 성질을 이용할 수 있다.

*<코드5> 조합을 재귀를 이용하여 구현*

def combi(n,m):  
if n==m :  
return 1  
elif m==0 :  
return 1  
else :  
return combi(n-1,m) + combi(n-1,m-1)

함수가 한번 실행될 때마다 두번의 재귀가 일어나기 때문에 효율성 측면에서 n이 커지면 매우 낮은 성능을 보이게 될 것이다. **이렇게 효율이 낮은 알고리즘인데도 불구하고 사용하는 이유는 무엇일까?**

재귀 알고리즘의 유용성

효율성은 낮을 수 있지만 사람이 생각하고, 구현하고자 하는 방식을 재귀적으로 구현할 때 쓰임새가 좋다.

재귀함수 응용 : [Gold V] 하노이 탑 - 1914

[문제 링크](https://www.acmicpc.net/problem/1914)

성능 요약

메모리: 31120 KB, 시간: 756 ms

분류

임의 정밀도 / 큰 수 연산, 재귀

제출 일자

2024년 6월 4일 10:51:53

문제 설명

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

  1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
  2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 100)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

N이 20 이하인 입력에 대해서는 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다. N이 20보다 큰 경우에는 과정은 출력할 필요가 없다.

풀이

n = int(input())

def cal\_hi(n):  
return 2\*\*n - 1

print(cal\_hi(n))

def hanoi(n, start , end , bridge):  
if(n == 1):  
print(start,end)  
return  
hanoi(n-1,start,bridge,end) # 1 → 3 → 2  
print(start,end)  
hanoi(n-1,bridge,end,start) # 2 → 3 → 1

if(n<=20):  
hanoi(n, 1, 3, 2) # 1→ 2 → 3

하노이탑의 움직임 횟수를 알아내는 것은 점화식을 통해 쉽게 해결이 가능하다. 하노이탑의 순서를 재귀함수를 이용하여 출력하는 것이 관건인 문제이다.

3개의 스틱이 있다고 가정할 경우(1번, 2번 , 3번) 하노이탑의 규칙 상으로 무조건 중간에 스틱하나를 거쳐서 이동해야한다. 1→ 2 → 3 , 1 → 3 → 2 , 2 → 3 → 1 의 모든 경우의 수를 재귀함수로 표현하면 위 함수와 같다.

티스토리툴바