재귀함수를 이용한 최대/최소값 구하기

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
 
public class Temp {
    public static void main(String[] args) {
        List<BigInteger> list = new ArrayList<BigInteger>(0);
        
        for(int i = 1; i <= 10; list.add(BigInteger.valueOf(i++)));
        
        System.out.println(max(list.subList(1, list.size()), list.get(0)));
    }
    
    public static BigInteger max(List<BigInteger> list, BigInteger val) {
        BigInteger retVal = (list.size() > 1) ? max(list.subList(1, list.size()), list.get(0))
                                              : list.get(0);
        
        return (val.compareTo(retVal) > 0) ? val : retVal;    
    }
}

 

https://t0pli.tistory.com/147 생각하다가 최대값도 되지 않나 싶어서 만들어봤다.

여기서는 10개 수 중에서 최대값을 구했지만 1000000개의 수 중에서 최대값을 구하려면 StackOverflowException이 발생한다. 재귀호출의 약점이기도 한데, JVM Stack에 max 메소드가 백만 개 가량 쌓이니 어찌 보면 당연한 일이다. 그래도 10000개 정도까지는 되는 것 같다..

18행에서 부등호 방향만 바꾸면 최소값을 구하는 메소드가 된다.

 

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
 
public class Temp {
    public static void main(String[] args) {
        List<BigInteger> list = new ArrayList<BigInteger>(0);
        
        long beginTime;
        long estimatedTime;
        
        for(int i = 1; i <= 1000; list.add(BigInteger.valueOf(i++)));
        
        beginTime = System.nanoTime();
        max1(list.subList(1, list.size()), list.get(0));
        estimatedTime = System.nanoTime() - beginTime;
        System.out.println("max1(): " + estimatedTime + "ns");
        
        beginTime = System.nanoTime();
        max2(list);
        estimatedTime = System.nanoTime() - beginTime;
        System.out.println("max2(): " + estimatedTime + "ns");
    }
    
    public static BigInteger max1(List<BigInteger> list, BigInteger val) {
        BigInteger retVal = (list.size() > 1) ? max1(list.subList(1, list.size()), list.get(0))
                                              : list.get(0);
        
        return (val.compareTo(retVal) > 0) ? val : retVal;    
    }
    
    public static BigInteger max2(List<BigInteger> list) {
        BigInteger max = list.get(0);
        for(int i = 1; i < list.size(); i++) {
            if(list.get(i).compareTo(max) > 0) {
                max = list.get(i);
            }
        }
        
        return max;
    }
}

$max1$ 메소드는 재귀호출 방식이고, $max2$ 메소드는 리스트 쭉 훑으면서 비교하는 방식이다.

리스트의 크기를 $1000$으로 설정해서 실행하면

시간도 느리고 공간도 많이 먹는다.

아마 매 호출 마다 $subList$ 메소드를 호출해서 그런 것 같다.

 

근데 생각해보니까 꼭 sub list를 만들지 않고 index로만 제어해도 될 듯 했다.

package temp;
 
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
 
public class Temp {
    public static void main(String[] args) {
        List<BigInteger> list = new ArrayList<BigInteger>(0);
        long beginTime;
        long estimatedTime;
 
        for(int i = 1; i <= 1000; list.add(BigInteger.valueOf(i++)));
        
        beginTime = System.nanoTime();
        max1(list, list.size() - 1);
        estimatedTime = System.nanoTime() - beginTime;
        System.out.println("max1(): " + estimatedTime + "ns");
        
        beginTime = System.nanoTime();
        max2(list);
        estimatedTime = System.nanoTime() - beginTime;
        System.out.println("max2(): " + estimatedTime + "ns");
    }
    
    public static BigInteger max1(List<BigInteger> list, int n) {
        if(n == 1) {
            return (list.get(0).compareTo(list.get(n)) > 0) ? list.get(0) : list.get(n);
        } else {
            BigInteger max = max1(list, n - 1);
            return (list.get(n).compareTo(max) > 0) ? list.get(n) : max; 
        }
    }
    
    public static BigInteger max2(List<BigInteger> list) {
        BigInteger max = list.get(0);
        for(int i = 1; i < list.size(); i++) {
            if(list.get(i).compareTo(max) > 0) {
                max = list.get(i);
            }
        }
        
        return max;
    }
}

이번에는 재귀가 더 빠르길 기대했는데 비교하는 게 더 빠르다. 그래도 많이 따라잡은 듯

근데 이럴 거면 왜 고민한 거지??