算法基础——10个常见编程面试题
准备编程面试需要大量的时间。候选人需要学习不同的编码原理、数据结构和算法。递归算法（Recursion）是最重要的算法之一。因为它是许多重要算法的基础，例如分治算法（Divide-and-Conquer Algorithm）、图解算法（Graph Algorithms）、动态规划（Dynamic Programming）、一些基于树的搜索和排序算法等。面试中一定会出现这些算法，所以，在进行编程面试之前反复练习非常重要。
本文将重点讨论基本编程面试中常见的有关递归的基本问题。如果在 Google 中搜索，你会发现这些问题经常出现。本文整理了一些常见的面试问题，你将了解不同的递归算法（Recursion Algorithm）问题，供你练习！如果你想了解更多数据分析相关内容，可以阅读以下这些文章：
Classification Algorithm 101: 一小时学会机器学习的分类算法
如何在分类算法中使用逻辑回归
5种机器学习的分类器算法
支付算法化–算法对支付产业的影响
本文将从易到难，为你讲述面试中的编程问题。本文不是递归算法教程，只提供练习的资源。因为我经常使用 python，我同时会提供Python解决方案。
我建议你先尝试自己解决所有问题，然后再看解决方案。
问题 1
编写一个递归函数，取一个数并返回从0到该数的所有数的总和。
我称该函数为“累积函数(Cumulative Function)”。如果我输入 10 ，该函数将返回从 0 到 10 的所有数字的总和，即 55。
以下为Python解决方案：
def cumulative(num):
if num in [0, 1]:
return num
else:
return num + cumulative(num-1)问题2
编写一个递归函数，输入一个数字,并返回该数的阶乘（factorial）。
我们都学过阶乘。我称此函数命为“阶乘函数（Factorial Function）”。
以下为Python解决方案：
def factorial(n):
assert n >=0 and int(n) == n, 'The number must be a positive integer only!'
if n in [0,1]:
return 1
else:
return n * factorial(n-1)问题 3
编写一个递归函数，输入数字“n”并返回第n个斐波那契数。
提醒一下，斐波那契数列是以 0 和 1 开头的正整数序列，其余数字是前两个数字之和：0、1、1、2、3、5、8、11……
以下为Python解决方案：
def fibonacci(n):
if n in [0, 1]:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)问题 4
编写一个递归函数，输入一列数字，并返回列表中所有数字乘积。
如果你不用 Python，Python 中的list就像 Java 或 JavaScript 或 PHP 中的array。
以下为Python解决方案：
def productOfArray(arr):
if len(arr) == 0:
return 0
if len(arr) == 1:
return arr[0]
else:
return arr[len(arr)-1] * productOfArray(arr[:len(arr)-1])问题 5
编写一个函数，接收字符串，并在该字符串是回文时返回。
提醒一下，如果一个字符串反过来写还是相同，则称为回文。比如Madam，Civic，Kayak。颠倒这些词中的任何一个，意思都将保持不变。
以下为python中的递归解决方案：
def isPalindrom(strng):
if len(strng) == 0:
return True
if strng[0] != strng[len(strng)-1]:
return False
return isPalindrome(strng[1:-1])如果字符串是回文，则此函数返回 True，否则返回 False。
问题 6
编写一个递归函数，接收字符串并反转该字符串。
如果输入“amazing”，该函数应返回“gnizama”。
以下为Python解决方案：
def reverse(st):
if len(st) in [0, 1]:
return st
else:
return st[len(st)-1] + reverse(st[:len(st)-1])问题 7
编写一个递归函数，接收一个可能包含更多数组的数组，并返回一个所有值平化的数组。
假设输入以下数组：
[[1], [2, 3], [4], [3, [2, 4]]]输出应该为：
[1, 2, 3, 4, 3, 2, 4]以下为Python解决方案：
def flatten(arr):
res = []
for i in arr:
if type(i) is list:
res.extend(flatten(i))
else:
res.append(i)
return res问题 8
编写一个递归函数，接收一个单词数组，并返回一个包含所有大写单词的数组。
输入以下数组：
['foo', 'bar', 'world', 'hello']输出数组应该为：
['FOO', 'BAR', 'WORLD', 'HELLO']以下为Python解决方案：
def capitalizeWords(arr):
if len(arr) == 0:
return []
else:
return [arr[0].upper()]+capitalizeWords(arr[1:])问题 9
编写一个递归函数，接收一个数组和一个回调函数（Callback Function），如果该数组的值从该回调函数，返回 True，否则返回 False。
在该解决方案中，我使用函数“isEven”作为回调函数，如果数字是偶数，则返回 True，否则返回 False。
以下为回调函数：
def isEven(num):
if num%2==0:
return True
else:
return False如果输入数组的一个元素从“isEven”函数返回 True，主递归函数应该返回 True，否则返回 False。以下是一个数组：
[1, 2, 3, 5]递归函数在这里应该返回 True，因为该数组有一个元素是偶数。
以下为Python解决方案：
def anyEven(arr, cb):
if len(arr) == 0:
return False
if cb(arr[0]):
return True
return anyEven(arr[1:], cb)问题 10
编写一个递归函数，返回字典中所有正数之和，字典中可能包含更多字典。
具体见下例：
obj = {
"a": 2,
"b": {"x": 2, "y": {"foo": 3, "z": {"bar": 2}}},
"c": {"p": {"h": 2, "r": 5}, "q": 'ball', "r": 5},
"d": 1,
"e": {"nn": {"lil": 2}, "mm": 'car'}该函数应该返回 10。因为该字典包含五个 2， 没有其他偶数。
以下为Python解决方案：
def evenSum(obj, sum=0):
for k in obj.values():
if type(k) == int and k%2 ==0:
sum += k
elif isinstance(k, dict):
sum += evenSum(k, sum=0)
return sum结论
只有通过大量练习，才能擅长递归函数。但在面试之前，了解上述问题没有什么坏处。没有人能完全押对面试问题，但准备不同的编程问题非常关键。而且截至目前，我从来没有在面试中遇到过特别棘手的问题。面试官通常会提问一些测试基础知识以及解决方案的问题，从而了解你的整体思路。
感谢你的阅读！希望这些关于递归函数的面试题，能对你学习算法有所帮助。你还可以订阅我们的YouTube频道，观看大量数据科学相关公开课：https://www.youtube.com/channel/UCa8NLpvi70mHVsW4J_x9OeQ；在LinkedIn上关注我们，扩展你的人际网络！https://www.linkedin.com/company/dataapplab/
原文作者：Rashida Nasrin Sucky
翻译作者：Lia
美工编辑：过儿
校对审稿：Jiawei Tong
原文链接：https://towardsdatascience.com/10-popular-coding-interview-questions-on-recursion-2ddd8aa86039
