今日份知识你摄入了么？
准备编程面试需要大量的时间。候选人需要学习不同的编码原理、数据结构和算法。递归算法（Recursion）是最重要的算法之一。
因为它是许多重要算法的基础，例如分治算法
（Divide-and-Conquer Algorithm）
、图解算法
（Graph Algorithms）
、动态规划
（Dynamic Programming）
、一些基于树的搜索和排序算法等。面试中一定会出现这些算法，所以，在进行编程面试之前反复练习非常重要。

本文将重点讨论基本编程面试中常见的有关递归的基本问题。
如果在 Google 中搜索，你会发现这些问题经常出现。本文整理了一些常见的面试问题，你将了解不同的递归算法
（Recursion Algorithm）
问题，供你练习！

本文将从易到难，为你讲述面试中的编程问题。本文不是递归算法教程，只提供练习的资源。因为我经常使用 python，我同时会提供Python解决方案。

我建议你先尝试自己解决所有问题，然后再看解决方案。
问题 1
编写一个递归函数，取一个数并返回从0到该数的所有数的总和。

我称该函数为“累积函数(Cumulative Function)”。如果我输入 10 ，该函数将返回从 0 到 10 的所有数字的总和，即 55。
以下为Python解决方案：
问题2
编写一个递归函数，输入一个数字,并返回该数的阶乘
（factorial）
。

我们都学过阶乘。我称此函数命为“阶乘函数（Factorial Function）”。
以下为Python解决方案：
问题 3
编写一个递归函数，输入数字“n”并返回第n个斐波那契数。
提醒一下，斐波那契数列是以 0 和 1 开头的正整数序列，其余数字是前两个数字之和：0、1、1、2、3、5、8、11……
以下为Python解决方案：
问题 4
编写一个递归函数，输入一列数字，并返回列表中所有数字乘积。

如果你不用 Python，Python 中的list就像 Java 或 JavaScript 或 PHP 中的array。
以下为Python解决方案：
问题 5
编写一个函数，接收字符串，并在该字符串是回文时返回。

提醒一下，如果一个字符串反过来写还是相同，则称为回文。比如Madam，Civic，Kayak。颠倒这些词中的任何一个，意思都将保持不变。
以下为python中的递归解决方案：
如果字符串是回文，则此函数返回 True，否则返回 False。
问题 6
编写一个递归函数，接收字符串并反转该字符串。

如果输入“amazing”，该函数应返回“gnizama”。
以下为Python解决方案：
问题 7
编写一个递归函数，接收一个可能包含更多数组的数组，并返回一个所有值平化的数组。

假设输入以下数组：
输出应该为：
以下为Python解决方案：
问题 8
编写一个递归函数，接收一个单词数组，并返回一个包含所有大写单词的数组。
输入以下数组：
输出数组应该为：
以下为Python解决方案：
问题 9
编写一个递归函数，接收一个数组和一个回调函数
（Callback Function）
，如果该数组的值从该回调函数，返回 True，否则返回 False。

在该解决方案中，我使用函数“isEven”作为回调函数，如果数字是偶数，则返回 True，否则返回 False。
以下为回调函数：
如果输入数组的一个元素从“isEven”函数返回 True，主递归函数应该返回 True，否则返回 False。以下是一个数组：
递归函数在这里应该返回 True，因为该数组有一个元素是偶数。

以下为Python解决方案：
问题 10
编写一个递归函数，返回字典中所有正数之和，字典中可能包含更多字典。

具体见下例：
该函数应该返回 10。因为该字典包含五个 2， 没有其他偶数。

以下为Python解决方案：
结论
只有通过大量练习，才能擅长递归函数。但在面试之前，了解上述问题没有什么坏处。没有人能完全押对面试问题，但准备不同的编程问题非常关键。而且截至目前，我从来没有在面试中遇到过特别棘手的问题。面试官通常会提问一些测试基础知识以及解决方案的问题，从而了解你的整体思路。
感谢你的阅读！希望这些关于递归函数的面试题，能对你学习算法有所帮助。
原文作者：Rashida Nasrin Sucky
翻译作者：Lia
美工编辑：过儿
校对审稿：Jiawei Tong
原文链接：https://towardsdatascience.com/10-popular-coding-interview-questions-on-recursion-2ddd8aa86039
公开课预告

往期精彩回顾

如何征服数据科学面试中的Python编程考试
DataJob入门 — 在 AWS 上构建和部署无服务器数据管道
展望2022 年，这些数据产品会引领潮流
如何开发群组分析（Cohort Analysis）的数据APP
Classification Algorithm 101: 一小时学会机器学习的分类算法


点「在看」的人都变好看了哦
点击“阅读原文”查看数据应用学院核心课程
继续阅读
阅读原文