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

心已赠人 2021-09-18 04:50 158阅读 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 条评论，158人围观）

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

相关阅读

相关 C++递归使用

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

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

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

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

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

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

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

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

相关递归——线性递归与二分递归

递归线性递归例子1：数组求和 int sum( int A[], int n) { //数组求和算法：线性递归版 if

向右看齐/ 2022年05月21日 04:41/ 0 赞/ 249 阅读

相关三人行

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

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

相关递归的使用

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

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

相关递归的使用

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

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

相关 day 5：递归与全排列

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

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

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

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

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

相关递归的定义？何时使用递归？递归模型？递归执行过程？常见的递归思想的例题和实现？

递归递归定义：递归是指函数的定义中又调用函数自身的方法。例题求n（n为正整数）的阶乘 int fun(int n){

我会带着你远行/ 2021年07月24日 13:37/ 0 赞/ 376 阅读