面试中遇到递归算法题别慌--常见递归算法题的解题思路

前几天在博客园看到有人面试时，遇到递归算法题，一时手痒就解了一个。顺便网上又找来几个，也实现了。给大家分享一下，开阔一下思路，没准你明天面试就能用上。

1、编写一个方法用于验证指定的字符串是否为反转字符，返回true和false。请用递归算法实现。（反转字符串样式为"abcdedcba"）

2、一列数的规则如下: 1、1、2、3、5、8、13、21、34...... 求第30个是多少

3、一列数的规则如下: 1、12、123、1234、12345、123456......,求第n个数的递归算法（n<=9）。
4、将一整数逆序，如987654321变为123456789。

5、一个射击运动员打靶,靶一共有10环,连开10枪打中90环的可能行有多少种?

以上的前提：不能用数组 或转成字符串处理，也不能用内置函数，如C#的幂函数(Math.Pow)

namespace RecursionAlgorithms { class Program { private static bool fn1(ref string str, ref int from, ref int to) { if (from >= to) return true; if (str[from++] != str[to--]) return false; return fn1(ref str, ref from, ref to); } private static int fn2(int i) { return i <= 2 ? 1 : fn2(i - 2) + fn2(i - 1); } private static long fn3(long x, ref long n) { return (x <= 1) ? x : fn3(x - 1, ref n) + x * (n *= 10); } private static long fn4(long x, ref long n) { return (x < 10) ? x : fn4(x / 10, ref n) + (x % 10) * (n *= 10); } private static long fn5(int n, int sum) { if ((n == 1 && sum <= 10) || (sum == n * 10)) return 1; if (sum > n * 10 || sum < 0) return 0; long ok = 0; for (int i = 0; i <= 10; i++) { ok += fn5(n - 1, sum - i); } return ok; } static void Main(string[] args) { string[] strs = { "", "a", "aa", "aba", "abba", "abcba", "ab", "abc", "abca" }; for (int i = 0; i < strs.Length; i++) { string str = strs[i]; int from = 0, to = str.Length - 1; Console.WriteLine("{0} is {1}", str, fn1(ref str, ref from, ref to)); } for (int i = 1; i <= 30; i++) Console.Write("{0}:{1} /t", i, fn2(i)); long n = 1, m = 1, t = 0; for (int i = 0; i <= 9; i++, n = m = 1) { Console.Write("/n {0} ==> {1}", t = fn3(i, ref n), fn4(t, ref m)); } Console.WriteLine("/n{0}种可能性", fn5(10, 90)); } } } 

递归算法很有意思的，并不是说函数调用自身就一定是递归算法。有一次我做面试官，有一童鞋在一道简单的递归函数中，还用到了for循环，当场被我Pass（当然还有其他因素）

总结一下递归算法的解题思路：

首先步骤分解，写出最后一次递归（n=1）的计算公式，然后是倒数第二次（n=2），n=3....，最后归纳出递归算法

如第二题：fn(1)=1；f(2)=1；f(3)=f(1)+f(2)；----> f(n)=f(n-2)+f(1)，那么很容易就写出这个递归函数

f(n)={n<=2?1:fn(n-2)+f(n-1)}

最后

以上就是缓慢萝莉最近收集整理的关于面试中遇到递归算法题别慌--常见递归算法题的解题思路的全部内容，更多相关面试中遇到递归算法题别慌--常见递归算法题内容请搜索靠谱客的其他文章。