Part One - Recursion Basics
Nested C++ Recursion - Introduction (Main Article Page)
Like loops, recursive software repeats statement execution in a controlled way. However, recursion solves problems that loops can’t handle. For example, a file directory structure can have two node types:
A loop solution can’t easily visit, or “traverse,” every node because a loop can’t efficiently deal with the different node types. Additionally, a loop can’t easily cover all levels of the parent-child structure. Recursion can solve the problem. Recursive software needs
but it also needs
to work. C++ and modern laptops and desktops cover the resource requirements. This article will show how lambdas, anonymous functions, and closures can expand the recursion solution space. We’ll explore C++ 14 software built in Visual Studio 2015 Enterprise, on a Windows 10 Home device. Except for the factorial example, all the recursive solutions that this article examines need heavy stack resources because of their recursion engineering. We’ll see how to configure the solutions for this as we proceed.
Often enough, developers first see recursion through the factorial function. The factorial function multiplies together all positive integers less than or equal to a given integer n. For example, if n = 6, the factorial calculation of n looks like this
n! = 6! = 6 x 5 x 4 x 3 x 2 x 1 = 720
and a C++ loop solution will certainly work:
#include "stdafx.h"
#include <iostream>
int loop_factorial(int n) {
unsigned long x = 1;
for (int i = 1; i <= n; i++) {
x *= i;
}
return x;
}
int main()
{
unsigned int n;
std::cout << "To use the factorial function, please type\n\n";
std::cout << “an integer greater than 0, and hit <ENTER<: ";
std::cin >> n;
std::cout << "\nFactorial(" << n << ") = " << loop_factorial(n) << "\n\n";
return 0;
}
This loop_factorial() function works for n values between 1 and 12 because of the long integer type data size restriction. This function multiplies all integers from 1 up to and including a given n value. A recursive factorial program in C++ might look like this:
#include "stdafx.h"
#include <iostream>
int recursive_factorial(int n) {
unsigned long x;
if (n == 1) {
// Base case: return n
return (n);
}
else {
// Recursively call recursive_factorial()
// with argument (n - 1)
return (n * recursive_factorial(n - 1));
}
}
int main()
{
unsigned int n;
std::cout << "To use the factorial function, please type\n\n";
std::cout << "an integer greater than 0, and hit <ENTER>: ";
std::cin >> n;
std::cout << "\nFactorial(" << n << ") = " << recursive_factorial(n) << "\n\n";
return 0;
}
The recursive_factorial() function has a base case at n == 1. When n gets to 1, the function returns n to main(). Otherwise, the else block multiplies the existing n value by a recursive call to the recursive_factorial() function. However, that call has an (n – 1) argument value. This moves the function – the software system – closer to the defined base. For values of n between 1 and 12, the recursive_factorial() function will get to the base case in a finite number of steps. This factorial solution shows that C++ can handle recursion. Unfortunately, the technique behind the solution offers little flexibility if we want to build software involving nested recursion. If we want to proceed through a file directory structure as described above, for example, and then run a different recursive process at every node, the technique behind the factorial solution won’t move us very far.
Here, we saw the basics of the recursion concept. Part Two - Pentagonal Numbers will describe the problem we'll solve with nested C++ recursion.
Like loops, recursive software repeats statement execution in a controlled way. However, recursion solves problems that loops can’t handle. For example, a file directory structure can have two node types:
• directory (a parent with zero or more child directories, and zero or more child files)
• file
A loop solution can’t easily visit, or “traverse,” every node because a loop can’t efficiently deal with the different node types. Additionally, a loop can’t easily cover all levels of the parent-child structure. Recursion can solve the problem. Recursive software needs
• a base case, or a defined solution for the software system
• a way to drive the software system toward the base case in a finite number of steps
but it also needs
• a software development product that handles recursion
• hardware resources that can handle recursive software memory demands
to work. C++ and modern laptops and desktops cover the resource requirements. This article will show how lambdas, anonymous functions, and closures can expand the recursion solution space. We’ll explore C++ 14 software built in Visual Studio 2015 Enterprise, on a Windows 10 Home device. Except for the factorial example, all the recursive solutions that this article examines need heavy stack resources because of their recursion engineering. We’ll see how to configure the solutions for this as we proceed.
Often enough, developers first see recursion through the factorial function. The factorial function multiplies together all positive integers less than or equal to a given integer n. For example, if n = 6, the factorial calculation of n looks like this
n! = 6! = 6 x 5 x 4 x 3 x 2 x 1 = 720
and a C++ loop solution will certainly work:
#include "stdafx.h"
#include <iostream>
int loop_factorial(int n) {
unsigned long x = 1;
for (int i = 1; i <= n; i++) {
x *= i;
}
return x;
}
int main()
{
unsigned int n;
std::cout << "To use the factorial function, please type\n\n";
std::cout << “an integer greater than 0, and hit <ENTER<: ";
std::cin >> n;
std::cout << "\nFactorial(" << n << ") = " << loop_factorial(n) << "\n\n";
return 0;
}
This loop_factorial() function works for n values between 1 and 12 because of the long integer type data size restriction. This function multiplies all integers from 1 up to and including a given n value. A recursive factorial program in C++ might look like this:
#include "stdafx.h"
#include <iostream>
int recursive_factorial(int n) {
unsigned long x;
if (n == 1) {
// Base case: return n
return (n);
}
else {
// Recursively call recursive_factorial()
// with argument (n - 1)
return (n * recursive_factorial(n - 1));
}
}
int main()
{
unsigned int n;
std::cout << "To use the factorial function, please type\n\n";
std::cout << "an integer greater than 0, and hit <ENTER>: ";
std::cin >> n;
std::cout << "\nFactorial(" << n << ") = " << recursive_factorial(n) << "\n\n";
return 0;
}
The recursive_factorial() function has a base case at n == 1. When n gets to 1, the function returns n to main(). Otherwise, the else block multiplies the existing n value by a recursive call to the recursive_factorial() function. However, that call has an (n – 1) argument value. This moves the function – the software system – closer to the defined base. For values of n between 1 and 12, the recursive_factorial() function will get to the base case in a finite number of steps. This factorial solution shows that C++ can handle recursion. Unfortunately, the technique behind the solution offers little flexibility if we want to build software involving nested recursion. If we want to proceed through a file directory structure as described above, for example, and then run a different recursive process at every node, the technique behind the factorial solution won’t move us very far.
Here, we saw the basics of the recursion concept. Part Two - Pentagonal Numbers will describe the problem we'll solve with nested C++ recursion.