学而不思则罔，思而不学则殆
伊始
递归在现实世界无处不在，在代码中使用递归，是为了更好更直观地描述现实世界。
本篇开始我们先从基本简单的递归算法练习入手，希望通过练习可以让大家掌握基本的递归算法，后面打算总结一些复杂的递归的练习，跟着大家一起学习递归之美。
1. Greatest common divisor
问题描述
- desc
Find the greatest common divisor of two positive integers.
The integers can be large, so you need to find a clever solution.
The inputs x and y are always greater or equal to 1, so the greatest
common divisor will always be an integer that is also greater or equal to 1.
- e.g
gcd(1, 3) = 1;
gcd(60, 12) = 12;
gcd(1590771464, 1590771620) = 4;
Solution
- 递归解答
long long gcd(long long x, long long y) {
return y == 0 ? x : mygcd(y, x%y);
}
顺便说一下，上面用到地算法叫欧几里得算法，不熟悉的同学可以上网查一下。
- 模板编程
除了经常使用的递归算法计算最大公约数，在C++中我们也可以使用模板编程计算两个整数的最大公约数，上代码。
template <long long V>
struct gcd {
static const long long value = V;
};
template <long long x, long long y>
struct gcd {
static const long long value = gcd<y, x%y>::value;
};
- usage
void test_gcd() {
auto v = gcd<20, 40>::value;
}
2. Sum of the odd digits of a number
- desc
Write a recursive function that returns the sum of the odd digits of a number.
For example, for the input number 321 the function will return 4,
and for the input 28 it will return 0.
- e.g
321 => 3 + 1 = 4
28 => 0
Solution
- 递归解答
int sum_odd_digits(int n) {
if (n == 0) return 0;
auto sum = 0;
auto r = n % 10;
if (r % 2 != 0) {
sum = sum + r;
}
return sum + sum_odd_digits(n / 10);
}
- 简化递归写法
上述的写法可以简化一下，用下面的方式表达，同样的功能效果。
int sum_odd_digits(int n) {
if (n == 0) return 0;
int digit = n % 10;
return digit % 2 * digit + sum_odd_digits(n / 10);
}
实现同样的算法，我们通常追求更见简短的代码，用越少的代码元素去实现相同的代码功能。
- 引入辅助函数
int sum_odd_digits(int n, int res) {
return n > 0 ? sum_odd_digits(n / 10, res + (n % 2 ? n % 10 : 0)) : res;
}
int sum_odd_digits(int n) {
return sum_odd_digits(n, 0);
}
和第二个想比，貌似并没有简化。。。
