Recursion with an Array

Question

I'm having a bit of trouble understanding the concept of recursion. I understand that it is basically a method that calls itself and turns a big problem into a bunch of smaller parts to solve it. What I'm having difficulty with is using recursion with an array. Here is an example in my book:

//Precondition: x is an array of n integers
public int recur(int[] x, int n)
{
  int t;

  if(n == 1)
  return x[0];

  else
  {
    t = recur(x, n-1);

    if(x[n-1] > t)
    return x[n-1];

    else 
    return t;
  }
}

If anyone has the time, could you explain what this method does and how it works? Greatly appreciated!

If it is not clear what the code does, how about writing a small example ;) — Stefan Freitag
– Stefan Freitag, Commented Apr 1, 2014 at 5:58
@Lashane shhhhh! let OP think! is nice to get eureka momments — Caffeinated
– Caffeinated, Commented Apr 1, 2014 at 5:58
Oh, i think I get it. Each call to the recursive method checks to se if the next number in the array is larger than the previous one. And at the end it will return the largest. Is that right? — zaynv
– zaynv, Commented Apr 1, 2014 at 6:01

Robert · Accepted Answer · 2014-04-07 12:32:11Z

3

This function returns the largest integer of an integer array.

Lets see how, Your function recur takes an integer array x and its length n.

If the length of array is 1 then the lone element x[0] is the largest one.

Else we get the largest element from the array starting with x[0] to x[n-2](that is array of length n - 1) and so on, when we get the largest element we keep on sending it as the return value till recursion finishes, finally returning the largest value.

edited Apr 7, 2014 at 12:32

Robert

11k16 gold badges76 silver badges119 bronze badges

answered Apr 1, 2014 at 6:01

Mohit

92110 silver badges25 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

zaynv Over a year ago

Thank you! Is there a reason why we start from n-1 and keep going down? Could you also start with x[0] and keep going up until you get to the value of n?

Mohit Over a year ago

you can go from 0 and keep on increasing too, but then you have to let the function know both ends of the array, when we decrease from n to 0, we know that the least index possible to check is 0(that becomes implicit), if you want to increase, you have to explicitly pass on the max limit on the length of the array

Dawood ibn Kareem · Accepted Answer · 2014-04-01 06:11:27Z

2

This method finds the biggest number among the first n elements of an array.

It works by finding the biggest number among the first n-1 elements; then checking whether the nth element is bigger. The recursion comes in when it finds the biggest number in the first n-1 elements - it does that by calling itself with n-1 in place of n.

Of course, if n is 1, then there's nothing to check - we should just return the first element. This is the "base case" of the recursion.

Note that when I say the nth element, this is actually x[n-1], not x[n] because array indexes start from zero.

edited Apr 1, 2014 at 6:11

answered Apr 1, 2014 at 6:00

Dawood ibn Kareem

80.2k15 gold badges102 silver badges112 bronze badges

Comments

emibloque · Accepted Answer · 2014-04-01 06:16:27Z

In recursion we have what is called base case which is a condition to make the recursion stop. In this situation the base case is if (n==1) where the first element of x[] is returned.

Let's go to the second part of the recursion. The function is calling itself but decrementing n, until it reachs to the base case. Once the base case is returned, the function will compare the first element, now t, with the next one x[n-1] (where n is equal to 2) and return the greater of both. When one value is returned the function goes to its previous call in the stack.

In other words, to analize recursion you should go through the function calls until the base case is reached and once there, start to go back leaded by the returns or the final execution of the function.

Gaurav Gupta · Accepted Answer · 2014-04-01 06:24:14Z

As stated in above answers this method will return largest among the first n values in the array, i would like to show this answer pictorially

Assume array with values {5, 4, 2, 1, 8, 6, 4, 2, 12, 33}

-----------------------------------------------------------------------------------
caller |  10  |  9 |  8 |  7  |  6  |  5  |  4  |  3  |  2  |  1  
===================================================================================
  t    |  12  |  8 |  8 |  8  |  8  | 5   |  5  |  5  |  5  |  none 
===================================================================================
return |  33  | 12 |  8 |  8  |  8  |  8  |  5  |  5  |  5  | 5

Here caller is the invoker of recursive method. and in the n = 10, 33 will be compared with 12 and 33 will be returned to invoker. Hence invoker will received largest value in the array.

Collectives™ on Stack Overflow

Recursion with an Array

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related