Recursion

To truly learn about Recursion, click HERE.

Up until now we have discussed the basic ways of controlling programs: Loops, Ifs and Methods. We are now going to dive into a more advanced concept that uses methods in way that you may not have considered.

Recursion is a way of controlling the flow of a program by having that method call itself to solve a problem. It operates on the principle of breaking down a large problem into smaller parts. Think of recursion as a two step process:

If the problem is simple, solve it.
If the problem is not simple, break the problem down into smaller parts and repeat on each broken down version of the problem.

Rather than dive right into the programming aspect of this type of problem solving, lets look at the problem in a more practical, real-world way first:

Consider the problem of being out of gas on a highway in the middle of the night. There are no cars around for miles, and even if there were there is little chance of them seeing you in order to pick you up and bring you to a gas station. In other words: Hitch-hiking is not an option. The nearest gas station is 2 kilometres away. How would you solve this problem?

The simple solution is to start walking. The proverb "a journey of 1000 miles begins with a single step" is an excellent application of recursion to solve a problem like this: Your problem is that you need to travel 2 kilometres on foot, which means you can break down the problem into:

Take 1 step
Travel the other 2 km minus 1 step

Often times recursive problems are easy to redefine as smaller versions of themselves, thus making recursion a good way to solve the problem. Beware: This is not always the case. Often times the recursive algorithm is actually slower than any other implementation of the same algorithm. Regardless, "divide and conquer" strategies are certainly useful.

For now, lets concern ourselves with HOW to create recursive methods.

Example:

Write a program that prints a Launch Countdown for a rocket. The output if the countdown starts from 3 should look like:

T-minus 3

T-minus 2

T-minus 1

Blast off!

Hopefully, when you look at this problem the first thing you think of is "I could use a for loop to solve it." You would be correct and it would look like this:

def countdown(n):

    for i in range(n, 0, -1):

        print("T-minus", i)

    print("Blast off!)

But what if we wanted to do this using recursion? Could we? The answer is: Yes, and it would look something like this:

def countdown(n):

    if (n<=0):

        print("Blast off!")

    else:

        print("T-minus", n)

        countdown(n-1)

We break down the problem into two cases:

The parameter n is less than or equal to 0. This is our base case, the time at which we want to print "Blast off!"
Everything else (n is greater than 0). Here we print the current count remaining. Notice that we are calling the countdown method INSIDE itself. This is the heart of of how recursion works in programming. The value being passed into our second call of countdown is always one less (n-1), ensuring we are always moving toward our base case of 0.

Review Tasks

Below are a few review tasks about recursion:

Task 1

Translate the following non-recursive algorithms into recursive algorithms. Without searching the internet. Use your brain.

Below is the non-recursive function fibo that calculates the n-th Fibonacci number :\

Python:

def fibo(n):

    if (n <= 1):

        return n

    f = 1

    fPrev = 1

    for i in range (2, n):

        temp = f

        f += fPrev

        fPrev = temp

    return f

Java:

public static int fibo(int n) {

    if (n <= 1) {

        return n;

    int f = 1;

    int fPrev = 1;

    for (int i = 2; i < n; ++i)  {

        int temp = f;

        f += fPrev;

        fPrev = temp;

Below is the non-recursive function factorial that calculates n!:

Python:

def factorial(n):

    r = 1

    for i in range(0, n):

        r = r * (i+1)

    return r

Java:

public static int factorial(int n) {

    int r = 1;

    for (int i = 0; i < n; ++i) {

        r = r * (i + 1);

Task 2

Write a recursive function to reverse a string. This function using the template provided below:

Python:

def reverse(s):

    return ""

Java:

public static String reverse(String s) {

    return "";

Task 3:

A palindrome is a sequence of characters or numbers that looks the same forwards and backwards. For example, "Madam, I'm Adam" is a palindrome because it is spelled the same reading it from front to back as from back to front. The number 12321 is a numerical palindrome. Write a function that takes a string and its length as arguments and recursively determines whether the string is a palindrome. The function should return True if the value is a palindrome and False if it is not.

Use the templates below:

Python

def isPalindrome(s):

    return True

Java

public static boolean isPalindrome (String s) {

    return true;

Task 4

Polish Notation Calculator - Given a string, you must solve a mathematical equation written in Polish Notation form. Normally, we write addition in the form "3 + 4". In Polish Notation, it is written as "+ 3 4". Your calculator should be able to solve the following equations:

+ 3 4

- 3 4

* 3 4

/ 3 4

* (+ 3 4) 5

+ (* 2 6) (- 4 3)

In other words, your calculator should be able to handle addition (+), subtraction (-), multiplication(*) and division(/). It should also be able to handle nested equations, such as the last two. For reference, the answers to the above questions are:

-1

0.75