재귀 알고리즘 기초 (recursive call)

자기 자신을 재참조한다 라는 정의를 가지고 있으며, 쉽게 설명하면,

함수 안에서 동일 함수를 호출한다고 생각하면 된다.

 

재귀를 설명할 때 제일 많이 등장하는 예제가 팩토리얼 문제이다.

 

팩토리얼의 개념은 아래와 같다.

3! = 3 x 2 x 1

2! = 2 x 1

1! = 1

 

여기서 이를 재귀로 구현을 해보려면 규칙을 찾는 것이 우선이다.

팩토리얼에는 무슨 규칙이 있을까?

말할 수 있는 규칙으로는 주어진 숫자가 3이라고 했을 때, 결과값은 3 x 2!과 같다.

2! 역시 2 x 1! 과 같다.

이를 통해서 우리는 식을 세울 수 있게 되는데, n! = n x (n-1)! 을 확인할 수가 있다.

 

 

이를 이제 코드로 구현해보자.

def factorial(num):
	
    if num == 1:
    	return num
        
    else:
    	return num * factorial(num-1)

factorial(3)을 일일히 한 번 풀어보자

입력값이 1이 아니니 else문으로 들어가서 num * factorial(num-1)을 실행하게 되는데,

factorial(2)도 역시나 num * factorial(num-1)을 실행하게 된다.

처음에 헷갈릴 수 있으나, 손으로 한 번 써보고, 작성을 하면 이해가 될 것이라 생각한다.

 

 

 

다음 예제로는 회문을 검사하는 재귀함수를 구현해보자.

회문(Palindrome)은 앞에서 내리읽으나 뒤에서 올려 읽으나 다 말이 되게 쓴 것 이라는 정의를 가지며

기러기, 토마토를 생각하면 쉽게 이해할 것이다.

 

여기서는 level이라는 단어를 가지고 설명을 하려고한다.

회문을 검사하려면 일단 제일 먼저 무엇을 보아야할까?

재귀를 안쓰고 접근을 해본다면, 가운데 인덱스를 중심으로 한칸씩 양옆으로 옮기며 문자 비교를 하는 방법이 있을 것이다.

 

그러나 만약 맨 처음글자와 끝글자부터 비교해가는 함수를 구현한다면?

왠지 재귀로 구현을 할 수 있을 것 같다.

level에서 첫 글자 ,끝 글자 둘 다 같은 글자이기에 다음 글자로 넘어간다. 즉 eve에 대해 다시 판별을 해야한다.

그리고 한글자만 남게된다면 True를 받으면 될 것 같다.

이를 코드로 한 번 구현해보자.

def Palindrome(string):
	
    if len(string)<=1:
    	return True
        
    if string[0] == string[-1]:
    	return Palindrome(string[1:-1])
        
   '''
   level
   eve
   v
   '''
    else:
        return False

 

마지막으로 한 문제만 더 정리하고 마무리 짓고자 한다.

4를 4보다 작거나 같은 숫자로 표현하려면 아래와 같다.

1+1+1+1, 2+1+1, 1+2+1, 1+1+2, 2+2, 3+1, 1+3, 총 7가지이다.

 

5를  표현하면 13가지가 나온다.

1은 1가지, 2는 2가지 3은 4가지가 나온다.

 

여기서의 규칙은 무엇일까?

2에서의 경우와 3에서의 경우와 4에서의 경우를 더하면 5에서의 경우의 수가 나온다.

6에서의 경우의 수는 3과 4와 5에서의 경우를 전부 더한 값과 같을 것이다.

 

def func(data):

    if data == 1:
        return 1
        
    elif data == 2:
        return 2
        
    elif data == 3:
        return 4
    
    return func(data-1) + func(data-2) + func(data-3)