递归的三定律

• 递归算法必须具有基本情况

• 递归算法必须向基本情况靠近

• 递归算法必须以递归方式调用自身

进制转换

以 10 进制数 996 为例，以 10 为进制，计算转换后的结果。先整除 10， 余数 6，商 99，余数小于 10，可以直接求得其字符 “6”，商 99 小于 996，在向基本情况靠 近。接着再递归调用自身，把前面计算得到的商 99 除以 10，再得 商 9 余 9，余数小于 10，转换为字符“9”，继续把剩下的商 9 除以 10，计算再得到最后的余数 “9”，最终得到 996 的 10 进制字符串 “996”。

// 10进制转其它进制
// 最多16进制，共有16位
const BASESTR: [&str; 16] = [
    "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F",
];

fn num2str_rec(num: i32, base: i32) -> String {
    if num < base {
        BASESTR[num as usize].to_string()
    } else {
        num2str_rec(num / base, base) + BASESTR[(num % base) as usize]
    }
}

fn main() {
  println!("{:?}", num2str_rec(996, 8)); // "1744"
  println!("{:?}", num2str_rec(996, 16)); // "3E4"
  println!("{:?}", num2str_rec(10, 2)); // "1010"
}

以二进制为例，计算过程如下

动态规划