Recursion Problem Solving I: Power, Digit Sum and Number Reversal

9
0

Recursion Problem Solving - I

Recursive problem solving begins by defining exactly what a function should return. The current problem is then expressed in terms of the same function applied to a smaller input.

The problems in this editorial focus on numbers and their digits. Each solution follows the same broad process:

  • Define the responsibility of the recursive function.

  • Identify how to reduce the input.

  • Determine the contribution of the current step.

  • Choose a correct base case and return value.

  • Combine the current contribution with the smaller problem's answer.

Problem 1: Calculate the Power of a Number

Given a base b and a non-negative exponent x, calculate: bx

For example, if b = 5 and x = 3:

53 = 5 * 5 * 5 = 125

Iterative Approach

The iterative solution begins with an accumulator equal to 1. It multiplies the accumulator by the base exactly x times.

  • Initially, answer = 1.

  • After the first multiplication, answer = 5.

  • After the second multiplication, answer = 25.

  • After the third multiplication, answer = 125.

Recursive Definition

Define power(b, x) as the value of bx. The exponent can be reduced by one:

power(b, x) = b * power(b, x - 1)

The smallest exponent is zero:

power(b, 0) = 1

Any nonzero base raised to the power zero is one. In ordinary integer power implementations, 00 is also commonly returned as 1 by convention.

#include <iostream>
using namespace std;
long long powerIterative(int base, int exponent) {
long long answer = 1;
for (int count = 1; count <= exponent; count++) {
answer *= base;
}
return answer;
}
long long powerRecursive(int base, int exponent) {
if (exponent == 0) {
return 1;
}
return base * powerRecursive(base, exponent - 1);
}
int main() {
int base = 5;
int exponent = 3;
cout << powerIterative(base, exponent) << '\n';
cout << powerRecursive(base, exponent) << '\n';
return 0;
}

Dry Run for 5 to the Power 3

The calls expand as follows:

  • powerRecursive(5, 3) = 5 * powerRecursive(5, 2)

  • powerRecursive(5, 2) = 5 * powerRecursive(5, 1)

  • powerRecursive(5, 1) = 5 * powerRecursive(5, 0)

  • powerRecursive(5, 0) = 1

The answers then return through the call stack:

  • powerRecursive(5, 0) returns 1.

  • powerRecursive(5, 1) returns 5 * 1 = 5.

  • powerRecursive(5, 2) returns 5 * 5 = 25.

  • powerRecursive(5, 3) returns 5 * 25 = 125.

Complexity Analysis

  • Time complexity: O(x).

  • Recursive stack space: O(x).

This direct recursive method assumes that the exponent is non-negative. Negative exponents require a fractional return type and a separate definition.

Problem 2: Count the Digits in a Number

Given a non-negative integer n, determine how many decimal digits it contains.

For example: n = 498

The number contains three digits: 4, 9, and 8.

Removing the Last Digit

Integer division by 10 removes the final decimal digit:

  • 498 / 10 = 49

  • 49 / 10 = 4

  • 4 / 10 = 0

Each reduction removes exactly one digit. Therefore, the recursive function contributes one and asks the smaller number for its remaining digit count:

countDigits(n) = 1 + countDigits(n / 10)

The helper function stops when n reaches zero:

countDigits(0) = 0

This zero represents an empty remaining suffix during recursion. The original number zero is a special input because its decimal representation contains one digit.

#include <iostream>
using namespace std;
int countDigitsIterative(int n) {
if (n == 0) {
return 1;
}
int count = 0;
while (n > 0) {
count++;
n /= 10;
}
return count;
}
int countDigitsRecursiveHelper(int n) {
if (n == 0) {
return 0;
}
return 1 + countDigitsRecursiveHelper(n / 10);
}
int countDigitsRecursive(int n) {
return n == 0 ? 1 : countDigitsRecursiveHelper(n);
}
int main() {
int n = 498;
cout << countDigitsIterative(n) << '\n';
cout << countDigitsRecursive(n) << '\n';
}

Iterative Dry Run for 498

  • Start with n = 498 and count = 0.

  • Increment the count to 1 and reduce n to 49.

  • Increment the count to 2 and reduce n to 4.

  • Increment the count to 3 and reduce n to 0.

  • The loop ends and returns 3.

Recursive Dry Run for 498

The calls expand as follows:

  • countDigits(498) = 1 + countDigits(49)

  • countDigits(49) = 1 + countDigits(4)

  • countDigits(4) = 1 + countDigits(0)

  • countDigits(0) = 0

The returned values are:

  • countDigits(4) = 1 + 0 = 1

  • countDigits(49) = 1 + 1 = 2

  • countDigits(498) = 1 + 2 = 3

Complexity Analysis

If the number contains d digits:

  • Time complexity: O(d), equivalent to O(log10 n) for positive n.

  • Recursive stack space: O(d).

Problem 3: Calculate the Sum of Digits

Given a non-negative integer, calculate the sum of its decimal digits.

For example:

115 = 1 + 1 + 5 = 7

Extracting the Last Digit

Two arithmetic operations are central to digit problems:

  • n % 10 extracts the last digit.

  • n / 10 removes the last digit.

For 115:

  • 115 % 10 = 5 and 115 / 10 = 11.

  • 11 % 10 = 1 and 11 / 10 = 1.

  • 1 % 10 = 1 and 1 / 10 = 0.

Recursive Definition

The current call contributes the final digit and recursively calculates the sum of the remaining prefix:

sumDigits(n) = (n % 10) + sumDigits(n / 10)

The base case is: sumDigits(0) = 0

Zero is the correct identity because adding zero does not change the accumulated sum.

#include <iostream>
using namespace std;
int sumDigitsIterative(int n) {
int sum = 0;
while (n > 0) {
sum += n % 10;
n /= 10;
}
return sum;
}
int sumDigitsRecursive(int n) {
if (n == 0) {
return 0;
}
int lastDigit = n % 10;
int remainingSum = sumDigitsRecursive(n / 10);
return lastDigit + remainingSum;
}
int main() {
int n = 115;
cout << sumDigitsIterative(n) << '\n';
cout << sumDigitsRecursive(n) << '\n';
}

Iterative Dry Run for 115

  • Start with sum = 0.

  • Extract 5, making sum = 5; reduce the number to 11.

  • Extract 1, making sum = 6; reduce the number to 1.

  • Extract 1, making sum = 7; reduce the number to 0.

  • Return 7.

Recursive Dry Run for 115

The calls expand into:

  • sumDigits(115) = 5 + sumDigits(11)

  • sumDigits(11) = 1 + sumDigits(1)

  • sumDigits(1) = 1 + sumDigits(0)

  • sumDigits(0) = 0

The answers return as follows:

  • sumDigits(1) = 1 + 0 = 1

  • sumDigits(11) = 1 + 1 = 2

  • sumDigits(115) = 5 + 2 = 7

Why Digit Order Does Not Matter Here

Addition is commutative. The digits may effectively be combined as 1 + 1 + 5 or 5 + 1 + 1; both orders produce 7. This allows each call to extract the final digit and combine it with the recursively calculated sum of the remaining number.

Complexity Analysis

  • Time complexity: O(d).

  • Recursive stack space: O(d).

Problem 4: Calculate the Product of Digits

Given a non-negative integer, calculate the product of its digits.

For example: 125 = 1 * 2 * 5 = 10

Recursive Definition

The current call extracts the final digit and multiplies it by the product returned for the remaining number:

productDigits(n) = (n % 10) * productDigits(n / 10)

The recursive helper uses the base case:

productDigits(0) = 1

The base case returns one because one is the multiplicative identity: x * 1 = x

Returning zero would cause every result above the base case to become zero, regardless of the actual digits.

#include <iostream>
using namespace std;
int productDigitsIterative(int n) {
if (n == 0) {
return 0;
}
int product = 1;
while (n > 0) {
product *= n % 10;
n /= 10;
}
return product;
}
int productDigitsRecursiveHelper(int n) {
if (n == 0) {
return 1;
}
return (n % 10) * productDigitsRecursiveHelper(n / 10);
}
int productDigitsRecursive(int n) {
return n == 0 ? 0 : productDigitsRecursiveHelper(n);
}
int main() {
int n = 125;
cout << productDigitsIterative(n) << '\n';
cout << productDigitsRecursive(n) << '\n';
}

Recursive Dry Run for 125

The calls expand as follows:

  • productDigits(125) = 5 * productDigits(12)

  • productDigits(12) = 2 * productDigits(1)

  • productDigits(1) = 1 * productDigits(0)

  • The helper's productDigits(0) returns 1.

The answers return through the stack:

  • productDigits(1) = 1 * 1 = 1

  • productDigits(12) = 2 * 1 = 2

  • productDigits(125) = 5 * 2 = 10

The Input Zero and the Empty Suffix

There is an important distinction between two meanings of zero:

  • When zero appears after repeatedly removing digits, it represents an empty remaining suffix. Its product identity must be one.

  • When the original input is the number zero, its only digit is zero, so the product of its digits is zero.

The public function handles the original input zero separately, while the recursive helper returns one at the end of a positive number's decomposition.

Numbers Containing a Zero Digit

If the number is 105, one extracted digit is zero. The multiplication correctly becomes zero:

1 * 0 * 5 = 0

Why Digit Order Does Not Matter Here

Multiplication is commutative. The product remains the same whether the digits are processed as 1 * 2 * 5 or 5 * 2 * 1.

Complexity Analysis

  • Time complexity: O(d).

  • Recursive stack space: O(d).

Problem 5: Reverse a Number

Given a non-negative integer, return the number formed by reversing its decimal digits.

For example: 456 becomes 654.

Iterative Construction

The reverse is built one digit at a time using:

reversed = reversed * 10 + lastDigit

Multiplication by 10 shifts the existing digits one place to the left. The extracted digit is then placed in the newly opened units position.

For 456:

  • Start with reversed = 0.

  • Append 6: 0 * 10 + 6 = 6.

  • Append 5: 6 * 10 + 5 = 65.

  • Append 4: 65 * 10 + 4 = 654.

Why an Accumulator Is Required

Unlike addition and multiplication, decimal digit stitching is order-sensitive. The digits must be appended in the order in which they are extracted: 6, then 5, then 4.

Every recursive call needs the reverse constructed by the previous calls. Therefore, the partially built number is carried as an accumulator parameter.

#include <iostream>
using namespace std;
int reverseIterative(int n) {
int reversed = 0;
while (n > 0) {
reversed = reversed * 10 + n % 10;
n /= 10;
}
return reversed;
}
int reverseRecursiveHelper(int n, int reversed) {
if (n == 0) {
return reversed;
}
int updated = reversed * 10 + n % 10;
return reverseRecursiveHelper(n / 10, updated);
}
int reverseRecursive(int n) {
return reverseRecursiveHelper(n, 0);
}
int main() {
int n = 456;
cout << reverseIterative(n) << '\n';
cout << reverseRecursive(n) << '\n';
}

Recursive Dry Run for 456

  • reverseHelper(456, 0) creates 6 and calls reverseHelper(45, 6).

  • reverseHelper(45, 6) creates 65 and calls reverseHelper(4, 65).

  • reverseHelper(4, 65) creates 654 and calls reverseHelper(0, 654).

  • reverseHelper(0, 654) reaches the base case and returns 654.

The value 654 is returned by every suspended call until it reaches main().

Trailing Zeros in the Original Number

Integer values do not preserve leading zeros. Reversing 1200 mathematically produces the digit sequence 0021, but as an integer the result is simply 21.

Complexity Analysis

  • Time complexity: O(d).

  • Recursive stack space: O(d).

Comparing the Digit Recurrences

Several digit problems reduce the number using n / 10, but they combine the current digit differently.

  • Digit count: 1 + countDigits(n / 10)

  • Digit sum: (n % 10) + sumDigits(n / 10)

  • Digit product: (n % 10) * productDigits(n / 10)

  • Number reversal: carry reversed * 10 + n % 10 into the next call.

Counting, addition, and multiplication can combine independently returned values because their relevant operations do not depend on digit order. Reversal must preserve construction order, so it carries the partially built answer forward.

Choosing the Correct Base-Case Value

The value returned by a base case participates in every result above it. It must be neutral for the operation being performed.

  • Power uses multiplication, so exponent zero returns 1.

  • Digit counting uses addition, so the empty suffix returns 0.

  • Digit sum uses addition, so the empty suffix returns 0.

  • Digit product uses multiplication, so the empty suffix returns 1.

  • Number reversal returns the accumulator already constructed.

A mechanically chosen base value can ruin the entire recurrence. For example, returning zero from the product helper would force every product to become zero.

Common Mistakes

  • Forgetting to reduce the exponent in the power function.

  • Using a base case that cannot be reached.

  • Returning zero from a multiplicative recurrence.

  • Treating the helper's empty suffix as identical to the original input zero.

  • Using n / 10 when the final digit is needed and n % 10 when the remaining number is needed.

  • Forgetting to return the result of the recursive call.

  • Attempting to reverse a number without carrying the partially constructed reverse.

  • Ignoring possible integer overflow for large powers, products, or reversed values.

  • Applying these positive-number recurrences to negative inputs without first defining the expected sign behavior.

Problem-Solving Pattern

For each recursive numerical problem, use the following process:

  • Write down what function(n) means.

  • Find a smaller input, often n - 1 or n / 10.

  • Determine the contribution of the current call.

  • Write the mathematical recurrence.

  • Identify the smallest meaningful input.

  • Choose a base return value compatible with the operation.

  • Dry-run the downward calls.

  • Dry-run the returned values in reverse order.

  • Check special inputs such as zero.

Key Takeaways

  • A recursive function should have a precise responsibility.

  • The recursive call must receive a smaller version of the problem.

  • Exponentiation reduces the exponent by one.

  • Digit problems reduce the number using integer division by 10.

  • The modulo operator extracts the current last digit.

  • Additive recurrences naturally use zero as their base identity.

  • Multiplicative recurrences naturally use one as their base identity.

  • Order-independent operations can combine current values with recursively returned answers.

  • Order-dependent construction, such as number reversal, often requires an accumulator.

  • A complete dry run must follow both call creation and returned values.

C++

Read Similar Blogs

C++

Recursion Problem Solving II: Array Traversal, Sorting Check and Reversal

Recursion Problem Solving - II Arrays are naturally suited to recursive processing because an array range can be divided into a current element and a smaller remaining range. A recursive function c...

9
C++

Recursion in C++ Explained: Base Cases, Call Stack and Recursive Functions

Recursion Foundation and Call Flow Recursion is a problem-solving technique in which a function calls itself with a smaller version of the original problem. Each call handles one part of the work a...

9
C++

C++ Enums Explained: Enum Class, Scoped Enumerations and State Modelling

Enums and Real-World Data Modelling Many programs need to represent values that belong to a small, fixed set of possibilities. An order can be placed, packed, shipped, delivered, or cancelled. A tr...

7
Comments0