Programming Discrete Math Concepts for Beginners/

...

/

Iterative Solution of Recursive Problems

Iterative Solution of Recursive Problems

Learn how a typically recursive algorithm can be implemented in an iterative way.

We'll cover the following...

Motivation for recursion

Some problems, such as tree traversals or the Tower of Hanoi, are inherently recursive. Of course, the same problems can be solved in an iterative way with the help of data structures. If we compare the lines of code, we see that recursion takes less code and looks cleaner.

In the next problem, we’ll find the prime factors of an integer. Usually, any prime number has only two factors: 1 and the number itself. Other integers have more than one factor.

Consider the number 6. It has the factors 1, 2, 3, and 6. The integer 6 is divisible by all those factors. In this list, not all factors are prime. Only 2 and 3 are prime factors.

Finding prime factors recursively in C++

In the following code snippet, we’ll find only the prime factors of an integer using recursion.

You can run the following code after typing the input value in the box given below the code.

Press + to interact
#include <iostream>
#include <string>
using namespace std;
void findPrimeFactors(int x){
    int a; 
    for(a = 2; a <= x; a++){
        if(x % a == 0){
            cout << a << " ";
            findPrimeFactors(x / a);
            break;
        }
    }
}
int main(int argc, char const *argv[]) {
    int number;
    //Enter a number: 
    cin >> number;
    cout << "\n" << "You entered a number: " << "\n";
    cout << number <<endl;
    findPrimeFactors(number);
    cout << "\n\n";
    return 0;
}

Enter the input below

We use a loop counter to call the function recursively. We can write the same code in a shorter space if we don’t use the loop counter. Instead, we can pass another parameter through the same function.

We get the following output when we run the code above:

  • Output 1:
    You
...