dgurung
9/2/2016 - 4:59 AM

Recursion. Coded using algorithm mentioned in programming interview exposed.

Recursion. Coded using algorithm mentioned in programming interview exposed.

_extra_3_index_of_last_occurrence.md
content_copyfile_download
  • Rendered
  • Source

Problem #3 Find Last Occurrence of Character in String
Base Case: Well if you are at the end of the string and no characters follow, it must be the last occurrence if there is a match.
Recursive Decomposition: Start at the end of the string and after each call remove the last character.

size_t last_occurrence(std::string str, char ch)
{
  size_t length = str.size();
  if(length < 1)
    return -1;
  else if (str[length -1] == ch)
    return length;
  return last_occurrence(str.substr(0, length - 1), ch);
}
_extra_2_count_space.md
content_copyfile_download
  • Rendered
  • Source

Problem #2 Count number of spaces
Base case: When the string is empty it cannot have a space, so the count of spaces is 0.
Recursive Decomposition: Check character by character by working with substrings of the string, and then sum the counts of the strings.

size_t count_space(std::string str)
{
  if(str.size() < 1)
    return 0;
  else
    return ( (str[0] == ' ' )? 1 : 0 ) + count_space(str.substr(1));
    
}

It runs as:

count_space("It is")
( 0 + count_space("t is"))
( 0 + ( 0 + count_space(" is") ) )
( 0 + ( 0 + ( 1 + count_space("is") ) ) )
( 0 + ( 0 + ( 1 + ( 0 + count_space("s") ) ) ) )
( 0 + ( 0 + ( 1 + ( 0 + ( 0 + count_space("") ) ) ) ) )
( 0 + ( 0 + ( 1 + ( 0 + ( 0 + 0) ) ) ) )
1
_extra_1_reverse_string.md
content_copyfile_download
  • Rendered
  • Source

Source: here
To solve a problem recursively:

  1. Think about how to solve the problem for simple cases (base case).
  2. Determine how to break down larger cases into smaller instances (recursive decomposition).

Problem #1 Reverse A String
Base Case: When the string is the empty string is it the same backwards as it is forwards
Recursive Decomposition: For strings, to shrink the string to make forward progress is the same as solving the problem for substrings of the string, and then combining the sub-solutions.

/* Returns the reverse of the indicated string. */
std::string reverse(std::string str) {
 if (str.size() < 1)
  return "";
 else
  return reverse(str.substr(1)) + line[0];
}

It runs as:

reverse("Hello")
(reverse("ello")) + "H"
((reverse("llo")) + "e") + "H"
(((reverse("lo")) + "l") + "e") + "H"
((((reverse("o")) + "l") + "l") + "e") + "H"
(((("o") + "l") + "l") + "e") + "H"
"olleH"
7_2_recursion_combinations.cpp
content_copyfile_download
#include <iostream>
#include <string>

void combine(const std::string& str, std::string& str_build, int pos);

void combinations(const std::string& str)
{
    if(str.size() < 1)
        return;
    else if(str.size() < 2)
    {
        std::cout << str;
        return;
    }

    std::string str_build;

    int pos = 0;

    combine(str, str_build, pos );
}

void combine(const std::string& str, std::string& str_build, int pos)
{
    size_t length = str.size();

    for(int indx = pos; indx < length; ++indx)
    {
        str_build.push_back(str[indx]);
        std::cout << str_build << '\n';
        combine(str, str_build, indx + 1 );
        str_build.pop_back();
    }
}

int main()
{
    combinations("wxyz");
}
7_1_recursion_permutation.cpp
content_copyfile_download
#include <string>
#include <iostream>
#include <vector>

// forward declaration of permute function
void permute(const std::string& str, std::string& str_build, std::vector<bool>& used);


// Wrapper function
void permutations(const std::string& str)
{
    size_t length = str.size();

    if(length < 1)
        return;
    else if (length < 2)
    {
        std::cout << str;
        return;
    }

    std::vector<bool> used(length, false);

    std::string str_build;  // string that builds over recursion.

    permute(str, str_build, used);
}

// Recursive funtion
void permute(const std::string& str, std::string& str_build, std::vector<bool>& used)
{
    size_t length = str.size();
    // Base case
    if(str_build.size() == length )
    {
        std::cout << str_build << '\n';
        return;
    }
    // Recursive case
    for(int indx = 0; indx < length; ++indx)
    {
        if( used[indx] == true )
            continue;
        else
            used[indx] = true;
            str_build.push_back(str[indx]);
            permute(str, str_build, used);
            used[indx] = false;
            str_build.pop_back();
    }
}

int main()
{
    std::string str{"abcd"};
    permutations(str);
}