🧭Recursion

intro

🍓 재귀함수란, 자기 자신을 다시 호출하는 함수이다. 함수 내에 다시 함수를 불러서, 동일 함수 로직을 반복적으로(재귀적) 진행한다. DFS 구현을 위해 자주 사용되는 개념. 아래 코드 예시 참조.

def recursive_function():
    print('recursive call')
    recursive_function()

recursive_function()

 

→ 무한히 출력되다가 python의 경우 'RecursionError: maximum recursion depth exceeded while calling a Python object'라는 메시지 출력 - 재귀 최대 허용 깊이가 있어 오류 메시지가 끝에 출력되며 종료. 함수를 부를 때 마다 스택 자료 구조에 함수가 계속 쌓이면서 컴퓨터 메모리에 적재가 된다. 따라서, 메모리는 한계가 있으므로 재귀 깊이 제한을 느슨하게 하거나, 별도 스택 자료구조를 이용하는 방법을 사용할 수 있다. 재귀는 여러 문제를 풀면서 익숙해지고 적응하는 게 BEST. 재귀함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있다. (단, 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수 있으므로 신중하게 사용해야 함!) 또한 모든 재귀함수는 반복문을 이용하여 동일한 기능을 구현할 수 있음 (역도 가능) / 재귀함수가 반복문보다 유리한 경우도, 불리한 경우도 있다. (문제 상황별로 구별) 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓임 (따라서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀함수를 이용하는 경우가 많다 - 대표적으로 DFS를 더 간결하고 짧은 코드로 구현하기 위해 재귀함수를 사용하는 경우가 많음) divide & conquer, DP, backtracking, DFS 등 다양한 알고리즘에 적용되는 recursion 필수 숙지! (ex 하노이 탑, Tree Traversal(Inorder, preorder, postorder)

 

→ Recursion helps in logic building. Recursive thinking helps in solving complex problems by breaking them into smaller subproblems.

 

→ Steps

① define a base case: Identify the simplest (or base) case for which the solution is known or trivial. This is the stopping condition for the recursion, as it prevents the function from infinitely calling itself.

② define a recursive case: Define the problem in terms of smaller subproblems. Break the problem down into smaller versions of itself, and call the function recursively to solve each subproblem.

③ Ensure the recursion terminates: Make sure that the recursive function eventually reaches the base case, and does not enter an infinite loop.

④ Combine the solutions: Combine the solutions of the subproblems to solve the original problem.

 

→ stack 자료구조를 사용하는 이유: stack은 LIFO(Last-In First-Out) 구조이므로 가장 최근에 실행된 recursive function이 먼저 실행되기 때문에 실제 메모리 구조상 stack 메모리에 함수 호출 때마다 적재된다.
(When any function is called from main(), the memory is allocated to it on the stack. A recursive function calls itself, the memory for a called function is allocated on top of memory allocated to the calling function and a different copy of local variables is created for each function call. When the base case is reached, the function returns its value to the function by whom it is called and memory is de-allocated and the process continues)

 

→ disadvantages

① recursive programs typically have more space requirements / more time to maintain the recursion call stack

② recursion can make the code more difficult to understand & debug(it requires thinking about multiple levels of function calls)

 

→ advantages

① provides a clean & simple way to write code

implementation

🍓 재귀함수를 문제 풀이에서 사용할 때는 재귀함수의 종료 조건을 반드시 명시해야 한다. 종료 조건을 명시하지 않으면 RecursionError 발생하고 함수가 무한히 호출. 아래 예제를 참조

def recursive_function(i):

    if i == 5:
        return #recursion end 
    print(i,'th recursion function calls', i+1, 'the recursion function')
    recursive_function(i+1)
    print(i,'th recursion function ends')

recursive_function(1)

🍓 마치 스택처럼, 함수에 대한 정보가 스택 프레임에 쌓이면서 차례대로 호출되다가 가장 마지막에 호출된 함수부터 차례대로 종료. 아래 그림을 참고하자. 가장 먼저 호출되는 재귀 함수가 맨 처음과 끝을 담당. 그 다음 호출되는 재귀 함수가 두 번째 처음과 끝을 담당..... 이렇게 계속 내부로 진행. 맨 마지막 호출되는 재귀함수에서 return 처리. 아래 그림 기준 오른쪽으로 진행되는 방향이 꺾여서, recursive_function() 호출 이후 아래 코드가 차례대로 진행.

examples

① factorial

def factorial_recursive(n):
    if n<=1:
        return 1
    return n*factorial_recursive(n-1)

print(factorial_recursive(5))

 

② euclidean algorithm

🍓 두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘으로 '유클리드 호제법'이 있다. 두 자연수 A,B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 하자. 이 때 A와 B의 최대공약수는 B와 R의 최대공약수와 같다. 아래 재귀 코드 참조

a,b=map(int,input().split())

def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)

print(gcd(a,b))

 

🧭 <BOJ S5 17478 재귀함수가 뭔가요?>

Q. 함수 안에 return문을 먼저 넣고 동일 재귀 함수 넣기 전과 뒤 각각 print()문 진행

 

🧭 <BOJ S3 4779 칸토어 집합>

Q. 함수 안에 재귀함수가 2개 있는 문제. 가운데는 빈칸으로 놔두고 빈칸 기준 앞과 뒤 각각 재귀함수 진행

 

🧭<BOJ B5 27433 팩토리얼 2 + B2 10870 피보나치 수 5>

Q. 두 문제 모두 재귀함수로도 풀 수 있는 문제.

 

🧭<BOJ B2 25501 재귀의 귀재>

Q. 재귀함수 내부에 return 종료 조건 2개 + return문에 내부 재귀함수 호출