IT 용어_재귀(再歸, Recursion)

    재귀(再歸, Recursion)는 컴퓨터 과학에 있어서 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻하며, 이를 프로그래밍에 적용한 재귀 호출(Recursive call)의 형태로 많이 사용된다. 통상, 문제 내 작은 형태의 문제가 연이어 포함된 내포 구조의 프로그래밍에 적합하며 자기 자신을 다시 호출하여 문제를 푸는 방법을 쓴다. 원래 문제보다 작아진 부분 문제를 대상으로 한다. 마치 루프(Loop, 반복)처럼 어떤 일을 반복적으로 수행하는 데에 유리하고, 트리 및 연결 리스트와 같은 컴퓨터 자료구조에 유용하다. 또 사진이나 그림 등에서 재귀의 형태를 사용하는 경우도 있다.

    재귀함수는 정의 단계에서 자신을 재참조하는 함수를 뜻하며, 어떤 사건이 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 한다.

    꼬리 재귀 최적화가 적용된 알고리즘은 영원히 반복하면서 프로그램이 멈춰버린다. 따라서 재귀함수 설계 시, 입력값이 종료 조건으로 수렴하는지를 꼭 검증해야 한다.

    재귀 호출은 점화식과 종료 조건만 구현하면 만들 수 있기 때문에 가시성이 높고, 구현하기 쉽다. 단, 파이썬(3.9.13)은 3000번까지 재귀호출이 가능하기 때문에 많은 호출이 필요할 때에는 사용이 불가하다. 또한 재귀호출과 반복문 구현은 시간 복잡도는 같으나, 실제 Call Stack 과정에서 재귀호출이 속도가 느리고, 메모리를 크게 차지한다. 즉, 반복분 구현은 전체 과정을 서술해야하기 때문에 재귀호출 보다 구현이 복잡하나 속도가 빠르고 호출의 제한이 없다는 장점이 있다. 결국, 프로그래밍 용이성 및 메모리 소요 크기로써 이 둘(재귀/반복) 중에 선택이 필요하다.

 

재귀적 프로그래밍의 특징

○ 프로그램을 직관적이고, 간결하게 작성 가능

○ 재귀 호출은 루프 보다 다소 비효율적

 - 재귀 호출은 루프와 달리, 메모리에 함수 복사본을 반복적으로 만들기 때문에 루프(반복) 보다 다소 느리고 더 많은 메모리가 필요

○ 내포 구조(nested)로 된 데이터를 다루기에 적합

 - 재귀 호출시, 함수 내 코드도 데이터처럼 내포된 구조로써 포함되는, 일종의 추상 자료형 형태로도 볼 수 있음

○ 최적의 하위 구조(Optimal Substructure)

 - 크기가 더 작은 동일 유형의 하위 문제를 갖는 경우로써, 상위 문제와는 크기만 작고 같은 유형을 갖는 하위 문제들을 포함하는 구조

 - 하위 최적 해법을 사용해 상위 최적 해법을 구할 수 있음

○ 하위 문제의 반복 계산(Overlapping Subproblems)

 - 반복되는(동일) 재귀 호출이 다수 발생하는 경우로, 이로 인해 실행 속도가 크게 늘어날 수 있다. 

 

최대 재귀 한도

    파이썬은 최대 재귀 한도(Maximum recursion depth)를 정해 허용되는 재귀 호출의 최대 반복 횟수를 지정한다. 한도는 파이썬 버전과 운영체제 등에 따라 다를 수 있으며 필요에 따라 조정하는 것도 가능하다. 사용하는 파이썬의 최대 재귀 한도는 다음 명령문으로 확인할 수 있다.

import sys
sys.getrecursionlimit()

 

재귀 시각화

○ 소용돌이

 - 재귀를 이해하기 위해 재귀 알고리즘의 작동과정을 시각화 해보자. 시각화를 위해 turtle 모듈을 이용한다. 재귀로 정의된 draw_spiral() 함수는 아래 그림과 같은 소용돌이를 그린다.

import turtle

def draw_spiral(my_turtle, line_len):
    if line_len > 0:
        my_turtle.forward(line_len)
        my_turtle.right(90)
        draw_spiral(my_turtle, line_len - 5)


my_turtle = turtle.Turtle()
my_win = turtle.Screen()
draw_spiral(my_turtle, 100)
my_win.exitonclick()

 

○ 프랙탈 트리

 - 아래 이미지처럼 아무리 확대하더라도 항상 동일한 구조를 보여주는 사물이 프랙탈(fractal)이다. 프랙탈의 구조는 재귀와 매우 밀접한 관계를 갖는다. 예를 들어, tree() 함수는 아래 모양의 프랙탈 트리를 그린다.

import turtle
# import time                    # 주의: repl.it 사이트에서 오류 발생

def tree(branch_len, t):
    if branch_len >= 15:           # 종료조건: branch_len < 15
        t.forward(branch_len)    # 전진
        # time.sleep(1)          
        t.right(20)              # 오른쪽 가지치기
        tree(branch_len - 15, t)
        t.left(40)               # 왼쪽 가지치기
        tree(branch_len - 15, t)
        t.right(20)              # 한 단계 후진
        t.backward(branch_len)

t = turtle.Turtle()
my_win = turtle.Screen()
t.left(90)
t.up()
t.backward(100)
t.down()
t.color("green")
tree(75, t)
my_win.exitonclick()

 

재귀호출 종료 조건

재귀호출을 사용하려면 반드시 다음과 같이 종료 조건을 만들어주어야 한다.

def halo(count):
    if count == 0:
        return
    print('halo world!', count)
    count -= 1
    halo(count)


halo(5)

 

재귀적 관계

○ 피보나치수열

○ 팩토리얼

○ 이항 계수

○ 수열의 점화식

○ 하노이 탑

○ 재귀적 알고리즘 : 병합 정렬, 퀵 정렬, 이전 탐색, DFS, 백트래킹

 

 

출처 : https://ko.wikipedia.org/wiki/%EC%9E%AC%EA%B7%80_(%EC%BB%B4%ED%93%A8%ED%84%B0_%EA%B3%BC%ED%95%99) 

재귀 (컴퓨터 과학) - 위키백과, 우리 모두의 백과사전

출처 : https://namu.wiki/w/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98

재귀함수 - 나무위키

출처 : https://velog.io/@jewon119/01.%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B8%B0%EC%B4%88-%EC%9E%AC%EA%B7%80-%ED%98%B8%EC%B6%9CRecursive-Call

알고리즘 기초 - 재귀 호출(Recursive Call)

출처 : http://www.ktword.co.kr/test/view/view.php?m_temp1=5938 

재귀 호출

출처 : https://dojang.io/mod/page/view.php?id=2352 

파이썬 코딩 도장: 31.1 재귀호출 사용하기

출처 : https://codingalzi.github.io/pybook/recursion.html

10. 재귀 함수 — 파이썬 프로그래밍 기초