Recursive function

Recursive function (1).pptx

Recursion : the act of a function invoking itself

목표 

1. Recursive한 생각을 이해한다.

2. 순열에 관련된 문제들을 재귀적인 방법으로 구현한다.

3. slimp & slump 문제를 재귀적 방법으로 구현하고 더 낳은 방법에 대해서 고민한다.

문제 1. Indexing & Recursive

1.1 배열을 다루는 방법

1. 임시 저장소를 두고 SWAP하는 방법

2. 인덱스를 활용하는 방법

public class RecursiveSelectionSort {
  public static void sort(double[] list) {
    sort(list, 0, list.length - 1); // Sort the entire list
  }
 
  private static void sort(double[] list, int low, int high) {
    if (low < high) {
      // Find the smallest number and its index in list(low .. high)
      int indexOfMin = low;
      double min = list[low];
      for (int i = low + 1; i <= high; i++) {
        if (list[i] < min) {
          min = list[i];
          indexOfMin = i;
        }
      }
 
      // Swap the smallest in list(low .. high) with list(low)
      list[indexOfMin] = list[low];
      list[low] = min;
 
      // Sort the remaining list(low+1 .. high)
      sort(list, low + 1, high);
    }
  }
 
  public static void main(String[] args) {
    double[] list = {2, 1, 3, 1, 2, 5, 2, -1, 0};
    sort(list);
    for (int i = 0; i < list.length; i++)
      System.out.print(list[i] + " ");
  }
}

->저는 이러한 경우 대부분 임시 저장소를 두고 구현하기에, 챙겨두어야 하는 방법이라 생각되어 정리합니다.

문제 2. Project euler 24번 - 사전식 순열

 

구현 1. 기존 작성 방식

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n-1)
 
List = []
digit = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
result = ''
 
for i in range(1, 11):
    List.append(factorial(i))
    print List[i-1]
 
 
target = 1000000
 
for i in range(8, -1, -1):
    cnt = 0
    while target > List[i]:
        target -= List[i]
        cnt +=1
    result += digit[cnt]
    del digit[cnt]
    print target
    
print result + digit[0]

C:\Users\soicem's com\Desktop>python test.py

1

2

6

24

120

720

5040

40320

362880

3628800

274240

32320

2080

640

40

16

4

2

1

2783915460

구현 2. 재귀적 방식

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n-1)
 
def dictionaryPerm(n, target, digit, List):
    if n<0: # List[0] is second number
        return digit[0]
    else:
        cnt = 0
        while target > List[n]:
            target -= List[n]
            cnt +=1
        s = digit[cnt]
        del digit[cnt]
        return s + dictionaryPerm(n-1, target, digit, List)
 
List = []
digit = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
result = ''
target = 1000000
 
for i in range(1, 11):
    #print factorial(i)
    List.append(factorial(i))
 
print dictionaryPerm(8, target, digit, List)

C:\Users\soicem's com\Desktop>python test.py

2783915460

-> 어떻게 구현할지 설계한 후 파이썬으로 비재귀적 방식과 이를 재귀적으로 바꿔서 구현해봤습니다.

문제 3. Slimp & Slump 구현하기

구현. slimp & slump

public class slimp {
 
    public static boolean slimp(String s) {
        if (s.length() == 2 && s.charAt(0) == 'A' && s.charAt(1) == 'H') {
            return true;
        } else if (s.charAt(0) == 'A' && s.charAt(1) == 'B' && s.charAt(s.length() - 1) == 'C') {
            if (s.length() <= 3) {
                return false;
            } else {
                return slimp(s.substring(2, s.length() - 1));
            }
        } else if(s.charAt(0) == 'A' && (s.charAt(1) == 'D' || s.charAt(1) == 'E') && s.charAt(s.length() - 1) == 'C'){
            int i = 2;
           //System.out.println(s.substring(1, s.length()-1));
            return slump(s.substring(1, s.length()-1));
        } else {
            return false;
        }
    }
 
    public static boolean slump(String s) {
        int i = 1;
        if ((s.charAt(0) == 'D' || s.charAt(0) == 'E') && s.charAt(1) == 'F') {
            while (i< s.length()) {
                if(s.charAt(i) == 'F'){i++;}
                else break;
            }
            
            if (s.charAt(i) == 'G' && s.charAt(s.length()-1) == 'G')  {
                return true;
            } else if (s.charAt(i) == 'D' || s.charAt(i) == 'E') {
                //System.out.println(s.substring(i, s.length()));
                
                return slump(s.substring(i, s.length()));
            }
        }
        return false;
    }
    
    public static boolean slurpy(String s){
        String slimp;
        String slump;
         
        for(int i=0; i<s.length(); i++){
            //System.out.println(s.charAt(i));
            if(s.charAt(0)=='A' && (s.charAt(i) == 'C' || s.charAt(i) == 'H') && (s.charAt(i+1) == 'D' || s.charAt(i+1) == 'E')) {
                i += 1;
                slimp = s.substring(0, i);
                System.out.println("slimp is " + slimp);
                slump = s.substring(i, s.length());
                System.out.println("slump is " +slump);
               
                if(slump(slump) && slimp(slimp)){
                    return true;
                } else {
                    return false;
                }  
            }
        }
        
        return false;
    }
 
    public static void main(String[] args) {
        String myStr;
        myStr = "ABAHC";
        String myStr2;
        myStr2 = "DFEFFFFFG";
        String myStr3;
        myStr3 = "ABAEFGCCDFEFFFFFFG";
        /*System.out.println(myStr + '\n' + slimp(myStr));
        System.out.println(myStr2 + '\n' + slump(myStr2));*/
        System.out.println(myStr3 + '\n' + slurpy(myStr3));
    }
}

-testcase 

AHDFG

ADFGCDFFFFFG

ABAEFGCCDFEFFFFFFG

-> slimp & slump를 구현한 후 slurpy로 받는 문자열을 slimp와 slump로 적절히 나눠주고 두 문자열이 slimp & slump인지 판별하여 둘 다 참이 나올 경우 slurpy로 판별하였습니다.