12.1 Recursion: Introduction

[Simonefleek]

An algorithm is a sequence of steps for solving a problem. For example, an algorithm for making lemonade is:

Figure 12.1.1: Algorithms are like recipes.
Picture of lemonade and a recipe showing that algorithms are like recipes.

Some problems can be solved using a recursive algorithm. A recursive algorithm is an algorithm that breaks the problem into smaller subproblems and applies the same algorithm to solve the smaller subproblems.
he mowing algorithm consists of applying the mowing algorithm on smaller pieces of the yard and thus is a recursive algorithm.

At some point, a recursive algorithm must describe how to actually do something, known as the base case. The mowing algorithm could thus be written as:

Mow the lawn
If lawn is less than 100 square meters
Push the lawnmower left-to-right in adjacent rows
Else
Mow one half of the lawn
Mow the other half of the lawn

[Simonefleek]

Which are recursive definitions/algorithms?

1) Helping N people:

If N is 1, help that person. Else, help the first N/2 people, then help the second N/2 people. Correct

Base case is to help 1 person. Recursive applications are to help the first N/2, then the second N/2.

[Simonefleek]

Driving to the store:

Go 1 mile.
Turn left on Main Street.

Go 1/2 mile.
Correct

There is no recursive call to "driving to the store".

False 

Their is no recursion 

Sorting envelopes by zipcode:

If N is 1, done.
Else, find the middle zipcode. Put all zipcodes less than the middle zipcode on the left, all greater ones on the right. Then sort the left, then sort the right.
The base case is that there is only 1 envelope (which itself is "sorted"). The recursive calls are to sort the lower numbers, then sort the higher numbers. This recursive process actually works well for sorting envelopes, or a stack of papers with people's names, for example.

True A method may call other methods, including calling itself. A method that calls itself is a recursive method

[Simonefleek]

A method may call other methods, including calling itself. A method that calls itself is a recursive method

  public class RecursionTutorial {
Public static void main (String[] args) {

     sayHi();
  }

   private static void sayHi(int count) {
 System.out.println("Hi");

 sayHi();

its a call stack if you stack over and over and over again it could cause a stack overFlow method

Refer to the above countDown example for the following.

1) How many times is countDown() called if main() calls CountDown(5)? 6

Check

Show answer Correct

6 The first call countDown(5) comes from main(). Then countDown() calls itself with 4, then with 3, 2, 1, and finally 0. That last instance does not call again, but instead returns. 2) How many times is countDown() called if main() calls CountDown(0)? 1

Check

Show answer Correct

1 Upon being called that first time, countDown() just prints "GO!" and returns. 3) Is there a difference in how we define the parameters of a recursive versus non-recursive method? Answer yes or no.

[Simonefleek]

import java.util.Scanner;

public class RecursiveCalls {
   public static void backwardsAlphabet(char currLetter) {
      if (currLetter == 'a') {
         System.out.println(currLetter);
      }
      else {
         System.out.print(currLetter + " ");
         backwardsAlphabet((char)(currLetter - 1));
    }
 }

     public static void main (String [] args) {
        Scanner scnr = new Scanner(System.in);
        char startingLetter;

        startingLetter = scnr.next().charAt(0);

         backwardsAlphabet(startingLetter);
     }
  }

A method may call other methods, including calling itself. A method that calls itself is a recursive method

[Simonefleek]

z y x w v u t s r q p o n m l k j i h g f e d c b a Testing with input: p Your output p o n m l k j i h g f e d c b a Testing with input: a Your output a

[Simonefleek]

A method may call other methods, including calling itself. A method that calls itself is a recursive method.

PARTICIPATION ACTIVITY public class CountDownTimer { public static void countDown(int countInt) { if (countInt <= 0) { System.out.println("Go!"); } else { System.out.println(countInt); countDown(countInt - 1); } }

 public static void main (String[] args) {
    countDown(2);
 }

}

[Simonefleek]

Each call to countDown() effectively creates a new "copy" of the executing method, as shown on the right. Returning deletes that copy.

The example is for demonstrating recursion; counting down is otherwise better implemented with a loop.

Recursion may be direct, such as f() itself calling f(), or indirect, such as f() calling g() and g() calling f().

PARTICIPATION ACTIVITY 12.2.2: Thinking about recursion.