Introduction

Next: Advanced Recursion

Recursion is process that repeats itself in a similar way. Anything that has its definition nested inside itself is considered to be recursive. For example, GNU stands for GNU's Not Unix!. Expanding this acronym gives us ((GNU's Not Unix) Not Unix!). As you can see this will go on forever and GNU's definition is nested inside itself so it is recursive. The Fibonacci sequence is also recursive: F(n) = F(n-1)+F(n-2). Inside the function F, we see two more F's!

In computer science, we want to avoid infinite looping since we want our programs to finish at some point. This means we have to find a stopping point where the function will stop calling itself. A base case is the condition where the last step is reached. All cases should eventually reduce to a base case. For the Fibonacci sequence, the base case is F(0) = 1 and F(1) = 1, and we can see that for all N>1, the Fibonacci sequence will reach the base case.

So for something to be recursive in computer science, it needs:

  • a recursive definition (contained in itself) and
  • a base case that all valid inputs will eventually reach

Template for recursion:

fun(x) {
  if baseCase(x) {
    return base
  }
  else {
    return fun(reduce(x))
  }
}

In this generic recursive function, fun is the recursive function with a single parameter x. The function baseCase(x) checks if x is the base case and if it is, fun(x) will return. The function reduce(x) reduces x to a value closer to the base case. If x is not the base case then we recursively call fun on a reduced version of x. This is the basis of most recursive functions.

Factorial

Let's look at a simple recursive function: factorial.

1! = 1

n! = 1 ∙ 2 ∙ 3 .... n.

Or we could write it as n! = (n-1)! ∙ n. We now see that in this form, the factorial function is defined within itself which makes it recursive. Our base case is 1! = 1.

Example:

4!

= 4 ∙ 3!

= 4 ∙ 3 ∙ 2!

= 4 ∙ 3 ∙ 2 ∙ 1!

= 4 ∙ 3 ∙ 2 ∙ 1

= 24

Formalization

Let f(n) be the nth factorial number where n is a positive integer.

Base case:
f(1) = 1

Recurrence:
f(n) = f(n-1) * n

Example:
f(4) 
= 4 * f(3)
= 4 * 3 * f(2)
= 4 * 3 * 2 * f(1)  [Base Case]
= 4 * 3 * 2 * 1
= 24

Implementation

int factorial(int n){
  if (n == 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

Sum of digits of a string

We can use recursion in many places, and we can apply it to simple problems that you probably have not thought about. Summing the digits of a string can be done using a simple loop, but we can also use recursion to do it.

Let's say we have the string '23528'. The sum is equal to the first digit plus the sum of the rest of the digits: 2 + '3528'. The sum of the rest of the digits is equal to sum of the second digit plus the rest of those digits. As we can see, each time we are performing the same operation on smaller parameters and this is our recurrence relation. We can keep doing this until we have no more digits and that is our base case.

  • sum('23528')
  • 2 + sum('3528')
  • 2 + 3 + sum('528')
  • 2 + 3 + 5 + sum('28')
  • 2 + 3+ 5 + 2 + sum('8')
  • 2 + 3+ 5 + 2 + 8 + sum('')
  • 2 + 3 + 5 + 2 + 8 + 0
  • 20

Formalization

Let sum(string) be the sum of digits in a string.
Let n be the length of the string.

For simplicity, let string[x..y] be the substring of the string from x inclusive to y exclusive.
Example: 
string = 'abcd'
string[0] = 'a'
string[1..4] = 'bcd'

Base case:
sum('') = 0

Recurrence:
sum(string) = int(string[0]) + sum(string[1..n])

Example:
sum("23528")
= 2 + sum("3528")
= 2 + ( 3 + ( sum("528") )
= 2 + ( 3 + ( 5 + sum ("28") ) )
= 2 + ( 3 + ( 5 + ( 2 + sum("8") ) ) ) )
= 2 + ( 3 + ( 5 + ( 2 + ( 8 + sum("") ) ) ) ) )
= 2 + ( 3 + ( 5 + ( 2 + ( 8 + 0 ) ) ) )
= 20

Implementation

int sum(String str) {
  int n = str.length();
  // Base case when string is empty.
  if (n == 0) {
    return 0;
  }
  // Case when string is not empty.
  else {
    // Convert ASCII to number.
    int charToNum = (str.charAt(0) - '0');
    return charToNum + sum(str.substring(1, n));
  }
}

// Example: should return 20.
sum('23528');

Count

Let's say we have an string of N characters and we want to find the number of times the letter 'c' appears. This time we will need to add some logic to the solution.

If the first letter of the string is a 'c', then we can add 1 to the count. Otherwise, we don't add anything. We can do the exact same thing for the rest of the string. If the second letter of the string is a 'c', we add 1, otherwise we don't add anything etc. As we can see, we are repeating the process on smaller parameters and we have our recurrence relation. We keep reducing this way until we get an empty string and this is our base case.

For example, we have the string 'cacaec'. Since the first letter is a 'c', we add 1 to the count. Then we do the same for the rest of the string 'acaec', the first letter is not a 'c' so we don't add to the count.

  • 'cacaec'
  • 1 + 'acaec'
  • 1 + 0 + 'caec'
  • 1 + 0 + 1 + 'aec'
  • 1 + 0 + 1 + 0 + 'ec'
  • 1 + 0 + 1 + 0 + 0 + 'c'
  • 1 + 0 + 1 + 0 + 0 + 1 + ''
  • 1 + 0 + 1 + 0 + 0 + 1 + 0
  • 3

Formalization

Let count(string) be the number of 'c's in the string.

For simplicity, let string[x..y] be the substring of the string from x inclusive to y exclusive.
Example: 
string = 'abcd'
string[0] = 'a'
string[1..4] = 'bcd'

Base case:
count(empty) = 0

Recurrence:
count(string) = 1 + count(string[1..n]) if string[0]=='c' 
count(string) = count(string[1..n]) otherwise

Example:
count("cacaec")
= 1 + count("acaec") 
= 1 + ( 0 + count("caec") )
= 1 + ( 0 + ( 1 + count("aec") ) )
= 1 + ( 0 + ( 1 + ( 0 + count("ec") ) ) )
= 1 + ( 0 + ( 1 + ( 0 + ( 0 + count("c") ) ) ) )
= 1 + ( 0 + ( 1 + ( 0 + ( 0 + ( 1 + count("") ) ) ) )
= 1 + ( 0 + ( 1 + ( 0 + ( 0 + ( 1 + 0 ) ) ) ) )
= 3

Implementation

int count(String str) {
  int n = str.length();

  // Base case for empty string.
  if (n == 0) {
    return 0;
  }
  // Case if first character is a 'c'.
  if (str.charAt(0) == 'c') {
    return count(str.substring(1, n)) + 1;
  }
  // Case if first character is not a 'c'.
  else {
    return count(str.substring(1, n));
  }
}

//Example: should return 3.
count('cacaec');

Calculate Exponential

Let's say we wanted to find the last four digits xn. Note that 2674 mod 10000 = (2673 mod 10000) * 267 mod 10000. This is important because it means we can take the last 4 digits in each step instead of having to compute the giant exponent and then taking the last 4 digits. By definition of exponents, xa * xa = x2a. Using this, we see that if n is divisible by 2, then xn = xn/2 * xn/2.

For example, 54 = 52 * 52.

But let's take a look at xn/2. If n is even, we can do the exact same thing! xn/2 = xn/4 * xn/4. We are solving a reduced version of the same problem so we have a recurrence relation. The base case is simple: x1 = x.

But what if n is odd and not 1? Then we have xn = x^^(n-1)/2^^ * x^^(n-1)/2^^ * x. Thus our recursive function has 3 different cases: the base case, even case and odd case.

Formalization

Let exp(b,n) be b^n.

Base case:
exp(b,1) = b  (Since b^1 = b)

Recurrence:
exp(b,n) = exp(b, n / 2) ^ 2 % 10000 if n is even
exp(b,n) = exp(b, (n - 1) / 2) ^ 2) * b % 10000 otherwise

Example: (for simplicity, leave out the modulus)
exp(3,10)
= exp(3, 5) ^ 2
= (exp(3, 2) ^ 2)) * 3) ^ 2
= (((exp(3, 1) ^ 2) * 3) ^ 2) [Base case]
= (((3 ^ 2) ^ 2) * 3) ^ 2)
= ((9 ^ 2) * 3) ^ 2)
= (81 * 3) ^ 2
= (243) ^ 2
= 59049

Implementation

int exponent(int b, int n){
  //Base case when n is 1.
  if (n == 1) {
    return b;
  }
  // Case when n is even.
  if(n % 2 == 0) {
    int x = exponent(b, n / 2);
    return (x * x) % 10000;
  }
  // Case when n is odd.
  else {
    int x = exponent(b, (n - 1) / 2);
    return (x * x * b) % 10000;
  }
}

Exercises

  1. Given an array of N integers, write a recursive function to get the sum.
  2. Given a string S, write a recursive function to determine if it is a palindrome.
  3. Given a number N, write a recursive function to output the number in binary.
  4. Given a string S, write a recursive function to return a reversed string.