[알고리즘] 재귀함수

이호영·2021년 7월 16일
0

python

목록 보기
9/13

재귀함수란?

  • 함수가 자신을 다시 호출하는 구조로 만들어진 함수

  • 탈출조건이 있어야 stack overflow를 방지할 수 있다.

재귀함수를 잘 푸는 방법?

  • 호출 관계는 파악하기 쉬우나, 호출 순서를 파악 하기가 힘들어진다.
    하지만 호출 순서는 재귀가 복잡해 질수록 파악 하기가 힘들어지고,
    호출 순서를 파악해야 될 상황이 오기전에 호출 관계를 파악하여 해결하여야한다.
  • 그리고 재귀 함수는 자칫 잘못 이용하면 시간이 오래 걸리게 되고 프로그램에 부담이 되기에 조심하여야 한다.

재귀함수와 for문 비교

같은 일을 되풀이 할때에는 반복을 사용한다. for나 while등의 반복문을 사용하는 것으로 반복횟수를 가지고 있는 변수를 사용하여 일정횟수동안이나 어떤 조건이 만족될 때 까지 반복하도록 했다. 이러한 반복 구조는 문제를 간결하고 효율적으로 해결할 수 있다.

그러나 어떤 문제들은 반복을 사용하면 지나치게 복잡해지는 경우도 있다. 이런 경우에는 재귀가 매우 좋은 해결책이 될 수 있다. 예를 들면 트리 알고리즘을 들 수 있다. 트리의 순회나 노드의 삽입연산 등 재귀가 많이 사용되는데, 이들을 반복으로 구현하면 코드가 매우 복잡해진다. 따라서 재귀는 재귀적인 문제나 그러한 자료구조를 다루는 프로그램에 매우 효율적이다.

재귀함수를 구현하는 두가지 방법

  1. 재귀함수를 호출하는 부분을 상단에 두고 표현
def function(입력):
    if 입력 > 일정값: # 입력이 일정 값 이상이면
        return function(입력 - 1) # 입력보다 작은 값
    else:
        return 일정값, 입력값, 또는 특정값 # 재귀 호출 종료
  1. 재귀함수가 돌아가는 부분은 아래의 부분에 삽입
def function(입력):
    if 입력 <= 일정값:              # 입력이 일정 값보다 작으면
        return 일정값, 입력값, 또는 특정값              # 재귀 호출 종료
    function(입력보다 작은 값)
    return 결과값

하노이 탑 문제를 위 방법으로 구현해보자

  1. if 문 안에서 호출
def hanoi(n,start,mid,end):

    if n == 1:
        move.append([start,end])
    else:
        hanoi(n-1,start,end,mid)
        move.append([start,end])
        hanoi(n-1,mid,start,end)

move = []

n = int(input())

hanoi(n,1,2,3)

print((n**2)+1)

for i in move:
    print(i[0], i[1])
  
  1. if 문 밖에서 호출
def hanoi(n,start,mid,end):

    if n == 1:
        print([start,end])
        return 0

    hanoi(n-1,start,end,mid)
    print([start,end])
    hanoi(n-1,mid,start,end)

move = []

n = int(input())

hanoi(n,1,2,3)

print((n**2)+1)

분리해보니 둘의 차이는 잘 모르겠다..

재귀함수의 틀을 이해해서 응용하는 방식으로 공부해야겠당

0개의 댓글