[알고리즘] 재귀함수(Recursive function) 정리 & 문제 풀이(Python)
재귀함수
: 함수 안에서 자신의 함수를 다시 호출하는 방식
- 재귀, 즉 자기호출은 어떤 문제를 해결하는 과정에서 자신과 똑같지만 크기가 다른 문제를 발견하고 이들의 관계를 파악함으로써 문제 해결에 접근하는 방식이다.
재귀함수의 장점
- 반복문을 대신해서 재귀함수로 사용하게 되면 보다 간결한 코드 작성이 가능해진다.
재귀함수의 단점
- 연산이 느리다.(많은 연산을 필요로 한다는 얘기)
- 재귀함수의 단점으로 인해 현재 실무에서는 거의 사용하지 않는다고 함.
- 재귀함수 단점 보안으로 동적프로그래밍 사용
def recursive():
print("재귀함수")
recursive()
recursive() # 함수 호출재귀함수를 사용할 때 가장 중요하게 봐야하는 것은 "탈출조건"이다. 위 코드와 같이 탈출조건(종료 조건)이 존재하지 않는다면, 함수가 무한 호출되어 StackOverflow(스택 오버플로)가 발생한다.
메모리 공간
참고) https://blog.naver.com/zzaxowns/222611286857
운영체제는 사용자의 편의성과 메모리 관리를 중요시한다. 운영체제의 역할 중 하나가 메모리 관리이다. 프로세스가 실행될 때 운영체제에서 메모리 공간을 할당해준다.
Heap garbage collector 를 언제 호출시켜서 할당되는 걸..
기본적으로 함수를 호출하는 형식의 메모리는 Stack이라는 부분에 쌓이게 되는데, 프로세스가 할당받는 Stack의 크기는 무한이 아니다. 따라서 어느순간부터 스택공간이 넘쳐버리면 Stack Overflow가 발생하게 된다.
아래 그림과 같이 함수가 지속적으로 자신을 호출하게 되면 언젠가는 Stack 메모리 공간의 한계까지 올 것이며 이 한계를 넘어버리는 순간 문제가 발생한다. 그러므로 재귀함수를 사용할 때에는 반드시 탈출조건의 여부를 확인해야한다.
대표적인 문제 및 사용
- 팩토리얼
- 피보나치 수열
- X^n
- 문자열 길이 계산, 거꾸로 출력
- DFS(깊이우선탐색)
- 10진수 수를 2진수로 변환하는 형식의 출력
(팩토리얼, 피보나치 제외하고 금시초문 느낌이지만 공부하다가 발견하면 재밌을거같다..)
[백준] 10872 : 팩토리얼
문제링크 https://www.acmicpc.net/problem/10872
팩토리얼(Factorial)은 !를 기호로 사용해 특정 n부터 1까지를 곱한 값을 구할 때 사용된다.
ex) 5! = 5 4 3 2 1 = 120
팩토리얼 함수는 반복문과 재귀함수 모두로 구할 수 있다.
문제는 0부터 12까지 N을 입력받아 N!을 출력하는 문제이다.
# 문제: 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.
# 입력: 첫째 줄에 정수 N(0<= N <= 12)이 주어진다.
# 출력: 첫째 줄에 N!을 출력한다.
# 예시) 5! = 5 4 3 2 1 = 120
def factorial(n):
if(n <=1):
return n # 0! = 1, 1! = 1
return n * factorial(n-1)
n = int(input())
print(factorial(n))함수가 무한히 호출되어 StackOverflow가 발생하지 않기 위해선 탈출조건을 확인해야한다. 위 코드에서는 n <= 1 이면 0 혹은 1을 리턴하고 아닌 경우 n * factorial(n-1)을 리턴한다.
[백준] 10870 피보나치 수 5
문제링크 https://www.acmicpc.net/problem/10870
피보나치 수는 0과 1로 시작한다. 0의 피보나치 수는 0이고, 1의 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.
이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. 피보나치 수열은 앞의 두 개의 값을 더한 값이 다음 값이 되는 형식의 수열이다.
n=17일때 까지 피보나치 수를 써보면 다음과 같다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
문제는 0~20에서 n이 주어졌을 때, n번째 피보나치 수를 구하는 문제이다.
# 0 1 1 2 3 5 8 13 21 ....
# 피보나치는 0번째는 0, 1번째는 1, 그 다음 2번째부터 바로 앞 피보나치 수의 합이 된다.
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-2)+fibonacci(n-1)
# 즉, fibonacci(2)일 때 fibonacci(0)+fibonacchi(1)=0+1=1 이 리턴된다.
n = int(input())
print(fibonacci(n))피보나치에서도 마찬가지로 탈출조건을 줘야한다. 여기서 탈출조건은 n이 0 혹은 1인 경우, return 값으로 n을 반환시켜, 초기값을 세팅한다. 만약 0과 1일 아닐 경우 그 수를 쪼개서 return fibonacci(n-1) + fibonacci(n-2) 를 호출해주면 나중에 0 혹은 1이 됐을 때부터 함수가 호출되지 않고 반환값을 받아 내려오면서 n의 피보나치 수가 된다.
[도움을 주신 블로그들 :) ]
https://velog.io/@wkahd01/%EC%9E%AC%EA%B7%80-%ED%95%A8%EC%88%98
https://blog.naver.com/zzaxowns/222611286857
https://blog.naver.com/zzaxowns/222612156582