[Python] 알고리즘 - 재귀용법(RecursiveCall)

[Python] 알고리즘 - 재귀용법(RecursiveCall)

---

• 재귀용법(RecursiveCall)은 실제로 많은 알고리즘들에서의 기반이 되기 때문에 알아두어야 할 기본적인 알고리즘이다.
• 재귀용법은 함수 내에서 동일한 함수 자신을 호출하는 형태를 띄는 것을 말한다.
• 재귀용법을 다음 여러 예제들을 해결하며 이해해보도록 하자.

1. 팩토리얼(Factorial)

• 사실, 팩토리얼은 재귀용법을 활용한 알고리즘 중 가장 쉬운 예시에 속한다.

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

• 위와 같이 if 조건문을 걸어 input값이 임계값보다 크거나 작으면 Output을 반환하며 재귀호출을 종료하는 구조가 일반적인 구조이다.

 

Input:

factorial(0)

Output:

0

 

Input:

factorial(4)

Output:

24

 

 

2. 스택(Stack)

• 스택(Stack)은 선입후출(FILO), 후입선출(LIFO) 구조를 가지는 자료구조이며, 자료를 밀어넣는 것이 push, 자료를 빼내는 것은 pop라고 용어를 칭한다.
• 재귀용법을 활용하여 구현하면 다음과 같다.

def stack_recursive(mydata):
    if mydata < 1:
        print("="*30)
        print ("push 종료")
        print("="*30)
    else:
        print(f"{mydata} is pushed")
        stack_recursive(mydata - 1)
        print(f"returned : {mydata}")

 

Input:

stack_recursive(5)

Output:

5 is pushed
4 is pushed
3 is pushed
2 is pushed
1 is pushed
==============================
push 종료
==============================
returned : 1
returned : 2
returned : 3
returned : 4
returned : 5

 

3. 리스트의 합(sum)

• 재귀용법을 사용해 리스트가 주어졌을 때, 해당 리스트의 모든 원소의 합을 구하는 알고리즘을 구현해보았다.

def rec_sum(mylist):
    if len(mylist)==0:
        return 0
    elif len(mylist)==1:
        return mylist[0]
    else:
        return mylist[0] + rec_sum(mylist[1:])

Input:

#mylist = [1,2,3,4,5,6,7,8,9,10]
for i in range(11):
    import numpy as np
    mylist = list(np.arange(i+1))
    print(rec_sum(mylist))

Output:

0
1
3
6
10
15
21
28
36
45
55

 

4. Palindrome

• 예전 포스트인 슬라이싱(Slicing)에서 다루었던 Palindrome 구별 함수를 재귀용법을 활용하여 구현하였다.

def rec_palindrome(text):
    if len(text) <= 1:
        return True
    
    if text[0] == text[-1]:
        return rec_palindrome(text[1:-1])
    else:
        return False

Input:

s1 = "saas"
s2 = "paap"
s3 = "KAYAK"
s4 = "REVIVER"
s5 = "ROTATOR"
s6 = "APC"
s7 = "marni"

print(rec_palindrome(s1))
print(rec_palindrome(s2))
print(rec_palindrome(s3))
print(rec_palindrome(s4))
print(rec_palindrome(s5))
print(rec_palindrome(s6))
print(rec_palindrome(s7))

Output:

True
True
True
True
True
False
False