재귀함수 반복문 변환 - jaegwihamsu banbogmun byeonhwan

Question

이미지 출처: 코딩도장

알고리즘은 효율적인 패턴을 찾아내어 문제를 해결하는데 도움을 준다.

목차 Show

재귀호출이란?
반복문을 재귀호출 이용하도록 바꿔보자!
재귀호출 문제 풀이

앞으로 그 알고리즘을 하나하나 배우면서 문제를 풀어나가려고 한다.

첫번째로 재귀호출에 대해서 공부해보았다.

알고리즘 문제를 풀 때, 복잡한 수식을 생각하기전에 단순하게 모든 경우의 수를 계산해보는 방법이 있다.

이를 완전탐색이라고하는데, 이 때 재귀함수를 사용하면 간단하게 해결할 수 있다.

재귀호출이란?

자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수

반복문을 재귀호출 이용하도록 바꿔보자!

문제) 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_num

2) 재귀호출 사용

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 False

1) 작은단위 어떻게 쪼개서 일할지 정의하기

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

public static void main(String[] args) {
    int N = 11; // 10진수

    String s = solutionByIterator(N);
    System.out.println("solutionByIterator : " + s);

    String result = "";
    result = solutionByDFS(N, result);
    System.out.println("solutionByDFS : " + result);
}


private static String solutionByIterator(int n) {
    StringBuilder sb = new StringBuilder();
    boolean isEnd = false;

    int temp = n;
    while(!isEnd){
        sb.insert(0, temp % 2); // 2진수로 변환, 맨 앞에 값을 입력하여 기존 값을 한칸씩 뒤로 미룬다.
        temp = temp / 2;    // 다음 계산에선 몫을 사용한다.

        if(temp == 0){
            isEnd = true;
        }
    }

    return sb.toString();
}

private static String solutionByDFS(int n, String result){
    if(n == 0){
        return result;
    }

    return solutionByDFS(n/2, String.valueOf(n % 2) + result);
}

재귀함수 장점 : 직관적인 알고리즘 설계가 가능

재귀함수 단점 : 함수 호출 오버헤드 (Context Switch) -> 시간 성능 저하, 자신을 다시 호출하면서 생성되는 변수 때문에 메모리 문제가 생길 수 있음. (출처 : http://bitly.kr/DNHtU3http://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
}

참고 출처 : http://wiki.gurubee.net/pages/viewpage.action?pageId=1507916

1. 재귀 호출이 하나인 경우 : 순환문으로 변환하면 됨. (위에 소스 참고)

2. 재귀 호출이 둘인 경우 : (이진트리)

주의점 : 비재귀함수가 항상 재귀함수보다 빠른건 아니다. (예외 케이스 찾아봐야 함)

예제) 이진트리(Binary Tree)의 순회를 재귀(recusive)방식에서 반복(iterative)방식으로 구현하기