C,C+ RECURSION AND RECURSIVE ALGORITHMS: HOW THEY ARE USEFUL IN SOLVING LARGER PROBLEMS

C,C+ RECURSION AND RECURSIVE ALGORITHMS: HOW THEY ARE USEFUL IN SOLVING LARGER PROBLEMS

By Eric Walz

Sometimes a problem is too difficult or too complex to solve because it is too big. If the problem can be broken down into smaller versions of itself, you may be able to find a way to solve one of these smaller versions and then be able to build up to a solution to the entire problem. This is the idea behind recursion. Recursive algorithms break down a problem into smaller pieces, which you either already know the answer to, or can solve by applying the same algorithm to each piece, and then combining the results.

Alternatively in computer programming, when a function calls itself can be used as a simple way to understand recursion in a C or C+ program.  The following C program shows recursion.  After execution, it prints a string (in this example your name in reverse).

Without using recursion, this simple program can also be done with the built in C++ function reverse(name.begin(), name.end()). However, these functions are not always suitable for solving complex mathematical equations.

HERE IS A CODE EXAMPLE USING RECURSION

In this example, the program prompts the user to enter their name. The programs checks the string for a match (any name is a match in this case) then by using a recursive algorithm, selects the last character of the string and uses recursion (recursive steps) on each character until the end of the string is reached (n=0). The final step of the program is outputting the initial string in reverse.

Recursive Algorithm: F(n) if n = 0 then return 1 else F(n-1)•n

#include <iostream>
#include <string>
using namespace std;

// function prototypes
void Reverse(string name);

int main( )
{
// declare variable
string name=””;
// get user data
cout <<“Enter your name: “;
getline (cin,name);
cout<< “\nYour name reversed is: “;

// function declaration
Reverse(name);
cout<<endl;
return 0;
}

// end of main

void Reverse(string name)
{
if(name == “”) // the base case
{
return;
}
else

// the recursive step
{
Reverse(name.substr(1));
cout<<name.at(0);
}

THE OUTPUT OF THIS PROGRAM:

Enter your name:    Eric Walz

Your name reversed is:  zlaW cirE

I wanted to include this visual as well of the Towers of Hanoi.  This picture shows a simple visual of the way recursion works. The problem is solved one (recursive) step at a time.  It helps some people who may be confused to visualize it like this without the code, to better understand how a computer program would handle a task like this one.  The goal is to move the tower from the left all the way to the right, moving one disk (step) at a time, never moving a larger disk on top of a smaller one.