순환(recursion)

순환 Recursion

자기자신을 호출

무한루프에 빠진다

적절한 구조를 갖추고 있다면 항상 무한루프에 빠지는 것은 아님.

적절한 구조란?

->base case:적어도 하나의 리커전으로 빠지지 않고 종료되는 경우가 존재해야한다.

->recursive case:recursion을 반복하다보면 결국 base case로 수렴해야한다.

ex) 피보나치,팩토리얼,최대공약수,X^n

수학함수뿐 아니라 다른 많은 문제들을 recursion으로 해결할 수 있다.

ex)문자열의 길이 계산

public static int length(String str){

if(str.equals(""))

return 0;

else

return 1+length(str.substring(1));

}

ex)문자열의 프린트

public static void printChars(String str){

if(str.length()==0)

return;

else{

System.out.print(str.charAt(0));

printChars(str.substring(1));

}

}

ex)문자열을 뒤집어 프린트

public static void printCharsReverse(String str){

if(str.length()==0)

return;

else{

printCharReverse(str.substring(1));

System.out.print(str.charAt(0));

}

}

ex)2진수로 변환하여 출력

public void printInBinary(int n){

if(n<2)

System.out.print(n);

else{

printInBinary(n/2);

System.out.print(n%2);

}

}

ex)배열의 합 구하기

public static int sum(int n, int [] data){

if(n<=0)

return 0;

else

return sum(n-1,data)+data[n-1];

}

ex)데이터파일로부터 n개의 정수 읽어오기

public void readFrom(int n, int[] data, Scanner in){

if(n==0)

return;

else{

readFrom(n-1,data,in);

data[n-1] = in.nextInt();

}

}

Recursion vs Iteration

모든 순환함수는 반복문으로 변경 가능, 그 역도 성립

순환함수는 단순하고 알기쉽게 표현하는 것 가능

하지만 함수호출에 따른 오버해드가있음

Designing Recursion

적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야함

모든 case는 결국 base case로 수렴해야 함

암시적(implicit) 매개변수를 명시적(explicit)매개변수로 바꿔라.

ex)순차탐색

int search(int [] data, int n, int target){

for

}

매개변수의 명시화

ex)

int search(int [] data, int begin, int end, int target){

if(begin>end)

return -1;

else if (target==data[begin])

return begin;

else

return search(data,begin+1,end,target);

}

이 함수를 search(data,0,n-1,target)으로 호출한다면 앞에 페이지의 함수와 동일한 일을 한다.

ex)

int search(int [] data, int begin, int end, int target){

if(begin>end)

return -1;

else if (target==data[end])

return end;

else

return search(data,begin,end-1,target);

}

ex)

int search(int [] data, int begin, int end, int target){

if(begin>end)

return -1;

else{

int middle = (begin+end)/2;

if(data[middle] == target)

return middle;

int index = search(data,begin,middle-1,target);

if(index!=-1)

return index;

else

return search(data,middle+1,end,target);

}

}

ex)최대값 찾기

int findMax(int [] data, int begin, int end){

if(begin==end)

return data[begin];

else

return Math.max(data[begin], findMax(data,begin+1,end));

}

ex)

int findMax(int [] data, int begin, int end){

if(begin==end)

return data[begin];

else{

int middle = (begin+end)/2;

int max1 = findMax(data,begin,middle);

int max2 = findMax(data,middle+1,end);

return Math.max(max1,max2);

}

}

ex)이진검색 binary search

public static int binarySearch(string[] items, String target, int begin, int end){

if(begin>end)

return -1;

else{

int middle = (begin+end)/2;

int comResult = target.compareTo(items[middle]);

if(comResult == 0)

return middle;

else if(comResult<0)

return binarySearch(items, target, begin, middle-1);

else

return binarySearch(items,target,middle+1, end);

}

}

미로찾기

Rcursive Thinking

현재 위치에서 출구까지 가는 경로가 있으려면

1) 현재 위치가 출구이거나 혹은

2) 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나

미로찾기(Decision problem)

Decision problem이란 답이 yes or no인 문제

boolean findPath(x,y)

if (x,y) is the exit

return true;

else

mark(x,y) as a visited cell; //무한루프방지하기위해 방문한거 표시

for each neighbouring cell(x',y') of (x,y) do

if(x',y') is on the pathway and not visited

if findPath(x',y')

return true;

return false;

boolean findPath(x,y)

if (x,y) is either on the wall or a visited cell

return false;

else if(x,y) is the exit

return true;

else

mark(x,y) as a visited wall;

for each neighbouring cell(x',y') of (x,y) do

if findPath(x',y')

return true;

return false;

public class Maze{

private static int N=8;

private static int [][] maze = {

{0,0,0,0,0,0,0,1},

{0,1,1,0,1,1,0,1},

{0,0,0,1,0,0,0,1}.

{0,1,0,0,1,1,0,0},

{0,1,1,1,0,0,1,1},

{0,1,0,0,0,1,0,1},

{0,1,1,1,0,1,0,0}

};

private static final int PATHWAY_COLOR = 0;

private static final int WALL_COLOR = 1;

private static final int BLOCKED_COLOR = 2;

private static final int PATH_COLOR = 3;

}

public static boolean findMazePath(int x, int y){

if(x<0 || y<0 || x>=N || y>=N)

return false;

else if(maze[x][y] != PATHWAY_COLOR)

return fasle;

else if(x==N-1 && y==N-1){

maze[x][y] = PATH_COLOR;

return true

}

else{

maze[x][y] = PATH_COLOR;

if(findMazePath(x-1,y) || findMazePath(x,y+1) || findMazePath(x+1,y) || findMazePaht(x,y-1)){

return true;

}

maze[x][y] = BLOCKED_COLOR;

return fasle;

}

}

public static void main(String [] args){

printMaze();

findMazePath(0,0);

printMaze();

}

상태공간트리란? 찾는 해를 포함하는 트리.

즉 해가 존재한다면 그것은 반드시 이 트리의 어떤 한노드에 해당함

따라서 이 트리를 체계적으로 탐색하면 해를 구할 수 있음.

* 상태공간 트리의 모든 노드를 탐색해야 하는 것은 아님

백트래킹에 이용하는 것은 recursion or stack but 대부분 recursion이 쉽고 간편

백트래킹 recursion의 기본 구조

return-type name(arguments) //매개변수는 내가 현재 트리의 어떤 노드에 있는지

{

if non-promising //꽝

report failure and return;

else if success

report answer and return;

else

visit children recursively;

}