백준 25501 재귀의 귀재

목차

• 재귀
• 기존 재귀 vs 꼬리 재귀
• 재귀의 귀재

재귀

재귀란?

자기 자신을 호출하여 작업을 수행하는 방식

특정 분기까지 자기 자신을 계속해서 호출하는데, 주로 반복문을 구현할 때 사용한다.

러시아 인형과 알고리즘 간에 어떤 상관관계가 있을까? 러시아 인형 속에 더 작은 러시아 인형이 있고 또 그 인형 안에 더 작은 인형이 있는데, 이는 러시아 인형이 너무 작아서 다른 인형을 담지 못할 때까지 계속 됩니다. 이처럼 어떤 문제를 해결하기 위해 알고리즘을 설계할 때 동일한 문제의 조금 더 작은 경우를 해결함으로써 그 문제를 해결하는 것이다. 문제가 간단해져서 바로 풀 수 있는 문제로 작아질 때까 말입니다. 이런 테크닉을 재귀라고 합니다.

재귀를 사용하는 이유

• 재귀적인 표현이 자연스러운 경우 코드가 간결해짐 -> 가독성이 증가됨

• 변수를 많이 만들 필요가 없음

기본 재귀의 단점

지속적으로 함수를 호출하게 되어 지역변수, 매개변수, 반환 값들을 모두 process stack 에 저장해야 함, 이는 반복문에 비해 메모리를 많이 사용하게 되고 속도 저하 + 오류 발생 가능성 상승으로 이어짐

이 stack 공간이 다 차버리는 현상을 '스택 오버 플로우' 라고 한다.

tail recursion (꼬리 재귀)

꼬리 재귀는 재귀 호출이 끝나면 아무 일도 하지 않고 결과만 바로 반횐되도록 하는 방법이다.

꼬리재귀의 핵심은 return에 연산이 필요 없다는 것

아래 간단한 recursive에 대한 예시 코드

int Recursive(int n) 
{
 if(n==1) return 1;
 return n + Recursive(n-1);
}
int Tail_Recursive(int n, int acc)
{
 if(n==1) return acc;
 return Tail_Recursive(n-1, n + acc );
}

일반 재귀는 값을 받으면 그 값에 대한 연산을 하고 다른 함수에게 전달을 해주었다.

반면에 꼬리 재귀는 아무것도 하지 않고 값을 전달한다.

다시 한 번 정리를 해보면 아래와 같다

일반 재귀는 마지막부분이 아래와 같이 생겼다.

이 함수는 스택에 쌓였다가 마지막 계산될때 자기 자리를 기억하고 있어야 한다.

자기자리란 ?
즉 스택이 빠져나올때 정확히 언제 계산이 되어야 하는지, 리턴 후 돌아갈 위치 값이 저장되는 것

return n * factorial(n-1);

하지만 꼬리 재귀의 마지막 부분은 굳이 자기자리를 기억하지 않아도 된다. 그래서 스택에 위치 값을 저장할 필요도 없어진다.

return factorial(n - 1, n * total);

다시 정리하면 꼬리 재귀는 자신이 호출한 함수한테 받은 결과값에 아무 일도 하지 않고 바로 반환 하기 위해 꼬리에서 함수를 호출하는 방식이다.

그럼 이제 아래 내용을 살펴보자

출력값은 Palindrome 여부, cnt 값이다.

로직은 인덱스들을 한 칸씩 옮기며 cnt를 +1 증가하며 서로 같은 값인지를 확인하며 문자열의 중앙값까지 같다면 true를 반환하는 방식이다.

import sys

N = int(sys.stdin.readline())


def recursion(s, l, r):
    global cnt
    cnt += 1 # 카운트 추가

    if l >= r: # 왼쪽 인덱스와 오른쪽 인덱스가 서로 만난다면 팰린드롬이다
        return 1
    elif s[l] != s[r]: # 왼쪽 인덱스와 오른쪽 인덱스 값이 다르다면 팰린드롬이 아니다
        return 0
    else:
        return recursion(s, l+1, r-1)

def isPalindrome(s):
    return recursion(s, 0, len(s)-1) # 문자열 길이보다 1 작게



for _ in range(N):
    cnt = 0
    print(int(isPalindrome(sys.stdin.readline().rstrip())), cnt)

여기서 핵심은 return 시 추가 연산을 하지 않고 결과값을 그대로 반환하는 것이다.

문자열이 Palindrome인지를 판단하기 위해서는 왼쪽에서 인덱스 1칸, 오른쪽에서 인덱스 1칸을 증가시켜야 하는데 이를 매개변수로 따로 만들어서 처리하는 것이 아닌 다음 함수를 호출할때 해당하는 그 값을 바로 넘겨주는 것이다.

이렇게 사용하게 되면 마지막 함수 호출시 스택에 쌓여있던 함수들이 빠져나오면서 순서대로 계산되는 것이 아닌 자기자리를 기억하지 않으므로 한 번에 호출되는 것을 알 수 있다.