You are not logged in. Please login at www.codechef.com to post your questions!

×

new to recursion, getting StackOverflow. Help!

I am writing a divide and conquer recursive function to find minimum element in array. But I am getting java.lang.StackOverflowError . Here is my code. Thanks in advance.

import java.util.Scanner;

public class dynamic {

    public static void main(String arg[])
    {   int i=0;
        Scanner s=new Scanner(System.in);
        int num[]=new int[8];
        while(i<8)
        {
            num[i]=s.nextInt();
            i++;
        }

        int b=findmin(num);
        System.out.println(b);
    }

    public static int findmin(int num[])
    {
        if(num.length==0)return 0;

        return findmin(num,0,num.length-1);
    }

    public static int findmin(int num[],int first,int last)
    {   
        if(first==last )return num[first];
        if(first+1==last)return Math.min(num[first],num[last]);

        if(findmin(num,(last/2)+1,last)>findmin(num,first,last/2)) return findmin(num,first,last/2);
        else return findmin(num,(last/2)+1,last);



    }

}

asked 18 Jun '14, 18:15

filmwalams's gravatar image

5★filmwalams
1.6k113141
accept rate: 7%

edited 18 Jun '14, 18:29

betlista's gravatar image

3★betlista ♦♦
16.9k49115225


first of all there is no use calculating the minimum by divide and conquer,the algorithm is still O(N).

secondly while dividing [first,last] the division is [first,(first+last)/2] & [(first+last)/2+1,last].

third point is that you are calling the function for same arguements twice, when you are comparing & when you return.

if(findmin(num,(last/2)+1,last)>findmin(num,first,last/2)) return findmin(num,first,last/2); else return findmin(num,(last/2)+1,last);

take care of the second point and your code will run ,atleast for small inputs

link

answered 18 Jun '14, 19:15

shubham12's gravatar image

2★shubham12
4421610
accept rate: 13%

edited 18 Jun '14, 19:16

1

I am using divide and conquer here just for learning purpose, and thanks for ur help. I will check if this works.

(19 Jun '14, 16:46) filmwalams5★

yeah this worked!!!!!!!!!!!!THANKS

(19 Jun '14, 16:56) filmwalams5★

I updated your code a little - added logging, please see the output...

http://ideone.com/UeL6gt

link

answered 18 Jun '14, 19:20

betlista's gravatar image

3★betlista ♦♦
16.9k49115225
accept rate: 11%

Thanks , but u have modified my function completely so I have to understand it. Please tell me what that printspaces doing ?

(19 Jun '14, 16:48) filmwalams5★

It's just logging recursive function calls printSpaces is doing indentation, to see how the the function was called. I'm using this approach when debugging some difficult problems - it's easy to do some mistake somewhere and when it is in 5-th level of recursion debugging is like waste of time...

If I have some time, I'll modify your working solution to show you the output...

(19 Jun '14, 17:34) betlista ♦♦3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,212
×348
×138

question asked: 18 Jun '14, 18:15

question was seen: 1,797 times

last updated: 19 Jun '14, 17:36