學(xué)而不思則罔姨蝴，思而不學(xué)則殆
伊始
遞歸在現(xiàn)實(shí)世界無處不在肺缕，在代碼中使用遞歸搓谆，是為了更好更直觀地描述現(xiàn)實(shí)世界。
本篇開始我們先從基本簡單的遞歸算法練習(xí)入手泉手，希望通過練習(xí)可以讓大家掌握基本的遞歸算法，后面打算總結(jié)一些復(fù)雜的遞歸的練習(xí)缝裤，跟著大家一起學(xué)習(xí)遞歸之美。
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);
}
順便說一下霎苗，上面用到地算法叫歐幾里得算法榛做，不熟悉的同學(xué)可以上網(wǎng)查一下。
- 模板編程
除了經(jīng)常使用的遞歸算法計(jì)算最大公約數(shù)厘擂，在C++中我們也可以使用模板編程計(jì)算兩個整數(shù)的最大公約數(shù)锰瘸，上代碼。
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);
}
- 簡化遞歸寫法
上述的寫法可以簡化一下舞萄，用下面的方式表達(dá)管削，同樣的功能效果。
int sum_odd_digits(int n) {
if (n == 0) return 0;
int digit = n % 10;
return digit % 2 * digit + sum_odd_digits(n / 10);
}
實(shí)現(xiàn)同樣的算法把还，我們通常追求更見簡短的代碼茸俭，用越少的代碼元素去實(shí)現(xiàn)相同的代碼功能安皱。
- 引入輔助函數(shù)
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);
}
和第二個想比酌伊，貌似并沒有簡化。居砖。。
