10-Recursion

Recursion

Chapter Goals

• To learn to “think recursively”
• To be able to use recursive helper functions
• To understand the relationship between recursion and iteration
• To understand when the use of recursion affects the efficiency of an algorithm
• To analyze problems that are much easier to solve by recursion than by iteration
• To process data with recursive structures using mutual recursion

Topics

1. Triangle numbers
2. Recursive helper functions
3. The efficiency of recursion
4. Permutations
5. Mutual recursion

Recursion

• Recursion is a powerful technique for breaking up complex computational problems into simpler ones.
• The "simpler one" leads to the solution of the whole problem.
• Recursion is often the most natural way of thinking about a problem.
• Some computations are difficult to perform without recursion.

Recursive Functions

• A recursive function is a function that calls itself, reducing the problem a bit on each call:

  void solveIt(the-Problem) {
    . . .
    solveIt(the-Problem-a-bit-reduced);
  }
  

How to think recursively – Triangle of Boxes

• Recursive function example from Chapter 5 to print a triangle of “boxes”

  []
  [][] 
  [][][] 
  [][][][]
  

  void print_triangle(int side_length);
  

Triangle of Boxes Code

void print_triangle(int side_length) {
  if (side_length < 1) { return; }
  print_triangle(side_length - 1);
  for (int i = 0; i < side_length; i++)
  {
    cout << "[]";
  }
  cout << endl;
}

How to think recursively – The Two Key Requirements

• Every recursive call must simplify the task in some way.
• There must be special cases to handle the simplest tasks directly so that the function will stop calling itself.

Triangle Numbers

• Problem: What is the sum of 1’s in a triangular pattern? Or, what is the area of a triangle of height n?

• Triangle number:

  n = 1: 1 (1)
  n = 2: 3 (2 + 1)
  n = 3: 6 (3 + 2 + 1)
  n = 4: 10 (4 + 3 + 2 + 1)
  

Triangle Numbers: the End Condition

• End condition: when side_length is 1, the triangle number (the area) is 1 and we are done.

  int triangle_area(int side_length) {
    if (side_length == 1) { return 1; }
    . . .
  }
  

Triangle Numbers: Reduced Problem

int triangle_area(int side_length) {
  if (side_length == 1) { return 1; }
  int smaller_side_length = side_length - 1;
  int smaller_area = triangle_area(smaller_side_length);
  return smaller_area + side_length;
}

• If the current side length is 4, this triangle number (the smaller triangle) plus this side length (the current side length).

Triangle Numbers: Problem

• Problem: What would happen if this function were called with -1?
• The recursive calls would be -2, -3, … forever.

Triangle Numbers: Solution

• Add a test that handles the situation where side_length is less than or equal to 0.

  int triangle_area(int side_length) {
    if (side_length <= 0) { return 0; }
    if (side_length == 1) { return 1; }
    int smaller_side_length = side_length - 1;
    int smaller_area = triangle_area(smaller_side_length);
    return smaller_area + side_length;
  }
  

Triangle Numbers Program

/**
  sec01/triangle.cpp
  Computes the area of a triangle with a given side length.
  @param side_length the side length of the triangle base
  @return the area
*/
int triangle_area(int side_length) {
  if (side_length <= 0) { return 0; }
  if (side_length == 1) { return 1; }
  int smaller_side_length = side_length - 1;
  int smaller_area = triangle_area(smaller_side_length);
  return smaller_area + side_length;
}

int main() {
  cout << "Enter the side length: ";
  int input;
  cin >> input;
  cout << "Area: " << triangle_area(input) << endl;
  return 0;
}

Common Error: Infinite Recursion

• Example:

  void forever_young( ) {
    cout << "I am " ;
    forever_young();
    cout << “forever young!" ;
  }
  

• This function prints out "forever young" forever.

Common Error: Infinite Recursion (2)

• Infinite recursion is an error.
• Each function call uses some system resources that only a return statement releases.
• The computer will hang or crash when it just WON’T STOP.
• In this code, the programmer forgot to write the end test.
• Infinite recursion can also occur when the test to end never becomes true.

Thinking Recursively – Palindromes

• Palindrome: a string that is equal to itself when you reverse all characters
• Examples:
  • Madam, I’m Adam
  • rotor

Thinking Recursively – Palindromes (1)

• Problem: Write a function to test if a string is a palindrome.

  bool is_palindrome(string s)
  

• Step 1: Break the input into parts that can themselves be inputs to the problem.

• Focus on a particular input or set of inputs for the problem.

• Think how you can simplify the inputs in such a way that the same function can be applied to the simpler input.

Thinking Recursively – Palindromes (2)

• To get simpler inputs, how about:
  • Remove the first character?
  • Remove the last character?
  • Remove both the first and the last character?
  • Remove a character from the middle?
  • Cut the string into two halves?

Thinking Recursively – Palindromes (3)

• Every palindrome’s first half is the same as its other half.
• In this problem, chopping in half seems to be a good way to reduce the problem.
• However:
  • "rotor" (chop) "rot" "or"
  • Not sure how chopping in half gets us closer to a way to determine a palindromic situation.

Thinking Recursively – Palindromes (4)

• One character at a time seems not so good.
• How about chopping off BOTH ends at the same time?
  • "rotor" (chop) "r" (chop) "oto" "r"
• We can reduce the problem to the “middle” of the string for the recursive call.

Thinking Recursively – Palindromes (5)

• Step 2: Combine solutions with simpler inputs to a solution of the original problem.
  • "rotor" (chop) "r" (chop) "oto" "r"
• If the end letters are the same AND is_palindrome( the middle word ) then the string is a palindrome!

Thinking Recursively – Palindromes (6)

• Step 3: Find solutions to the simplest inputs.
• A recursive computation keeps simplifying its inputs. Eventually it arrives at very simple inputs.
• To make sure that the recursion comes to a stop, deal with the simplest inputs separately.
• That leaves us with two possible end situations, both of which are palindromes themselves:
  • string of length 0, and string of length 1

bool is_palindrome(string s) {
  // Separate case for shortest strings
  if (s.length() <= 1 ){ return true; }
  ...

Thinking Recursively – Palindromes (7)

• Step 4: Implement the solution by combining the simple cases and the reduction step.

// Get first and last character, converted to lowercase
char first = tolower(s[0]);
char last = tolower(s[s.length() - 1]);

if (first == last)
{
  string shorter = s.substr(1, s.length() - 2);
  return is_palindrome(shorter);
}
else
{
  return false;
}

Thinking Recursively – Palindromes – Test Program

int main() {
  cout << "Enter a string: ";
  string input;
  getline(cin, input);
  cout << input << " is ";
  if (!is_palindrome(input)) { cout << "not "; }
  cout << "a palindrome." << endl;
  return 0;
}

• Program Run

Enter a string: aibohphobia
aibohphobia is a palindrome.

Recursive Helper Functions

• Sometimes it is easier to find a recursive solution if you change the problem slightly.
• Then it can be solved by calling a recursive helper function.
• Consider the palindrome problem.
• It is inefficient to construct new string objects in every step.
• Instead of testing whether the entire string is a palindrome, check whether a substring is a palindrome:

Palindrome Substring Function

• Check whether a substring is a palindrome:
• This function turns out to be even easier to implement than the original test.

/*
  Tests whether a substring of a string is a palindrome.
  @param s the string to test
  @param start the index of the first character of the substring
  @param end the index of the last character of the substring
  @return true if the substring is a palindrome
*/
bool substring_is_palindrome(string s, int start, int end);

Palindrome Substring Function (2)

• In the recursive calls, simply adjust the start and end arguments to skip over matching letter pairs.
• No need to construct new objects for the shorter strings.

bool substring_is_palindrome(string s, int start, int end) {
  // Separate case for substrings of length 0 and 1
  if (start >= end) { return true; }

  if (s[start] == s[end])
  {
    // Test substring that doesn’t contain
    // the first and last letters
    return substring_is_palindrome(s, start + 1, end - 1);
  }
  else
  {
    return false;
  }
}

Palindrome Function to Call the Helper Function

• Finally, provide a function that solves the original problem by calling the helper function.

bool is_palindrome(string s) {
  return substring_is_palindrome(s, 0, s.length() - 1);
}

Practice It: Recursive Helpers

• Recursive function for finding the first vowel in a string:

char first_vowel(string str) {
  if (str.length() == 0) { return '?'; } // No vowels
  char first = str[0];
  string rest = str.substr(1);
  if (is_vowel(first)) { return first; }
  else { return first_vowel(rest); }
}

• The above code is inefficient to generate a new string each recursive call.
• Write a recursive helper function that avoids that problem by having a substring input rather than a complete string:

char first_vowel(string str, int pos) { }

The Efficiency of Recursion

• Recursion can lead to simpler solutions to problems, but recursive algorithms may perform poorly.
• The Fibonacci sequence is a sequence of numbers defined by the equations:
  • f_1 = 1
  • f_2 = 1
  • fn = f{n-1} + f_{n-2}
• Each value in the sequence is the sum of the 2 preceding.
• The first ten terms of the sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,…

Recursive Fibonacci Sequence Code

#include <iostream>
using namespace std;

/**
 Computes a Fibonacci number.
 @param n an integer (non-negative)
 @return the nth Fibonacci number
*/
int fib(int n) {
  if (n <= 2) { return 1; }
  else return { fib(n - 1) + fib(n - 2); }
}

int main() {
  cout << "Enter n: ";
  int n;
  cin >> n;
  int f = fib(n);
  cout << "fib(" << n << ") = " << f << endl;
  return 0;
}

The Efficiency of Recursion

• Running the above code with n = 3 is too fast to time.
• Try n = 15. There appears to be a bit of a pause between outputs.
• Try n = 30, 40, 50. There is a very noticeable pause between outputs and it seems to be getting longer as n gets larger.

Fibonacci Messages

• Modify the above code to output trace messages:

int fib(int n) {
  cout << "Entering fib: n = " << n << endl;
  int f;
  if (n <= 2) { f = 1; }
  else { f = fib(n - 1) + fib(n - 2); }
  cout << "Exiting fib: n = " << n
  << " return value = " << f << endl;
  return f;
}

int main() {
  cout << "Enter n: ";
  int n;
  cin >> n;
  int f = fib(n);
  cout << "fib(" << n << ") = " << f << endl;
  return 0;
}

• The output of the above code with n = 6 is as follows:

Enter n: 6
Entering fib: n = 6
Entering fib: n = 5
Entering fib: n = 4
Entering fib: n = 3
Entering fib: n = 2
Exiting fib: n = 2 return value = 1
Entering fib: n = 1
Exiting fib: n = 1 return value = 1
Exiting fib: n = 3 return value = 2
Entering fib: n = 2
Exiting fib: n = 2 return value = 1
Exiting fib: n = 4 return value = 3
Entering fib: n = 3
Entering fib: n = 2
Exiting fib: n = 2 return value = 1
Entering fib: n = 1
Exiting fib: n = 1 return value = 1
Exiting fib: n = 3 return value = 2
Exiting fib: n = 5 return value = 5
Entering fib: n = 4
Entering fib: n = 3
Entering fib: n = 2
Exiting fib: n = 2 return value = 1
Entering fib: n = 1
Exiting fib: n = 1 return value = 1
Exiting fib: n = 3 return value = 2
Entering fib: n = 2
Exiting fib: n = 2 return value = 1
Exiting fib: n = 4 return value = 3
Exiting fib: n = 6 return value = 8
fib(6) = 8

Fibonacci Call Tree

• The above execution can be shown more clearly as a call tree.
• Notice that the same values, for example, fib(2), are computed over and over.
• Each recursive call generates 2 more calls.

The Efficiency of Iteration

• The iterative solution is best for Fibonacci numbers, because each recursive function call takes a certain amount of processor overhead time.

#include <iostream>
using namespace std;

/**
 Computes a Fibonacci number.
 @param n an integer
 @return the nth Fibonacci number
*/
int fib(int n) {
  if (n <= 2) { return 1; }
  int fold = 1;
  int fold2 = 1;
  int fnew;
  for (int i = 3; i <= n; i++)
  {
    fnew = fold + fold2;
    fold2 = fold;
    fold = fnew;
  }
  return fnew;
}

Iteration vs. Recursion

• Is the iterative solution always faster than the recursive?
• Look at the iterative palindrome solution:

bool is_palindrome(string s) {
  int start = 0;
  int end = s.length() - 1;
  while (start < end)
  {
    if (s[start] != s[end]) { return false; }
    start++;
    end--;
  }
  return true;
}

Iteration vs. Recursion (2)

• Both the iteration and the recursion run at about the same speed.
• If a palindrome has n characters, the iteration executes the loop n/2 times.
• The recursive solution calls itself n/2 times, because two characters are removed in each step.

Permutations

• A problem that would be difficult to program as an iteration: permutations.
• A permutation is simply a rearrangement of the letters.
• For example, the string "eat" has six permutations (including the original string itself):
  • "eat"
  • "eta"
  • "aet"
  • "ate"
  • "tea"
  • "tae“

Permutation Function (1)

• Write a function that generates all permutations of a string.
• Example use case for the string “eat”:

vector<string> v = generate_permutations("eat");
for (int i = 0; i < v.size(); i++) {
  cout << v[i] << endl;
}

Permutation Function Plan

• To generate the permutations recursively, consider the string "eat" and simplify the problem.
• First, generate all permutations that start with the letter 'e', then those that start with 'a', and finally those that start with 't'.
• How do you generate the permutations that start with 'e'? You need to know the permutations of the substring "at".
• That’s the same problem —to generate all permutations— with a simpler input, namely the shorter string "at".

Permutation Function Plan (2)

• For each result of the simpler problem, add the letter 'e' in front.
• Now you have all permutations of "eat" that start with 'e', namely "eat" "eta"

Permutation Function Plan (3)

• Next, turn your attention to the permutations of "eat" that start with 'a'.
• You must create the permutations of the remaining letters, "et", namely "et" "te“
• Add the letter 'a' to the front of the strings and obtain "aet" "ate"
• Generate the permutations that start with 't' in the same way.

Permutation Function Plan (4)

• When does the recursion stop?
• The simplest possible string is the empty string, which has a single permutation—itself.

Permutations via Iterations?

• Could you generate the permutations without recursion?
• There is no obvious way of writing a loop that iterates through all permutations.
• For generating permutations, it is much easier to use recursion than iteration.

Permutation Code (1)

// sec04/permute.cpp
#include <iostream>
#include <string>
#include <vector>
using namespace std;

/**
 Generates all permutations of the chars in a string.
 @param word a string
 @return a vector of all permutations of the word
*/

Permutation Code (2)

// sec04/permute.cpp
vector<string> generate_permutations(string word) {
  vector<string> result;
  if (word.length() == 0)
  {
    result.push_back(word);
    return result;
  }
  for (int i = 0; i < word.length(); i++)
  {
    string shorter_word = word.substr(0, i)+ word.substr(i + 1);
    vector<string> shorter_permutations =
    generate_permutations(shorter_word);
    for (int j = 0; j < shorter_permutations.size(); j++)
    {
      string longer_word = word[i] + shorter_permutations[j];
      result.push_back(longer_word);
    }
  }
  return result;
}

Permutation Code (3)

int main() {
  cout << "Enter a string: ";
  string input;
  getline(cin, input);
  vector<string> v = generate_permutations(input);
  for (int i = 0; i < v.size(); i++)
  {
    cout << v[i] << endl;
  }
  return 0;
}

Practice It: Permutations

• Trace through the call generate_permutations("eat")
• Write the string vectors returned by the recursive calls.

Mutual Recursion

• In the preceding examples, a function called itself.
• In mutual recursion, a set of cooperating functions calls each other in a recursive fashion.
• Develop a program that can compute the values of arithmetic expressions such as these:
  • 3 + 4 * 5
  • (3 + 4) * 5
  • 1 - (2 - (3 - (4 - 5)))
• This is hard because:
  • * and / bind more strongly than + and -
  • parentheses can be used to group subexpressions

Expression Definitions

• Expression defined using a formalized definition language:
  • An expression is either a term, or a sum or difference of terms.
  • A term is either a factor, or a product or quotient of factors.
  • A factor is either a number or an expression enclosed in parentheses.

Expression Syntax Diagrams

Expression

term

+
term

Term

factor

*
factor

Factor

expression

number

(
)

Expression Syntax Diagrams Applied

Expression

Term
Number
3
+
Factor

Number
4
*
Factor
Number
5

Factor
Expression
Term

Number
(
4
)
*
Factor
+ Number
5
3

Trees and Mutual Recursion

• Syntax trees accurately represent which operations should be carried out first.

Trees and Mutual Recursion (2)

• In the first tree, 4 and 5 should be multiplied, and then the result should be added to 3.

Trees and Mutual Recursion (3)

• In the second tree, 3 and 4 should be added, and the result should be multiplied by 5.

Functions for the Expressions

• To compute the value of an expression, implement three functions:
  • expression_value
  • term_value
  • factor_value
• The expression_value function first calls term_value to get the value of the first term of the expression.
• Then it checks whether the next input character is + or -. If so, it calls term_value again and adds or subtracts it:

expression_value Function

int expression_value(){
  int result = term_value();
  bool more = true;
  while (more) {
    char op = cin.peek(); //read char without removing
    if (op == '+' | | op == '-') {
      cin.get();
      int value = term_value();
      if (op == '+') {
        result = result + value;
      } else {
        result = result - value;
      }
    }
    else{
      more = false;
    }
  }
  return result;
}

term_value Function

• The term_value function calls factor_value in the same way, multiplying or dividing the factor values.

int term_value(){
  int result = factor_value();
  bool more = true;
  while (more){
    char op = cin.peek();
    if (op == '*' | | op == '/'){
      cin.get();
      int value = factor_value();
      if (op == '*'){
        result = result * value;
      } else {
        result = result / value;
      }
    }
    else{
      more = false;
    }
  }
  return result;
}

How the Three Functions Interact

• Finally, the factor_value function checks whether the next input character is a '(' or a digit.
• When it is a digit, the value is simply the value of the number.
• However, if the function sees a parenthesis, the factor_value function makes a recursive call to expression_value.
• Thus, the three functions are mutually recursive.

factor_value Function

int factor_value(){
  int result = 0;
  char c = cin.peek();
  if (c == '(') {
    cin.get();
    result = expression_value(); //recursive call
    cin.get(); // Read ")"
  } else { // Assemble number value from digits
    while (isdigit(c))
    {
      result = 10 * result + c - '0';
      cin.get();
      c = cin.peek();
    }
  }
  return result;
}

main() Program for Expressions

int main() {
  cout << "Enter an expression: ";
  cout << expression_value() << endl;
  return 0;
}