Recursion

Minjeong Bak·2021년 12월 22일
WeCode

Algorithm

목록 보기
1/1
post-thumbnail

Recursion

어떠한 것을 정의할 때 자기 자신을 참조하는 것을 말하며 컴퓨터 과학과 수학에서, 재귀는 함수가 자신의 정의에 의해 정의될 때의 개념을 가리킨다.
또한 문제 해결을 위해 문제가 간단해져 바로 풀 수 있도록 알고리즘을 설계해 문제를 해결하는 방법을 말한다.

재귀 함수(Recursive Function)

재귀 호출(recursive call)을 사용하는 함수, 함수 정의에 자기자신을 사용하며 정의하고 호출한다.

재귀 호출(recursive call)

  • 함수 내부에서 함수가 자기 자신을 또다시 호출하는 행위
  • 재귀 호출은 일반적인 상황에서는 잘 사용하지 않지만 알고리즘을 구현할 때 유용하다.
  • 알고리즘에 따라서 반복문으로 구현한 코드보다 재귀 호출로 구현한 코드가 좀 더 직관적이고 이해하기 쉬운 경우가 많다.
  • 재귀 호출은 자기가 자신을 계속해서 호출하여 끝없이 반복되게 되므로(stack overflow) 함수 내에 재귀 호출을 중단하도록 조건이 변경될 명령문을 반드시 포함해야 한다.

Recursion 예시

팩토리얼(Factorial) 함수

1부터 n까지 양의 정수를 차례대로 곱한 값이며 !(느낌표) 기호로 표기
ex) 5!은 5 * 4 * 3 * 2 * 1이며 결과는 120

def factorial(n):
    if n == 1:      # n이 1일 때
        return 1    # 1을 반환하고 재귀호출을 끝냄
    return n * factorial(n - 1)    # n과 factorial 함수에 n - 1을 넣어서 반환된 값을 곱함
 
print(factorial(5))
# 120

  • factorial 함수의 호출

  • factorial 함수의 반환

  • factorial 함수의 호출 순서와 계산 과정

그림 출처: 파이썬 코딩 도장

피보나치 수열(fibonacci sequence)

피보나치 수(Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열을 말한다. 즉 처음 여섯 항은 1, 1, 2, 3, 5, 8이며 그 뒤로 쭉 이어진다. 또한 프로그래밍에서 인덱스가 0부터 시작하는 것과 함께 0번째 항을 0으로 두기도 한다.

f(n) = f(n-1) + f(n-2)
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, .....

재귀함수로 피보나치 수열을 구현할 경우 수학에서의 점화식과 비슷한 형태로 코드를 작성할 수 있기 때문에 가독성이 높아진다. 그러나 재귀함수의 특성상 연산 효율이 떨어진다는 것이 단점인데, 이것은 인덱스 숫자(피보나치 수 몇 번째 값)가 높아질수록 연산 효율이 급격하게 떨어진다는 것이 가장 큰 문제점이다.

피보나치 수열에서 N(input) 번째 수를 반환
만약 n = 4 라면 fib(n) = 3

def fibo(n):
    if n < 3:
        return 1
    else:
        return fibo(n-1) + fibo(n-2)
print(fibo(4)) # 3

출처 및 참고자료 링크

profile
Minjeong Bak

0개의 댓글