if-else语句中的递归调用

Question

我无法弄清楚为什么我的程序在条件语句中包含时会递归调用它自己.我正在进行一项演示快速选择的作业,这是一种快速排序的变体,可以让你找到第k个最小元素.我不想太冗长所以我发布了问题代码希望我的解释可以给你一个我的目标的图片.

在下面的代码块中,k是我想要找到的第k个元素.l是左边的下边界,所有数字都小于枢轴.如果k落在下边界和下边界之间,我们的想法是搜索这一边l.

    if (k-1<l) {
        System.out.println("call quickSelect from " + begin + " to " + l);
        if (l-1==begin) 
            {return begin;} //added to prevent random from throwing error
        else {                  
            depth++;
            return quickSelect(arr,k,begin,l-1);            }
    }

当我以quickSelect递归方式调用时出现问题l-1==begin.我得到错误,Exception in thread "main" java.lang.IllegalArgumentException: bound must be positive 因为我使用Java的随机对象(我用来在边界内找到一个数据透视图)只能采用正整数.所以这就是我添加条件语句l-1==begin以防止在无效参数中调用quickSelect()的原因.但是,我得到了相同的错误!我很惊讶这是因为我认为if-else语句会处理这个异常.我真的很感激有关如何调用quickSelect的任何想法l-1==begin.我已经为下面的程序包含了整个代码以获取更多详细信息,递归调用是针对底部的.

import java.util.Scanner;
import java.io.FileNotFoundException;
import java.io.File;
import java.util.ArrayList;
import java.util.Random;
import java.util.Collections;

public class quickSelect{ 
    static int depth=0;
    public static void main(String args[]) {
        int totalDepth=0;
        ArrayList<Integer>al = new ArrayList();             
        Scanner doc = new Scanner("");
//      String smallFile = "proj2small.txt";
        String smallFile = "proj2big.txt";

        try {
            File openSmallFile=new File(smallFile);
            doc = new Scanner(openSmallFile);
        } catch (FileNotFoundException e1 ) {
            e1.printStackTrace();
        }
        while (doc.hasNext()) {
            int f = doc.nextInt();
            al.add(f);
        }
        int k=al.size()/2;
            depth=0;
            int p = quickSelect(al,k,0,al.size()-1);
            System.out.println(k + "th element is " + p);
            System.out.println(depth + " recursive calls ");
        }       

    public static int quickSelect(ArrayList<Integer>arr,int k,int begin,int end) {
        Random rand = new Random();
        int range = end-begin;
        int j = rand.nextInt(range);
        //int equals=0;
        int pivot = arr.get(j+begin);
        System.out.println("pivot is " + pivot + " at index " + (j+begin));
        int h=end-1;
        int l=begin;
        arr.remove(j+begin);//remove the pivot. Assume no duplicates are allowed
        if (j+begin<k) {
            k--; //shift k left one if index of pivot comes before it because we removed pivot
        }
        while (true) {
            while (arr.get(l)<pivot) {
                l++;
            }
            while(arr.get(h)>pivot) {
                h--;
            }
            if(l>=h) {
                break;
            }
            Collections.swap(arr, l, h);
            l++;
            h--;

        }
        //l is equal to the pivot? 
        //System.out.println("l is " + ((arr.get(l)==pivot)?"equal":"not equal") + " to the pivot");
        System.out.println("k is " + k);

        if (k-1<l) { //l-1 because left shift one after removal
            System.out.println("call quickSelect from " + begin + " to " + l);
            if (l-1==begin) 
            {return begin;} //added to prevent random from throwing error
            else {                  
                            depth++;
                return quickSelect(arr,k,begin,l-1); //array gets smaller k becomes smaller
            }
        }
        else if (k-1==l) {
            return pivot;
        }
        else {
            System.out.println("call quickSelect from " + l + " to " + end);
            if (end-1==l) 
            {return l;} //added to prevent random from throwing error
            else {
                return quickSelect(arr,k,l,end-1); //we removed the pivot so l is part of the high range
            }
        }   
    }
}

抱歉有趣的代码格式.从日食中剔除并不是一个好主意

Answer 1

如果您的文件包含零或仅包含一个值,则al.size()的值将为0或1.

因此,k无论哪种方式都是0,因为0/2和1/2都等于0.

因此,当传递al.size()-1作为end用于该方法中,在的非常第一次运行quickSelect(),它通过0-1其是,当然,-1.

当你打电话时nextInt(0, -1),IllegalArgumentException会抛出一个,给你错误.