数据结构与算法 | 递归及递归常见面试题
程序员文章站
2024-03-16 15:00:04
...
一、递归的概念
递归是一个函数直接或间接地调用自身,是为直接或间接递归。
- 递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。
- 用递归需要注意以下两点:(1) 递归就是在过程或函数里调用自身。(2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。
- 尾递归:尾递归就是从最后开始计算,每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量。
二、面试题
1、求斐波那契数列的第n项。
常规求解:
long long Fibonacci(int n)
{
if(n<=0)
return 0;
if(n=1)
return 1;
return Fibonacci(n-1)+Fibonacci(n-2);
}
采用尾递归方法:
// res1和res2的初始值为0,1.
long long Fibonacci(int n,int res1,int res2)
{
if(n=0)
return res1;
return Fibonacci(n-1,res2,res1+res2);
}
2、青蛙跳台阶问题:一只青蛙能一次可以跳一级或二级,求上n级台阶有多少种算法。
由题可知n=1,f(n)=1;n=2,f(n)=2;n>=3,f(n)=f(n-1)+f(n-2).
int FN(int n)
{
if(n=1)
return 1;
if(n=2)
return 2;
return FN(n-1)+FN(n-2);
}
3、leetcode687最长同值路径
给定一个二叉树,找到最长的路径,这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意:两个节点之间的路径长度由它们之间的边数表示。
示例 1:
输入:
5
/ \
4 5
/ \ \
1 1 5
输出:2
示例 2:
输入:
1
/ \
4 5
/ \ \
4 4 5
输出:2
class Solution {
public:
int maxL = 0;
int getMax(TreeNode* root, int val){
if(root==NULL)
return 0;
int left = getMax(root->left, root->val);
int right = getMax(root->right, root->val);
maxL = max(maxL, left+right);
if(root->val==val)
return max(left, right)+1;
return 0;
}
int longestUnivaluePath(TreeNode* root) {
if(!root)
return 0;
getMax(root, root->val);
return maxL;
}
};