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

주어진 문제가 있을 때, 이것을 같은 종류의 보다 쉬운 문제의 답을 이용해서 풀 수 있는 성질을 이용하여 같은 알고리즘을 반복적으로 적용함으로 써 풀어내는 방법.

재귀함수 (recursive functions) 란?

하나의 함수에서 **자신을 다시 호출**하여 작업을 수행하는 것.

EX)

이진 트리(binary trees)
자연수의 합 구하기(1부터 n까지 모든 자연수의 합을 구하시오)
def sum(n): if n <= 1: return n else: return n+sum(n-1)

재귀알고리즘은 항상 그와 대칭을 이루는 반복적인 알고리즘을 가지게 된다.

아래와 같은 재귀버전을 Recursive version

def sum(n):  
    if n <= 1:  
        return n  
    else:  
        return n+sum(n-1)

아래와 같은 반복적인 버전을 Iterative version 이라고 부른다.

def sum(n):  
    s = 0
    while n >= 0:
        s+=n
        n -= 1
    return s

해당 둘의 함수의 복잡도는 O(n)으로 같다 하지만 효율성에서 본다면

Recursive version은 n이 증감함에 따라 함수를 호출하고 return 하는데 드는 부가적인 작업이 필요하기 때문에 Iterative version보다 떨어진다. 사람이 보기엔 편하지만 효율성 측면은 항상 조심해야한다.

극단적으로 보면 def sum(n): return n \* (n + 1)//2 만해도 구할 수 있고 복잡도 측면에서도 좋은 알고리즘이라고 볼수있다

what 은 팩토리얼을 구하는 함수 = n!

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

연습문제

 알고리즘의 종결 조건 필수 조건.


 연습문제 - Fibonacci 순열

 F0 = 0
 F1 = 1
 Fn = F(n-1) + F(n-2), n>=2

def solution(x):  
    if x == 0:  
        return 0  
    if x == 1:  
        return 1  
    if x >= 2:  
        return solution(x-1) + solution(x-2)