Kotlinlearncs.online LogoJava

    ← Prev

    Index

    Next →

    Kotlin
    Java

    • Trees : 48

    • Recursion : 47

    • Lists Review and Performance : 46

    • Linked Lists : 45

    • Algorithms and Lists : 44

    • Lambda Expressions : 43

    • Anonymous Classes : 42

    • Practice with Interfaces : 41

    • Implementing Interfaces : 40

    • Using Interfaces : 39

    • Working with Exceptions : 38

    • Throwing Exceptions : 37

    • Catching Exceptions : 36

    • References and Polymorphism : 35

    • References : 34

    • Data Modeling 2 : 33

    • Equality and Object Copying : 32

    • Polymorphism : 31

    • Inheritance : 30

    • Data Modeling 1 : 29

    • Static : 28

    • Encapsulation : 27

    • Constructors : 26

    • Objects, Continued : 25

    • Introduction to Objects : 24

    • Compilation and Type Inference : 23

    • Practice with Collections : 22

    • Maps and Sets : 21

    • Lists and Type Parameters : 20

    • Imports and Libraries : 19

    • Multidimensional Arrays : 18

    • Practice with Strings : 17

    • null : 16

    • Algorithms and Strings : 15

    • Strings : 14

    • Functions and Algorithms : 13

    • Practice with Functions : 12

    • More About Functions : 11

    • Errors and Debugging : 10

    • Functions : 9

    • Practice with Loops and Algorithms : 8

    • Algorithms I : 7

    • Loops : 6

    • Arrays : 5

    • Compound Conditionals : 4

    • Conditional Expressions and Statements : 3

    • Operations on Variables : 2

    • Variables and Types : 1

    • Hello, world! : 0

    Recursion

    int countLetter(String string, char character) {
    if (string == null) {
    throw new IllegalArgumentException("String must not be null");
    }
    if (string.length() == 0) {
    return 0;
    }
    if (string.charAt(0) == character) {
    return 1 + countLetter(string.substring(1), character);
    } else {
    return 0 + countLetter(string.substring(1), character);
    }
    }
    System.out.println(countLetter("you are not alone", 'o'));
    System.out.println(countLetter("you are not alone", 'e'));

    This lesson introduces a new problem solving strategy called recursion. Recursion represents an exciting new addition to our algorithm toolbox. It can be hard to wrap your head around at first. But we’ll go slow and, as always, use lots of examples. What are we waiting for?

    What is Recursion?
    What is Recursion?

    So far we’ve looked exclusively at iterative algorithms that solve a problem by repeating a series of steps. The implementations of iterative algorithms are characterized by the use of looping constructs such as for and while.

    Recursive algorithms work differently. They solve problems by breaking them down into smaller yet similar pieces, and the reassembling the solutions to the smaller problems into a solution to the larger problem. This will make more sense once we look at some examples!

    But let’s start by examining both the general definition of recursion and how recursion is used in computer science.

    Iteration v. Recursion
    Iteration v. Recursion

    Learning to think recursively takes time and practice. You’ll get both!

    But let’s start by comparing and contrasting an iterative and recursive solution to the same problem. That will both help us start to learn to think recursively, and identify the differences between the two approaches.

    Is A Palindrome: Iterative
    Is A Palindrome: Iterative

    Let’s write an algorithm to determine if a String is a palindrome, that is, whether it reads the same forwards and backwards. First, let’s design an iterative algorithm:

    // Iterative Palindrome

    Is A Palindrome: Recursive
    Is A Palindrome: Recursive

    Next, let’s try and approach the problem recursively.

    What does that mean? A recursive solution tries to make the problem smaller in each step until it is trivial to solve. Let’s think about how to apply that to palindrome detection.

    // Recursive Palindrome

    Compare and Contrast
    Compare and Contrast

    To wrap up, let’s put the two approaches side by side and discuss the differences.

    // Iterative Palindrome v. Recursive Palindrome

    Recursive Strategies
    Recursive Strategies

    A recursive implementation contains a function that calls itself. At first, this may seem really weird. But the trick is not to not let that throw you, and to just consider what happens.

    Successful recursive algorithms must do three things correctly:

    1. Make the problem smaller. If you don’t do this, the problem never gets small enough to solve!
    2. Solve the smallest problem. This is known as the base case.
    3. Combine the results properly. This is required to arrive at a correct solution.

    Let’s examine another recursive implementation. We’ll identify the three requirements enumerated above, and trace its execution.

    int countLetter(String string, char character) {
    if (string == null) {
    throw new IllegalArgumentException("String must not be null");
    }
    if (string.length() == 0) {
    return 0;
    }
    if (string.charAt(0) == character) {
    return 1 + countLetter(string.substring(1), character);
    } else {
    return 0 + countLetter(string.substring(1), character);
    }
    }

    Factorial
    Factorial

    The next homework problem has you complete a recursive implementation of factorial. For reference, here is the iterative implementation that matches the homework problem:

    public static long factorial(long input) {
    // factorial gets big really quickly
    if (input < 0 || input > 20) {
    throw new IllegalArgumentException();
    }
    long result = 1;
    for (long multiplier = 2; multiplier <= input; multiplier++) {
    result *= multiplier;
    }
    return result;
    }
    assert factorial(0) == 1;
    assert factorial(2) == 2;
    assert factorial(4) == 24;

    To complete the recursive implementation, consider the following questions:

    1. What is the smallest problem, or the base case? (You know that the factorial of 0 is 1).
    2. How do you make the problem smaller and combine the results? (You know that the factorial of n is n * n - 1).

    Practice: Recursive Factorial

    Created By: Geoffrey Challen
    / Version: 2020.11.0

    Create a public class Factorial that provides a single static method factorial. factorial accepts a single long and returns its factorial as a long. You can reject negative arguments and ones greater than 20 by throwing an IllegalArgumentException.

    You should submit a recursive solution. The factorial of 0 is 1, and this represents the base case. The factorial of n is n * the factorial of n - 1, and this represents the recursive step.

    Homework: Recursive Range Sum

    Created By: Geoffrey Challen
    / Version: 2021.10.0

    Create a class RangeSum with a public static method sum that accepts a single int value and returns the sum of all the integers in the range 1..value as an int. So, for example, given the input 10 you should return 55: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10. You can reject arguments less than or equal to 0 and ones greater than 128 by throwing an IllegalArgumentException.

    You should submit a recursive solution. The range sum of 1 is 1, and this represents the base case. The range sum of n is n + the range sum of n - 1, and this represents the recursive step.

    More Practice

    Need more practice? Head over to the practice page.