blog
blog copied to clipboard
Qingquan-Li
C++ Recursion
Reference: Book: Starting Out with C++ from Control Structures to Objects, byTony Gaddis, ninth edition
Running on pythontutor.com and visualizing code.
Contents:
- Introduction to Recursion
- Using Recursion to Calculate the Factorial of a Number
- Recursive GCD Function
- Recursive Power Function
- Recursive Summation Function (1+2+3+...+n)
- A Recursive Algorithm for Fibonacci Numbers
1. Introduction to Recursion
Concept: A recursive funtion is one that calls itself.
// This program demonstrates a simple recursive function.
#include <iostream>
using namespace std;
// Function prototype
void message(int);
int main() {
message(3);
return 0;
}
//*************************************************************
// Definition of function message. If the value in times *
// is greater than 0, the message is displayed and the *
// function is recursively called with the argument times -1. *
//*************************************************************
void message(int times) {
cout << "**** message called with " << times << " in times ****\n";
if (times > 0) {
cout << "This is a recursive function.\n";
message(times - 1); // Recursive call
}
cout << "==> message returning with " << times << " in times <==\n";
} // Control returns here from the recursive call, causing the function to return.
Output:
**** message called with 3 in times ****
This is a recursive function.
**** message called with 2 in times ****
This is a recursive function.
**** message called with 1 in times ****
This is a recursive function.
**** message called with 0 in times ****
==> message returning with 0 in times <==
==> message returning with 1 in times <==
==> message returning with 2 in times <==
==> message returning with 3 in times <==
The function contains an if statement that controls the repetition.
As long as the times argument is greater than zero, it will display the message ant call itself again.
Each time it calls itself, it passes times - 1 as the argument.
Because there are no more statements to be executed after the function call, the third instance of the function returns control of the program back to the second instance. This repeats until all instances of the function return.
2. Using Recursion to Calculate the Factorial of a Number
In mathematics, the notation n! represents the factorial of the number n.
The factorial of a nonnegative number can be defined by following rules:
If n = 0 then n! = 1
If n > 0 then n! = 1 × 2 × 3 × ... × n
When designing a recursive algorithm to calculate the factorial of any number, we first identify the base case, which is the part of the calculation we can solve without recursion:
If n = 0 then factorial(n) = 1
What do we do when n is greater than 0? That is the recursive case, or the part of the problem we use recursion to solve:
If n > 0 then factorial(n) = n × factorial(n - 1)
The following pseudocode shows how we might implement the factorial algorithm as a recursive function:
factorial(n)
If n is 0 then
return 1
else
return n times the factorial of n - 1
end factorial
Here is the C++ code for such a function:
int factorial(int n) {
if (n == 0)
return 1; // Base case
else
return n * factorial(n - 1); // Recursive case
}
// This program demonstrates a recursive function
// to calculate the factorial of a number.
#include <iostream>
using namespace std;
// Function prototypes:
// int regular_factorial(int);
int recursive_factorial(int);
int main() {
// cout << regular_factorial(5) << endl;
cout << recursive_factorial(5) << endl; // 120
return 0;
}
//int regular_factorial(int n) {
// int result = 1;
// for (int i = 1; i <= n; i++)
// result *= i;
// return result;
//}
int recursive_factorial(int n) {
if (n == 0)
return 1; // Base case
else
return n * recursive_factorial(n - 1); // Recursive case
}
| Arguments | Return statement | Return value |
|---|---|---|
| 5 | return 5 * factorial(4) | 120 (back to factorial(5), so the final answer is 120) |
| 4 | return 4 * factorial(3) | 24 (↖️ back to return 5 * factorial(4) = 120 |
| 3 | return 3 * factorial(2) | 6 (↖️ back to return 4 * factorial(3) = 24) |
| 2 | return 2 * factorial(1) | 2 (↖️ back to return 3 * factorial(2) = 6) |
| 1 | return 1 * factorial(0) | 1 (↖️ back to return 2 * factorial(1) = 2) |
| 0 | (base case) return 1 | 1 (↖️ back to return 1 * factorial(0) = 1) |
3. Recursive GCD Function
Concept: The gcd function uses recursion to find the greatest common divisor (GCD) of two numbers.
Using Euclid's algorithm, the GCD of two positive integers, x and y, is:
gcd(x, y) = y; if y divides x evenly (means x ÷ y without leaving a remainder)
gcd(y, remainder of x/y); otherwise
The definition above states the GCD of x and y is y if x/y has no remainder. Otherwise, the answer is the GCD of y and the remainder of x/y.
// This program demonstrates a recursive function to calculate
// the greatest common divisor (gcd) of two numbers.
#include <iostream>
using namespace std;
int gcd(int, int);
int main() {
int num1, num2;
cout << "Enter two integers: ";
cin >> num1 >> num2;
cout << "The greatest common divisor of " << num1;
cout << " and " << num2 << " is ";
cout << gcd(num1, num2) << endl;
return 0;
}
int gcd(int x, int y) {
if (x % y == 0)
return y; // Base case
else
return gcd(y, x % y); // Recursive case
// argument `y` here will become the function parameter `int x`
// argument `x % y` will become the function parameter `int y`
}
Output:
Enter two integers: 81 54
The greatest common divisor of 81 and 54 is 27
Calculate gcd with a for loop:
int divisor;
for (int i = 1, i <= num2; i++) {
if (x % i == 0 && y % i == 0)
divisor = i;
}
How it Works?
#include <iostream>
/**
* A Recursive Algorithm for Computing Greatest Common Divisor.
* @param a Non-negative integer
* @param b Non-negative integer.
* a < b.
* If a > b, the first recursive call will be gcd(b % a, a). Since b % a is
* always less than a, the algorithm will adjust itself, and the inputs will
* be in the correct order in the next step.
* How: If a > b, the first recursive call will be gcd(b % a, a). In this
* case, b % a is equivalent to b since b < a, so the function will be called
* with gcd(b, a). From this point on, the algorithm will proceed with a > b,
* working as expected.
*/
int gcd(int a, int b) {
if (a == 0)
return b; // Base case
else
return gcd(b % a, a); // Recursive case
// `b % a` here will become the function parameter `int a`
// argument `a` will become the function parameter `int b`
}
int main() {
std::cout << gcd(49, 21); // 7
return 0;
}
| Arguments | Return statement | Return value |
|---|---|---|
| a = 49, b = 21 | ||
| a = 21, b = 49 | return gcd (49 % 21, 21) | 7 (7 is returned to the original calling function gcd(49, 21), so the final answer is 7) |
| a = 7, b = 21 | return gcd (21 % 7, 7) | 7 (↖️ return to gcd (49 % 21, 21)) |
| a = 0, b = 7 | (base case) return 7 | 7 (↖️ return to gcd (21 % 7, 7)) |
4. Recursive Power Function
#include <iostream>
using namespace std;
double regular_power(double, int);
double recursive_power(double, int);
int main() {
cout << "Using regular function to calculate power of a number: 0.5^3: \n";
cout << regular_power(0.5, 3) << endl;
cout << "Using recursive function to calculate power of a number: 0.5^3: \n";
cout << recursive_power(0.5, 3) << endl;
return 0;
}
double regular_power(double base, int exponent) {
double result = 1;
while (exponent != 0) {
result *= base;
exponent--;
}
return result;
}
double recursive_power(double base, int exponent) {
if (exponent == 0)
return 1;
else
return base * recursive_power(base, exponent - 1);
}
Output:
Using regular function to calculate power of a number: 0.5^3:
0.125
Using recursive function to calculate power of a number: 0.5^3:
0.125
5. Recursive Summation Function (1+2+3+...+n)
#include <iostream>
using namespace std;
int summation(int);
int main() {
cout << summation(100); // 5050
return 0;
}
int summation(int n) {
if (n == 0)
return 0;
else
// return (1 + n) * (n / 2);
// return (n * (n + 1)) / 2;
return n + summation(n - 1);
}
6. A Recursive Algorithm for Fibonacci Numbers
| index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| value: | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 |
Draw a tree for tracing fibonacci(4):
fibonacci(4) [=3]
/ \
fibonacci(3) [=2] fibonacci(2) [=1]
/ \ / \
/ \ / \
fib(2) [=1] fib(1) [=1] fib(1) [=1] fib(0) [=0]
/ \
fib(1) [=1] fib(0) [=0]
(C++ )Using a recursive function to calculate the Fibonacci number at position 4:
#include <iostream>
int fibonacci(int n) {
if (n == 0)
return 0;
if (n == 1)
return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
std::cout << fibonacci(4) << std::endl; // 3
return 0;
}
