알고리즘은 효율적인 패턴을 찾아내어 문제를 해결하는데 도움을 준다.
앞으로 그 알고리즘을 하나하나 배우면서 문제를 풀어나가려고 한다.
첫번째로 재귀호출에 대해서 공부해보았다.
알고리즘 문제를 풀 때, 복잡한 수식을 생각하기전에 단순하게 모든 경우의 수를 계산해보는 방법이 있다.
이를 완전탐색이라고하는데, 이 때 재귀함수를 사용하면 간단하게 해결할 수 있다.
재귀호출이란?
자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수
반복문을 재귀호출 이용하도록 바꿔보자!
문제) 1~N까지의 수를 더해주는 함수
ex) numbers=5 -> 1+2+3+4+5
1) 반복문 사용
def is_sum(N): sum_num = 0 for i in range(1,N+1): sum_num += i return sum_num2) 재귀호출 사용
def is_sum(N): if N == 1: return 1 return N + is_sum(N-1)리턴에서 함수를 다시 호출하는데, N은 이번에 처리하고 다음 작업을 넘겨준다 (N-1)
중요한건, 언제 멈출지를 꼭 정해줘야하는것!
for 문에서 언제 멈출지를 정해주는것처럼, 재귀호출 사용할 때도 언제까지 불러줄지 꼭 써주어야한다.
위 코드에서는 N이 1일때 또 재귀함수를 호출하면 is_sum(0)을 호출하고, 그 다음에는 is_sum(-1)를 호출하기 때문에,
if N==1: return 1 이라는 조건을 추가해서 재귀호출을 멈춰준다.
재귀호출 문제 풀이
문제 출처 -코딩도장
파이썬 코딩 도장: 31.4 연습문제: 재귀호출로 회문 판별하기
다음 소스 코드를 완성하여 문자열이 회문인지 판별하고 결과를 True, False로 출력되게 만드세요. 여기서는 재귀호출을 사용해야 합니다. practice_recursive_function_palindrome.py def is_palindrome(word): �
dojang.io
문제설명
재귀호출을 사용해서 회문을 판별하자.
ex) 'level' > True, 'discribe' > False, 'Tenet' > True
def is_palindrome(word): if len(word) < 2: return True if word[0] == word[-1]: return True * is_palindrome(word[1:-1]) else: return False1) 작은단위 어떻게 쪼개서 일할지 정의하기
2) 언제 재귀호출 멈출지 정해주기
위의 순서로 문제를 풀었다.
먼저, 문자열의 맨 앞과 맨 뒤의 글자를 비교하는 작업을 수행하고
다음 호출문에서 2번째 글자와 맨 뒤에서 2번째 글자를 비교하는 작업을 수행한다.
그러다가 비교해야할 글자가 없을 때 함수호출을 멈추어준다!
알아야 할 개념
1) 논리연산
True * True = True
True * False = False
False * False = False
2) 문자열 슬라이싱
t = 'abcdefg'
t[0] = 'a'
t[-1] = 'g'
t[1:-1] ='bcdef'
t[>=:<] -> 앞에 오는 인덱스는 포함하고, 뒤에 오는 인덱스는 포함하지 않음
10진수 N이 입력되면 2진수로 변환하여 출력하는 프로그램을 작성하세요.
단 재귀함수를 이용 해서 출력해야 합니다.
▣ 입력설명
첫 번째 줄에 10진수 N(1<=N<=1,000)이 주어집니다.
▣ 출력설명
첫 번째 줄에 이진수를 출력하세요.
▣ 입력예제 1
11
▣ 출력예제 1
1011
재귀함수 장점 : 직관적인 알고리즘 설계가 가능
재귀함수 단점 : 함수 호출 오버헤드 (Context Switch) -> 시간 성능 저하, 자신을 다시 호출하면서 생성되는 변수 때문에 메모리 문제가 생길 수 있음. (출처 : //bitly.kr/DNHtU3//bitly.kr/DNHtU3)
-최적화 단계에서 비재귀 함수로 변환해야 함.-
1. 재귀함수와 비재귀 함수의 성능 차이
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <time.h> using namespace std; //재귀함수 long long recursiveFactorial(int n) { if (n < 1) { return 1; } else { return n * recursiveFactorial(n - 1); } } //비재귀함수 long long nonRecursiveFactorial(int n) { long long f = 1; while (n > 0) { f = f * n--; } return f; } int main() { time_t start, end; double result; start = clock(); //시간 측정 시작 cout << "Recur: "<<recursiveFactorial(20) << endl; //2432902008176640000 end = clock(); //시간 측정 끝 result = (double)(end - start); cout << "Time:" << result << endl; //3 start = clock(); //시간 측정 시작 cout << "Non: "<<nonRecursiveFactorial(20) << endl;//2432902008176640000 end = clock(); //시간 측정 끝 result = (double)(end - start); cout << "Time" << result << endl; //1 }참고 출처 : //wiki.gurubee.net/pages/viewpage.action?pageId=1507916
1. 재귀 호출이 하나인 경우 : 순환문으로 변환하면 됨. (위에 소스 참고)
2. 재귀 호출이 둘인 경우 : (이진트리)
주의점 : 비재귀함수가 항상 재귀함수보다 빠른건 아니다. (예외 케이스 찾아봐야 함)
예제) 이진트리(Binary Tree)의 순회를 재귀(recusive)방식에서 반복(iterative)방식으로 구현하기