재귀호출 Recursive call

재귀호출

재귀함수는 하위작업을 수행하도록 자기 자신을 호출하여 작업을 수행한다. 어느 단계에 이러러서는, 자기 자신을 호출하지 않고도 수행할 수 있는 기본 단위를 수행합니다. 함수가 자기 자신을 호출해서 하위 작업을 수행하는 것을 재귀 경우라고 합니다. 모든 재귀 함수는 아래의 형식으로 쓰여질 수 있다.

if (기본 경우인지 확인)

return 기본 값

else if (또 다른 기본경우인지 확인)

return 또 다른 기본 값

else

(어떤 작업)

return (재귀호출)

재귀호출 될때마다 메서드의 복사본(실제로는 변수만)이 메모리에 만들어지고 메서드가 종료될때 복사본이 메모리에서 삭제된다. 

재귀와 반복 비교

재귀

1. 기본 경우에 도달하면 종료한다.

2. 각 재귀 호출은 스택에 공간을 필요로 한다.

3. 무한루프에 들어가면 메모리 용량을 초과해서 스택 오버플로우가 발생한다.

4. 어떤 문제의 답은 재귀적인 수식으로 만들기 쉽다.

반복

1. 조건이 거짓일 때 종료한다.

2. 각 반복이 별도 공간을 필요로 하지 않는다.

3. 무한 루프는 추가 메모리가 필요하지 않아 무한히 반복한다.

4. 반복 해법은 재귀 해법에 비해 간단하지 않을 때가 있다.

재귀 참고사항

재귀적 알고리즘에는 2가지, 재귀적 경우와 기본경우가 있다.

모든 재귀함수는 기본경우에 종료해야한다.

일반적으로 반복해법이 재귀해법보다 효율적이다. 반복은 추가 메모리를 필요로하지 않는다.

재귀적으로 풀 수 있는 문제는 반복적으로 풀 수도 있다.

어떤 문제들의 경우엔 눈에 띄는 반복적 알고리즘이 없을 수도 있다.

어떤 문제는 재귀적 해법이 최적이고, 어떤 문제는 그렇지 않다.

재귀알고리즘 예

피보나치 수열, 팩토리얼 구하기, 병합 정렬, 퀵 정렬, 이진 검색, 트리탐색, 중위, 전위, 후위 등 트리문제, 그래프 탐색, 깊이우선탐색(DFS), 너비우선탐색(BFS)

백트래킹

분할 정복을 이용한 완전검색 기법이다.

백트래킹 알고리즘 예

이진문자열, k-ary문자열 만들기, 배낭채우기, 문자열 일반화, 해밀턴 사이클, 그래픽 색칠

문제 : n 비트의 모든 문자열을 생성하라.

import java.io.*;

public class Binary {

static int[] A;

static void binary(int n){

if(n<1){

for(int i:A)

System.out.print(i);

System.out.println();

}

else{

A[n-1] = 0;

binary(n-1);

A[n-1] = 1;

binary(n-1);

}

}

public static void main(String[] args) throws Exception{

int N;

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

N = Integer.parseInt(br.readLine());

A = new int[N];

binary(N);

}

}

입력 / 출력

3

000

100

010

110

001

101

011

111

문제 : 0..k-1 사이에서 고른 길이가 n인 모든 문자열을 생성하라

import java.io.*;

import java.util.*;

public class Recursive {

static int N,K;

static int[] A;

public static void rec(int n,int k){

if(n<1){

for(int i:A)

System.out.print(i);

System.out.println();

}

else{

for(int j=0;j<k;j++){

A[n-1] = j;

rec(n-1,k);

}

}

}

public static void main(String[] args) throws Exception{

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

StringTokenizer st = new StringTokenizer(br.readLine());

N = Integer.parseInt(st.nextToken());

K = Integer.parseInt(st.nextToken());

A = new int[N];

rec(N,K);

}

}

입력 / 출력

3 3

000

100

200

010

110

210

020

120

220

001

101

201

011

111

211

021

121

221

002

102

202

012

112

212

022

122

222