재귀 알고리즘

재귀 알고리즘

---

하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것
중요 – 생각보다 많은 종류의 문제가 재귀적으로 해결 가능함

모든 수의 합

< 재귀 알고리즘 >         vs          < 반복 알고리즘 >

복잡성 측면: 재귀 알고리즘 O(n) vs 반복 알고리즘 O(n)
효율성 측면: 재귀 알고리즘은 좋지 않음

 

n! 을 구하는 알고리즘

def what(n):

    if n<=1:
        return 1
        
    else:
        return n * what(n-1)

 

x가 인덱스 값일 때, 피보나치 순열

def solution(x):

    if x <= 1:
        return x
        
    else:
        return solution(x-1) + solution(x-2)

 

재귀 이진탐색

def solution(L, x, l, u):

    if l>u:
        return -1
        
    mid = (l + u) // 2
    
    if x == L[mid]:
        return mid
        
    elif x < L[mid]:
        return solution(L,x,l,mid-1)
        
    else:
        return solution(L,x,mid+1,u)

 

 

 

 

 

 

---

참고) https://programmers.co.kr/learn/courses/57