재귀알고리즘(recursive algorithms)

같은 알고리즘을 반복적으로 적용함으로써 풀어내는 방법

피보나치 순열
: 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다
예) 1 1 2 3 5 8 13 21 34 ...

정의)
F0 = 0
F1 = 1
Fn = Fn - 1 + Fn - 2, n >= 2

문제)
0 이상의 정수 x를 인덱스로 가지는 피보나치 수열에서 x(인덱스)에 해당하는 값을 구하라

비효율적

def solution(x):
    if x < 2:			# 0, 1는 해당 값을 바로 리턴한다.
        return x
    a, b = 0, 1			# a:첫번째 인덱스, b:두번째 인덱스
    for i in range(x - 1):	# x가 2인경우 단 한번만 계산하기 위해 x-1까지 계산한다.
        a, b = b, a + b		# python문법, a=b, b=(이전 a값)a+b의 효과를 낸다.
    print(b)
    
    return b

효율적

def solution(n):
	if x < 2:
		return x
	else:
		return solution(x-1) + solution(x-2)	# 피보나치 수열의 정의를 그대로 구현

출처: 프로그래머스 강의 "어서와! 자료구조와 알고리즘은 처음이지?"