Search⌘ K
AI Features
Home
Courses
Programming Discrete Math Concepts for Beginners

Iterative Solution of Recursive Problems

Understand the motivation behind recursion and how iterative solutions compare. Learn to implement recursive and iterative methods for problems like factorial calculation, prime factorization, and Fibonacci series. Discover the trade-offs in memory and speed, and when recursion offers clearer and more intuitive code despite overhead.

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.

C++
#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;
}
Did you find this helpful?

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. ...