Basics of Recursion

• Note: The topic of recursion isn’t often found on free-response questions, it shows up in the multiple-choice questions.

• Recursion has a similar idea compared to a loop, but it functions a bit differently.

• A recursive method has the characteristic to call a method itself. This is referred to as the recursive call.

• To make sure that an infinite loop doesn’t occur the recursive method calls something called a base case.

• Base case- Signal the execution to stop the recursion and return to each prior recursive call.

• The best way to explain this is to use an example.

• Say that you have a giant bag of small, and various colored candy. Since you are a programmer, and don’t want to ruin your set up you decide that you need an algorithm. You will eat the random candies one at a time until you find the candy with your favorite color. Once you found your favorite colored candy, you will eat the same colors you ate before, but in a backward order.

• Say the order that you eat the candies is red, blue, orange, blue, and green. Green is considered the based case. You will then continue to eat, and will choose the blue, orange, blue, and red candies respectively. The recursion is now complete.

  • Let’s look at some code to help simplify this further:

    eatCandy(color of current candy)
    
    {
    
      if(current candy color is green)
    
         done eating;
    
      else
    
         eat more candy;
    
    }

• Even though there are no loops used the logic, and the behavior is similar to that of loops. There is a forward, and backward progression.

  Recursively Traversing Arrays

• Recursion is very useful when you want to solve problems, and the structure continues to repeat.

• The base case is used to help stop the recursion just in case.

• You can also use recursion to traverse arrays.

• It’s often more common to use a for loop, but this is an alternative.

• Let’s use an example to explain how this would work.

• There is a lineup of football players, and they have numbered jerseys. Say you want to traverse the array to find the position of the person that has the 9 on their jersey.

  • Code:

    public int findPosition(int nums[], int key, int currentIndex)
    
    {
    
    // The code above is for if the entire array has already been traversed, it
    
    //       shows that the number doesn’t exist
    
    if(nums.length <= current Index)
    
       return -1;
    
    //if the next item found in the array matches, then return it
    
    if(nums[currentIndex] == key)
    
       return currentIndex;
    
    //or you need to step past the current item in the array, and keep searching
    
    Return findPosition(nums, key, currentIndex +1)
    
    }

• If we continue to use our example of football players it would look something like this:

  int [] players = numPlayers;
  
  int position = findPosition(players, 9,0);

• Tying it up:

  • Recursion will make sure that the task is accomplished, even though it might not actually go according to plan.

  • When the base case is reached, the execution of the current method is complete, and the process repeats all the way back to the initial recursive call.