자료구조: 재귀 알고리즘(Recursive Algorithms) 기초, 응용

재귀 알고리즘(Recursive algorithms) - 기초

• 재귀 함수란?
  • 하나의 함수에서 자신을 다시 호출하여 작업을 수행
  • 많은 종류의 문제가 재귀적으로 해결 가능
    • 이진 트리(Binary trees)
    • 자연수의 합 구하기
  • 종결 조건(trivial case)이 매우 중요함
• 재귀 알고리즘의 효율
  • 알고리즘의 복잡도 측면과 효율성 측면

 

피보나치 순열

피보나치 순열 재귀적 방법

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

문제 설명에서 피보나치 순열에 대한 정의가 주어졌고, 여러 번 작성해본 적이 있는 코드라서 작성하는 데 큰 어려움을 느끼지 않았다. 그래도 여러 번의 코드 반복 작성과 손으로 디버깅하는 걸 많이 연습해야 할 거 같다.

line2 ~ line5는 더 짧게 고칠 수 있다는 걸 알았다.

if n <= 1:
    return n

 

피보나치 순열 반복적(iterative) 방법

def solution(x):
    if x == 0:
        return 0
    elif x == 1:
        return 1
    else:
        F0 = 0
        F1 = 1
        idx = 2

        while idx <= x:
            Fn = F0 + F1
            F0, F1 = F1, Fn
            idx += 1
        answer = Fn
        return answer

온전히 스스로 풀었다고 하기에는 무리가 있고, 다른 사람의 코드를 참조했다.

 

재귀 알고리즘(Recursive algorithms) - 응용

• 조합의 수 계산
  • 효율성 측면 생각하기
• 재귀 알고리즘의 유용성
  • 하노이의 탑
• 재귀 알고리즘의 효율
  • 피보나치 순열의 경우 불필요한 함수 호출로 인한 성능 저하 발생

재귀적 이진 탐색

처음에 제출했던 답은 효율성 테스트에서 틀렸다. 그래서 나와 똑같이 틀린 사람의 질문 글에서 답변을 보고 코드를 고쳤다. 내가 틀린 부분은 리스트에 찾는 값이 없을 때 -1을 반환하는 부분이었다. 나는 단순히 lower와 upper가 같을 때만을 확인했는데 이렇게 코드를 작성해서 실행할 때는 문제가 없었다. 그런데 질문 글의 답변을 보고 새로운 테스트 케이스를 추가했더니 리스트의 정 가운데에 위치했을 때 (lower == upper) 찾는 값이 있어도 -1을 반환하는 걸 확인했다. 그래서 조건문에 and L[l] != x 를 추가함으로써 해결할 수 있었다.

 

-

프로그래머스 어서와! 자료구조와 알고리즘은 처음이지? - 파트4, 5 수업노트