Factorial, Power and GCD – Recursively

Lesson 2 of 7 · Recursion and backtracking

Classic examples of recursion from mathematics: the factorial, the power of a number (slow and fast), Euclid's algorithm and the Fibonacci sequence. With every example we also look at how many calls the function makes – this is an introduction to complexity and to dynamic programming.

Before you start: prerequisites – Introduction to recursion.
How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.

The factorial

The factorial is the product of the first n natural numbers: n! = 1 · 2 · … · n, and by convention 0! = 1. The recursive definition follows directly: n! = n · (n − 1)!.

#include <iostream>
using namespace std;

long long factorial(int n) {
    if (n <= 1) return 1;                 // 0! = 1! = 1
    return n * factorial(n - 1);
}

int main() {
    int n;
    cin >> n;
    cout << factorial(n) << endl;
    return 0;
}

The factorial grows very fast: 20! is about 2.4·1018, and that is the largest factorial that fits in a long long. For larger n, tasks usually ask for the remainder of division (e.g. by 109+7) – see the lesson Combinatorics (SR).

The power of a number: slow and fast

The simplest definition is xn = x · xn−1. It makes n calls. It is much faster to use halving the exponent:

  • if n is even: xn = (xn/2)2;
  • if n is odd: xn = x · xn−1.

This way the exponent is halved at least every two steps, so the number of calls is about 2·log₂ n – for n = 1018 that is about 120 calls instead of 1018.

#include <iostream>
using namespace std;

const long long MOD = 1000000007;

// x^n modulo MOD, for n up to 10^18
long long power(long long x, long long n) {
    if (n == 0) return 1;                     // x^0 = 1
    long long half = power(x, n / 2);         // one call for n/2 – not two!
    long long result = half * half % MOD;
    if (n % 2 == 1) result = result * (x % MOD) % MOD;
    return result;
}

int main() {
    long long x, n;
    cin >> x >> n;
    cout << power(x, n) << endl;
    return 0;
}

Important: store the result of the call for n / 2 in a variable. Written as power(x, n/2) * power(x, n/2), the solution would again make about n calls. The same idea without recursion is explained in the lesson Fast exponentiation algorithm.

Euclid's algorithm (GCD)

The greatest common divisor satisfies gcd(a, b) = gcd(b, a mod b), and gcd(a, 0) = a. That is almost literally a recursive function:

#include <iostream>
using namespace std;

long long gcd(long long a, long long b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    long long a, b;
    cin >> a >> b;
    long long d = gcd(a, b);
    cout << "GCD = " << d << ", LCM = " << a / d * b << endl;   // divide first, then multiply
    return 0;
}

The number of steps is small (logarithmic), so there is no danger of deep recursion here. More about the GCD and the LCM: Finding the GCD and the LCM.

The Fibonacci sequence: when recursion becomes slow

The Fibonacci sequence: F(0) = 0, F(1) = 1, F(n) = F(n−1) + F(n−2). Direct recursion is correct, but every call makes two new ones, so the same numbers are computed many times:

#include <iostream>
using namespace std;

long long calls = 0;

long long fib(int n) {
    calls++;
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);       // two calls -> exponentially many calls
}

int main() {
    int n;
    cin >> n;
    cout << fib(n) << " (calls: " << calls << ")" << endl;
    return 0;
}

For n = 30 that is over 2.6 million calls, and for n = 50 the program would run for minutes. The solution is to remember the values once they are computed (memoization) – that is the beginning of dynamic programming: The Fibonacci sequence, memoization and DP.

Practice tasks

Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.

TASK 01Difficulty: medium

Climbing the stairs

We climb a staircase with n steps (n ≤ 30) one or two steps at a time. In how many different ways can we reach the top?

Example

Input

4

Output

5
TASK 02Difficulty: medium

The last digits of a power

Read the natural numbers a and b (b ≤ 1018) and print the last three digits of the number ab (as a three-digit number, with leading zeros).

Example 1

Input

2 10

Output

024

Example 2

Input

7 1000000000000000000

Output

001
TASK 03Difficulty: easy

The GCD of a sequence of numbers

Read n and then n natural numbers. Print their greatest common divisor.

Example

Input

4
12 18 30 42

Output

6
Common mistakes and tips
  • Before multiplying check the range: int up to 2·109, long long up to 9·1018.
  • In fast exponentiation store the result of the call for n/2 in a variable – two identical calls spoil the complexity.
  • For the LCM divide first, then multiply: a / d * b, to avoid overflow.
  • If a recursion calls itself twice for almost the same argument (like Fibonacci), think about memoization.

Check your knowledge

Open the quiz

Mini quiz: factorial, power, GCD

1. How many calls does fast exponentiation make for n = 1024?




2. What is gcd(a, 0) equal to?




3. Why is the recursive Fibonacci slow?