Day6 递归：使用三行代码找到推荐人

心已赠人 2021-09-18 04:50 222阅读 0赞

主题：递归

递归是一种编程技巧，比如在 DFS 和 前中后序二叉树遍历中，都使用了递归的思想。

--------------------

**使用递归需要满足的是三个条件：**

1.  一个问题的解可以分解为几个问题的解
2.  这个问题和分解之后的子问题，处理数据规模的不同，求解的思路是相同的
3.  存在递归的终止条件

--------------------

**如何写出递归代码：**

数学归纳法，找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，找出递归的终止条件。

**注意**

1.  递归代码要警惕堆栈溢出，即 StackOverflowError，解决方法可以设置最大的递归深度
2.  递归代码要避免重复计算，可以借助散列表避免重复计算

**示例：**  
n 个台阶，每次只能跨 1 个或者 2 个台阶，问共有几种跨法？

1.  总结规律  
    f(0) = 0;  
    f(1) = 1;  
    f(2) = 2; // 1,1 2  
    f(3) = 3; // 1,2 2,1 1,1,1  
    f(4) = 5; // 1,1,1,1 1,1,2 1,2,1 2,2  
    …  
    f(n) = f(n-1) + f(n-2)
2.  找到终止条件  
    终止条件是 n=1 和 n = 2 的时候

funciton (int n) {
    	if (n == 1) return 1;
    	if (n == 2) return 2;
    	return f (n-1) + f (n-2);
    }

但是这种计算方式正如上边所说的，会重复计算。比如 f(5) = f(4) + f(3)  
, f(4) = f(3) + f(2)，这里 f(3) 计算了两次。所以可以借用哈希表来避免重复计算。

function (int n) {
    	if(n == 1) return 1;
    	if(n == 2) return 2;
    	if(map.containsKey(n)) return map.get(n);
    	int ret = f(n-1) + f(n-2);
    	map.put(n, ret);
    	return ret;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，222人围观）

还没有评论，来说两句吧...

相关阅读

相关 C++递归使用

首先来谈谈常规的递归概念，递归递归先递后归。指的是我问你，你问他，他问下一个人这样层层递进直到得知结果并返回的过程。因此递归作为一种[算法][Link 1]在[程序设计语][

矫情吗；*/ 2024年03月16日 22:54/ 0 赞/ 86 阅读

相关 linux 递归显示代码,linux-find【递归搜索文件名】(示例代码)

1 命令格式： $ find 最常见示例：查找文件名(忽略大小写) $find . -iname sqlquery.java 1.1 ：所要搜索的目录及其所有子目录

以你之姓@/ 2023年01月21日 11:18/ 0 赞/ 20 阅读

相关 2021-05-15 递归：如何用三行代码找到“最终推荐人”

如何理解“递归”？去的过程叫递，回来的过程叫归；所有的递归问题都可以用递归公式来解决；举例 int f(int n) { if (n

雨点打透心脏的1/2处/ 2023年01月21日 06:28/ 0 赞/ 16 阅读

相关如何用三行代码找到“最终推荐人“

一概述推荐注册反佣金是近几年比较常见的功能，很多App都有这个功能。这个功能中，用户A推荐用户B来注册，用户B又注册了用户C来注册。此时的用户C的"最终推荐人"为用户

傷城~/ 2022年12月11日 13:57/ 0 赞/ 121 阅读

相关 linux统计文件行数_递归方法统计文件夹代码行数

![11ef52c151c9d736a679449a374905fe.png][] 源码如下： import java.io.BufferedReader;

骑猪看日落/ 2022年10月25日 14:07/ 0 赞/ 339 阅读

相关三人行

子曰：“三人行，必有我师焉。择其善者而从之，其不善者而改之。” 本题给定甲、乙、丙三个人的能力值关系为：甲的能力值确定是 2 位正整数；把甲的能力值的 2 个数字调换位置就是

客官°小女子只卖身不卖艺/ 2022年05月14日 13:56/ 0 赞/ 175 阅读

相关递归的使用

package com.liaojianya.chapter1; / This program demonstrates the use of re

秒速五厘米/ 2022年01月10日 06:47/ 0 赞/ 238 阅读

相关递归的使用

关于递归，自我理解就是，需要一层一层的去分析，然后倒着写出来就好了 ![1611686-20190611102812465-623624649.png][] 转载于:htt

我就是我/ 2021年11月01日 04:31/ 0 赞/ 307 阅读

相关 day 5：递归与全排列

day 5：递归与全排列今天感觉讲的还是挺简单的，就是通过全排列的案例，让我们了解递归，但是感觉如果在比赛的时候，恐怕我还是会用C++的全排列函数，而不会用递归虽然

痛定思痛。/ 2021年10月30日 02:52/ 0 赞/ 185 阅读

相关 Day6 递归：使用三行代码找到推荐人

主题：递归递归是一种编程技巧，比如在 DFS 和前中后序二叉树遍历中，都使用了递归的思想。 -------------------- 使用递归需要满足的是三个条件：

心已赠人/ 2021年09月18日 04:50/ 0 赞/ 223 阅读