How recursion works

Question

static void sort(int array[])
{
    //int array[]={20,40,30,60,70,80,50,90};
    if(array.length==1)
        return;

    int mid=array.length / 2;
    int part1[]=new int[mid];
    int part2[]=new int[array.length-mid];

    for(int i=0; i<array.length; i++)
    {
        if(i<mid)
        {
            part1[i]=array[i];
        }
        else
        {
            part2[i-mid]=array[i];
        }
    }

    sort(part1);
    sort(part2);

    merge(part1,part2,array);
    //for(int x=0; x<part1.length; x++)
        //System.out.print(part1[x]+" ");

    //for(int x=0; x<part2.length; x++)
        //System.out.print(part2[x]+" ");

}

i know recursion is method(function) that call it self. im confused in this code why that program stop, when the sort() method execute and call itself sort(part1)method then the sort(part1) is executed again and again and how sort(part2) and merge(part1,part2,array) is executed, why this code is not infinite and how the program stop. sorry im new in java

`if(array.length==1) return;` is what makes your code stop. Have you tried looking up other questions about recursion here on StackOveflow? — lucian.pantelimon, Mar 13 '14 at 07:42
Try looking up the question at the end of this comment as it has more detailed explanations on the topic, which will help you understand recursion better. Your code is similar to jkohlhepp's answer, which is easier to follow. http://stackoverflow.com/questions/3021/what-is-recursion-and-when-should-i-use-it — lucian.pantelimon, Mar 13 '14 at 07:49
@Coeur A question about recursion doesn't need 'disambiguation from other languages'. The answer is the same for all. This 5.75-year-old post didn't need any editing at all. Don't make trivial edits. — user207421, Dec 10 '19 at 04:13
@user207421 it was part of the "duplicate titles" collection (second link on my profile). Also note that you closed it as a duplicate of an off-topic question. — Cœur, Dec 10 '19 at 04:15

DaoWen · Answer 1 · 2014-03-13T07:58:22.693

Each recursive call works on a segment half as big as the parent call:

int mid=array.length / 2;

When the sub-segment length reaches one, the recursion is at the "base case" and the method returns:

if(array.length==1)
    return;

I think this is actually an implementation of Quicksort. This algorithm belongs to a family of algorithms known as Divide and Conquer, since they work by recursively dividing the problem into smaller and smaller pieces, solving the smaller problems, and finally combining the smaller solutions to get the full result.

Now that you know what the algorithm is called, I'd recommend studying the algorithm in more detail if you'd like to better understand how it works. The Wikipedia article even has one of those nice animations to help you visualize how the algorithm works.

Note that the code as posted will result in infinite recursion for an empty array. The usual way that Quicksort avoids this is by checking for the base case using length ≤ 1 rather than length = 1.

score 3 · Answer 2 · answered Mar 13 '14 at 07:42

It stops because part1 and part2 are smaller arrays than the original one. And finally they are just 1-element array, and so

if(array.length==1)
    return;

fires. In general, you have a recurrent function here in the form of

  T(n)     =    T(n/2)     +    T(n/2)       + O(n) 
  ----          ------          ------         ---
sort(part)     sort(part1)     sort(part2)     merge

T(1) = 1 #

score 0 · Answer 3 · answered Mar 13 '14 at 07:42

0

At each recursive call you divide your array into 2 new half-sized arrays. Your base condition says that if the size of the array is 1 then return. That's where your program stops because eventually size of the arrays will be 1 .

answered Mar 13 '14 at 07:42

newbieee

440
1
5
17

score 0 · Answer 4 · edited Apr 12 '17 at 07:31

Each time the sort method is called, it keeps the current method call in stack and pushes the new call to sort. So at the end of that method call, the previous call to sort gets executed and this continues until the stack is empty, or the first call to sort returns.

https://softwareengineering.stackexchange.com/questions/25052/in-plain-english-what-is-recursion

The above example explains recursion in great detail.

How recursion works

4 Answers4