python 재귀알고리즘 (Recursive Algorithms)

재귀함수에 의해 구현이 되는 알고리즘

재귀함수란 ?(recursive functions)- 하나의 함수에서 자신을 다시 호출해서 작업을 수행하는 것을 말한다.

생각보다 많은 종류의 문제가 재귀적으로 해결가능하다고한다.

 

#재귀적인버전(Recursive version)
#O(n)
def sum(n):
    
    if n<=1:
        print("n :: ",n)
        return n
    else:
        print(n)
        return n + sum(n-1)

a = int(input("Number : "))
print(sum(a))

 

출력

 

n이 1이되면 n+(n-1)이 아닌 n을 반환하기 때문에 -값을 반환하지 않게됨(종결조건)

 

 

#반복적인 버전(lterative version)
#O(n)
def sum(n):
    s=0
    while n >=0:
        s+=n
        n-=1
        print("s :",s ,"| n ::",n)
    return s

a = int(input("Number:: "))
print(sum(a))

출력

보기쉽게 s와 n을 찍어봤다.

s는 4+3+2+1을 누적하는 값을 담은 변수이고

n은 입력값에서 -1 되는 변수 n+(n-1) 

 n이 0 이하일때 while 문이 종료되기 때문에 n값을 더한 10 출력

 

 

알고리즘 복잡도는 O(n)으로 둘다 동일하지만 

알고리즘의 효율성 측면에서는 첫번째버전(Recursive version)이  n이 증가할때마다 함수를 호출을 해야해서 효율성이 떨어짐

 

 

 

*재귀함수로 구현하는 팩토리얼 문제

 

N!=NX(N-1)X(N-2)X(N-3).......

0!=1

1!=1X(1-1)=1X0!=1

2!=2X1

3!=3X2X1

 

#n! 구하는 함수 예시

def factorial(n):
    if n <=1:
        return 1 #마지막 X1을 위해 1 리턴
    else:
        print("n :",n)
        return n*factorial(n-1)
    
    
a = int(input("Number :: "))
print(factorial(a))

출력

리턴에서 자기자신을(factorial함수) 다시불러서 n-1 값을 넣어 연산

팩토리얼을 마지막에 x1로 끝나기 때문에 n값이 1이 됐을때는 1을 리턴한다.

 

 

이렇게 짧게도 구현가능

def factorial(n):
    return n * factorial(n-1) if n > 1 else 1

a = int(input("Number :: "))
print(factorial(a))

 

 

 

 

 

+재귀함수가 아닌 for문을 이용한 방법

작년 코테때 for문으로 구현했었는데 재귀함수를 알고나니 for문 구현방식이 더 복잡하게 느껴짐...