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
4Output
5Classic 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.
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 simplest definition is xn = x · xn−1. It makes n calls. It is much faster to use halving the exponent:
n is even: xn = (xn/2)2;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.
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: 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.
Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.
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?
45Read 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).
2 100247 1000000000000000000001Read n and then n natural numbers. Print their greatest common divisor.
4
12 18 30 426int up to 2·109, long long up to 9·1018.n/2 in a variable – two identical calls spoil the complexity.a / d * b, to avoid overflow.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?