(python)알고리즘, 자료구조 - 재귀알고리즘(1)

'재귀' 란?

자신을 정의할 때 자기 자신을 '재참조'하는 방법

요런 느낌

재귀 알고리즘

• 정의: 함수를 정의할때 해당 함수를 사용하여 정의하는 방법
• 장점: 함수가 간단하다, 직관적으로 이해하기 쉽다.
• 단점: 효율성이 좋지 못하다.
• 주의할점: 무한반복을 피하기 위해 반드시 종결지점을 만들어 주어야 한다.

문제(피보나치 수열)

인자로 0 또는 양의 정수인 x 가 주어질 때, Fibonacci 순열의 해당 값을 구하여 반환하는 함수 solution() 을 완성하세요.

Fibonacci 순열은 아래와 같이 정의됩니다.
F0 = 0
F1 = 1
Fn = Fn - 1 + Fn - 2, n >= 2

 

문제풀이(1) - 재귀적 방법

def solution(x):
    answer = 0
    if x == 0:
        answer = 0
    elif x ==1:
        answer = 1
    else:
        answer = solution(x-1) + solution(x-2)
    return answer

문제풀이(2) - 반복문

def solution(x):
    answer = 0
    f = [0,1]
    if x >= 2:
        n = 2
        while n <= x:
            a = f[n-1] + f[n-2]
            f.append(a)
            n = n+1
    answer = f[x]
    return answer

끝.