재귀 알고리즘(recursive algorithms)

오늘은 재귀 알고리즘(recursive algorithms)에 대해 알아보겠습니다

 

재귀 알고리즘에서 재귀적(recursive)이란 것은 무엇을 의미할까요?

하나의 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 것을 의미하는데욥

 

왜 굳이 자기 자신을 호출하면서 문제를 해결하는가?

-> 많은 종류의 문제들이 재귀적으로 (recursively) 풀리기 때문 

-> 경우에 따라서 재귀 알고리즘 사용시 수월하게 해결 가능( 하노이탑 문제 )

 

아래는 다양한 문제를 재귀적으로 구현한 것들입니다! 

 

1부터 n까지의 자연수 합

 

def hap(n):

    if n <= 1:

        return n

    else:

        return n + hap(n-1)

 

1부터 n까지의 자연수 합 (n! 팩토리얼)

def factorial(n):

    if n <= 1:

        return n

    else:

        return n * factorial(n - 1)

 

피보나치 수열

def fibo(n):

    if n <=1:

        return n

    else:

        return fibo(n-2) + fibo(n-1)

 

 

그렇다면 효율적인가?

-> NO! 

-> 일반적인 반복문이 더 효율적임

-> 같은 함수를 여러번 호출하여 계산 -> 비효율적