Java教程

算法总结——递归

本文主要是介绍算法总结——递归,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录

一、递归定义

百度百科

其他

二、循环与递归

三、几个经典题

斐波那契数

题目

基本思路

递归解法

动态规划解法 

 汉诺塔

题目 

基本思路


一、递归定义

百度百科

递归,就是在运行的过程中调用自己。

函数嵌套调用过程示例

构成递归需具备的条件:

1. 子问题须与原始问题为同样的事,且更为简单;

2. 不能无限制地调用本身,须有个出口,化简为非递归状况处理。

其他

递归是一种解决问题的有效方法,在递归过程中,函数将自身作为子例程调用。

你可能想知道如何实现调用自身的函数。诀窍在于,每当递归函数调用自身时,它都会将给定的问题拆解为子问题。递归调用继续进行,直到到子问题无需进一步递归就可以解决的地步。

为了确保递归函数不会导致无限循环,它应具有以下属性:

  • 一个简单的基本案例 —— 能够不使用递归来产生答案的终止方案。
  • 一组规则,也称作递推关系,可将所有其他情况拆分到基本案例。

二、循环与递归

举个栗子,你用你手中的钥匙打开一扇门,结果去发现前方还有一扇门,紧接着你又用钥匙打开了这扇门,然后你又看到一扇们...但是当你开到某扇门时,发现前方是一堵墙无路可走了,你选择原路返回——这就是递归

但是如果你打开一扇门后,同样发现前方也有一扇们,紧接着你又打开下一扇门...直到打开最后一扇门出去,或者一直没有碰到尽头 (死循环)——这就是循环。

三、几个经典题

斐波那契数

题目

大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。

f(n) = f(n-1) + f(n-2)

基本思路

上面那个链接可以用递归求解

这道题在剑指offer中实际是当作递归的反例来说的。(用动态规划来解)

递归的本质是吧一个问题分解成两个或者多个小问题,如果多个小问题存在互相重叠的情况,那么就存在重复计算。

f(n) = f(n-1) + f(n-2)这种拆分使用递归是典型的存在重叠的情况,所以会造成非常多的重复计算。

另外,每一次函数调用爱内存中都需要分配空间,每个进程的栈的容量是有限的,递归层次过多,就会造成栈溢出。

递归是从最大数开始,不断拆解成小的数计算,如果不去考虑递归,我们只需要从小数开始算起,从底层不断往上累加就可以了,其实思路也很简单。

递归解法

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    if(n<=1){
        return n
    }
    return fib(n-1)+fib(n-2)
};

动态规划解法 

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    if(n<=1){
        return n
    }
    let pre=0,current=1,result=0,i=1
    while(i++<n){
        result=pre+current
        pre=current
        current=result
    }
    return result
};

 汉诺塔

题目 

在经典汉诺塔问题中,有 3 根柱子及 N 个不同大小的穿孔圆盘,盘子可以滑入任意一根柱子。一开始,所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。

请编写程序,用栈将所有盘子从第一根柱子移到最后一根柱子。

你需要原地修改栈。

基本思路

采用递归的思路
三要素如下:
递归结束条件:只剩下最后一个盘子需要移动
递归函数主功能:
1.首先将 n-1 个盘子,从第一个柱子移动到第二个柱子
2.然后将最后一个盘子移动到第三个柱子上
3.最后将第二个柱子上的 n-1 个盘子,移动到第三个柱子上
函数的等价关系式:
f(A,B,C,n) 表示将n个盘子从A移动到C
f(A,B,C,n)=f(A,C,B,n-1)+f(A,B,C,1)+f(B,A,C,n-1)

/**
 * @param {number[]} A
 * @param {number[]} B
 * @param {number[]} C
 * @return {void} Do not return anything, modify C in-place instead.
 */
var hanota = function(A, B, C) {
    let n=A.length
    return move(A,B,C,n)
};
function move(A,B,C,n){
    if(n===0) return;
    move(A,C,B,n-1)
    C.push(A.pop())
    move(B,A,C,n-1)
}

这篇关于算法总结——递归的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!