精华内容
下载资源
问答
  • 递归函数正确思维方法

    分享一下我老师大神的人工智能教程!零基础,通俗易懂!http://blog.csdn.net/jiangjunshow

    也欢迎大家转载本篇文章。分享知识,造福人民,实现我们中华民族伟大复兴!

                   

    递归是编程中一个相对难以理解但是却又很重要的概念. 对于从命令式语言开始学习编程的程序员天生对此有理解缺陷, 而对于从类似C++这种对函数式编程范式不友好的语言开始学习编程的程序员就更加如此了.(比如我自己) 碰巧(其实不巧)最近在读这本书(这本书国内没有引进, 网上只有巨贵的亚马逊卖的原版, 我读的是网上的中文版), Paul Graham在书中讲述的如何写递归函数的部分, 让我印象深刻. 因为原书是讲Lisp的, 当然这个部分也是用Lisp作为例子描述的, 考虑到国内会看这本书的人太少, 能看懂Lisp的就更不多了, 我这里根据自己的理解, 重新整理一下. 最重要的是, 书中原来的例子太少, 太简单, 我自己提供了一些额外的, 并且更加复杂的例子. 以期对问题能有更好的理解.

    什么是递归

    迭代的是人,递归的是神
    –L. Peter Deutsch

    简单的定义: “当函数直接或者间接调用自己时,则发生了递归.” 说起来简单, 但是理解起来复杂, 因为递归并不直观, 也不符合我们的思维习惯, 相对于递归, 我们更加容易理解迭代. 因为我们日常生活中的思维方式就是一步接一步的, 并且能够理解一件事情做了N遍这个概念. 而我们日常生活中几乎不会有递归思维的出现.
    举个简单的例子, 即在C/C++中计算一个字符串的长度. 下面是传统的方式, 我们一般都这样通过迭代来计算长度, 也很好理解.

    size_t length(const char *str) {  size_t length = 0;  while (*str != 0) {    ++length;    ++str;  }  return length;}

    而事实上, 我们也可以通过递归来完成这样的任务.

    size_t length(const char *str) {  if (*str == 0) {    return 0;  }  return length(++str) + 1;}

    只不过, 我们都不这么做罢了, 虽然这样的实现有的时候可能代码更短, 但是很明显, 从思维上来说更加难以理解一些. 当然, 我是说假如你不是习惯于函数式语言的话. 这个例子相对简单, 稍微看一下还是能明白吧.
    迭代的算法可以这样描述: 从第一个字符开始判断字符串的每一个字符, 当该字符不为0的时候, 该字符串的长度加一.
    递归的算法可以这样描述: 当前字符串的长度等于当前字符串除了首字符后, 剩下的字符串长度+1.
    作为这么简单的例子, 两种算法其实大同小异, 虽然我们习惯迭代, 但是, 也能看到, 递归的算法无论是从描述上还是实际实现上, 并不比迭代要麻烦.

    理解递归

    在初学递归的时候, 看到一个递归实现, 我们总是难免陷入不停的回溯验证之中, 因为回溯就像反过来思考迭代, 这是我们习惯的思维方式, 但是实际上递归不需要这样来验证. 比如, 另外一个常见的例子是阶乘的计算. 阶乘的定义: “一个正整数的阶乘(英语:factorial)是所有小于或等于该数的正整数的积,并且0的阶乘为1。” 以下是Ruby的实现:

    def factorial(n)   if n <= 1 then    return 1  else    return n * factorial(n - 1)  endend

    我们怎么判断这个阶乘的递归计算是否是正确的呢? 先别说测试, 我说我们读代码的时候怎么判断呢?
    回溯的思考方式是这么验证的, 比如当n = 4时, 那么factoria(4)等于4 * factoria(3), 而factoria(3)等于3 * factoria(2)factoria(2)等于2 * factoria(1), 等于2 * 1, 所以factoria(4)等于4 * 3 * 2 * 1. 这个结果正好等于阶乘4的迭代定义.
    用回溯的方式思考虽然可以验证当n = 某个较小数值是否正确, 但是其实无益于理解.
    Paul Graham提到一种方法, 给我很大启发, 该方法如下:

    1. 当n=0, 1的时候, 结果正确.
    2. 假设函数对于n是正确的, 函数对n+1结果也正确.
      如果这两点是成立的,我们知道这个函数对于所有可能的n都是正确的。

    这种方法很像数学归纳法, 也是递归正确的思考方式, 事实上, 阶乘的递归表达方式就是1!=1,n!=(n-1)!×n(见wiki). 当程序实现符合算法描述的时候, 程序自然对了, 假如还不对, 那是算法本身错了…… 相对来说, n,n+1的情况为通用情况, 虽然比较复杂, 但是还能理解, 最重要的, 也是最容易被新手忽略的问题在于第1点, 也就是基本用例(base case)要对. 比如, 上例中, 我们去掉if n <= 1的判断后, 代码会进入死循环, 永远不会结束.

    使用递归

    既然递归比迭代要难以理解, 为啥我们还需要递归呢? 从上面的例子来看, 自然意义不大, 但是很多东西的确用递归思维会更加简单……
    经典的例子就是斐波那契数列, 在数学上, 斐波那契数列就是用递归来定义的:

    ·F0 = 0
    ·F1 = 1 
    ·Fn = Fn – 1 + Fn – 2

    有了递归的算法, 用程序实现实在再简单不过了:

    def fibonacci(n)  if n == 0 then    return 0  elsif n == 1 then    return 1  else    return fibonacci(n - 1) + fibonacci(n - 2)  endend

    改为用迭代实现呢? 你可以试试.
    上面讲了怎么理解递归是正确的, 同时可以看到在有递归算法描述后, 其实程序很容易写, 那么最关键的问题就是, 我们怎么找到一个问题的递归算法呢?
    Paul Graham提到, 你只需要做两件事情:

    1. 你必须要示范如何解决问题的一般情况, 通过将问题切分成有限小并更小的子问题.
    2. 你必须要示范如何通过有限的步骤, 来解决最小的问题(基本用例).
      如果这两件事完成了, 那问题就解决了. 因为递归每次都将问题变得更小, 而一个有限的问题终究会被解决的, 而最小的问题仅需几个有限的步骤就能解决.

    这个过程还是数学归纳法的方法, 只不过和上面提到的一个是验证, 一个是证明.
    现在我们用这个方法来寻找汉诺塔这个游戏的解决方法.(这其实是数学家发明的游戏)

    有三根杆子A,B,C。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:
    1.每次只能移动一个圆盘.
    2.大盘不能叠在小盘上面.

    汉诺塔
    这个游戏在只有3个盘的时候玩起来较为简单, 盘越多, 就越难, 玩进去后, 你就会进入一种不停的通过回溯来推导下一步该干什么的状态, 这是比较难的. 我记得第一次碰到这个游戏好像是在大航海时代某一代游戏里面, 当时就觉得挺有意思的. 推荐大家都实际的玩一下这个游戏, 试试你脑袋能想清楚几个盘的情况.
    现在我们来应用Paul Graham的方法思考这个游戏.

    一般情况:
    当有N个圆盘在A上, 我们已经找到办法将其移到C杠上了, 我们怎么移动N+1个圆盘到C杠上呢? 很简单, 我们首先用将N个圆盘移动到C上的方法将N个圆盘都移动到B上, 然后再把第N+1个圆盘(最后一个)移动到C上, 再用同样的方法将在B杠上的N个圆盘移动到C上. 问题解决.

    基本用例:
    当有1个圆盘在A上, 我们直接把圆盘移动到C上即可.

    算法描述大概就是上面这样了, 其实也可以看作思维的过程, 相对来说还是比较自然的. 下面是Ruby解:

    def hanoi(n, from, to, other)  if n == 1 then    puts from + ' -> ' + to  else    hanoi(n-1, from, other, to)    hanoi(1, from, to, other)    hanoi(n-1, other, to, from)  endend

    当n=3时的输出:

    A -> C
    A -> B
    C -> B
    A -> C
    B -> A
    B -> C
    A -> C

    上述代码中, from, to, other的作用其实也就是提供一个杆子的替代符, 在n=1时, 其实也就相当于直接移动. 看起来这么复杂的问题, 其实用递归这么容易, 没有想到吧. 要是想用迭代来解决这个问题呢? 还是你自己试试吧, 你试的越多, 就能越体会到递归的好处.

    递归的问题

    当然, 这个世界上没有啥时万能的, 递归也不例外, 首先递归并不一定适用所有情况, 很多情况用迭代远远比用递归好了解, 其次, 相对来说, 递归的效率往往要低于迭代的实现, 同时, 内存好用也会更大, 虽然这个时候可以用尾递归来优化, 但是尾递归并不是一定能简单做到.

    参考

    1. Ansi Common Lisp
    2. 精通递归程序设计 
               

    给我老师的人工智能教程打call!http://blog.csdn.net/jiangjunshow

    这里写图片描述
    展开全文
  • 递归函数

    2017-10-27 09:56:32
    什么是递归:当函数直接或间接调用自己时,则发生递归。 在数学上,斐波纳契数列被以递归的方法定义:F(0)=0,F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*) 通过迭代计算斐波那契数列代码如下: def fibo(n): ...
    什么是递归:当函数直接或间接调用自己时,则发生递归。
    在数学上,斐波纳契数列被以递归的方法定义:F(0)=0,F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)
    通过迭代计算斐波那契数列代码如下:
    def fibo(n):
        befor = 1
        now = 0
        after = 0
        for i in range(n):
            after = now + befor
            befor = now
            now = after
        return now
    print(fibo(8))
    而通过递归来完成这个任务:
    def fibo(n):
        if n <= 2:
            return 1
        return fibo(n-2)+fibo(n-1)
    print(fibo(8))
    这样做代码更短,但也更难理解
    迭代的方法对斐波那契数列的描述为:F(-1)=1,F(0)=0,F(n)=F(n-1)+F(n-2) ,F(n+1)=F(n)+F(n-1)
    递归的方法对斐波那契数列的描述为:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)
    迭代方法的描述起来更像数学归纳法推理过程:
    递推的基础:证明当n=1时表达式成立。
    递推的依据:证明如果当n=m时成立,那么当n=m+1时同样成立。
    而递归方法描述起来更像是数学归纳法的结论。
    斐波纳契数列被以递归的方法定义,而它的描述看起来数学归纳法的结论,那么我们是不是可以用数学归纳法思考方式去思考递归?
    答案是肯定的。
    保罗·格雷厄姆(Paul Graham)在《ANSI Common Lisp》一书中提到, 关于递归你只需要做两件事情:
    1. 你必须要示范如何解决问题的一般情况, 通过将问题切分成有限小并更小的子问题.
    2. 你必须要示范如何通过有限的步骤, 来解决最小的问题(基本用例).
    3. 如果这两件事完成了, 那问题就解决了. 因为递归每次都将问题变得更小, 而一个有限的问题终究会被解决的, 而最小的问题仅需几个有限的步骤就能解决.
    这个描述像是数学归纳法换了种表述。
    递归的基础:证明当n=1时成立,但也是很容易被新人忽略的,如果去掉if n <= 2:的判断语句之后,代码就会陷入死循环。
    递归函数特点:
    1、自己直接(或间接)调用自己
    2、递归函数需要一个结束条件,不然代码会进入死循环
    3、但凡递归能做的循环一样可以做,只是有时候递归代码更简洁
    4、实现同样的功能,一般情况下递归的效率往往低于迭代的效率,且占用更多内存。
    5、一般情况下迭代远远比递归更好理解,所以通常推荐使用迭代方法
    引用:



    展开全文
  • 68_递归函数

    2020-08-28 15:14:31
    递归函数123使用递归计算n的阶乘结果(5!=5*4*3*2*1)测试递归算法树形递归(裴波那契)尾递归链表实现 68.递归函数 71 递归函数指的是:自己调用自己的函数,在函数体内部直接或间接的自己调用自己。递归类 似于...


    68.递归函数

    71

    递归函数指的是:自己调用自己的函数,在函数体内部直接或间接的自己调用自己。递归类 似于大家中学数学学习过的“数学归纳法”。 每个递归函数必须包含两个部分:

    1. 终止条件 表示递归什么时候结束。一般用于返回值,不再调用自己。
    2. 递归步骤 把第 n步的值和第 n-1步相关联

    递归函数由于会创建大量的函数对象、过量的消耗内存和运算能力。在处理大量数据时,谨 慎使用。

    【操作】 使用递归函数计算阶乘(factorial)

    1

    def factorial(n): 
        if n==1:return 1 
        return n*factorial(n-1)
        
    for i in range(1,6):
        print(i,'!=',factorial(i))
    
    

    执行结果:

    1 != 1
    2 != 2
    3 != 6 
    4 != 24 
    5 != 120
    
    In [15]: factorial(5)
    Out[15]: 120
    

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-euBXtjDV-1598595910190)(C20C98F8EB5A4027917A370A3DC54ECC)]


    2

    这种简单的只有一个调用的也可以叫做 线性迭代 递归

    #  递归函数         很重要
    # 就是自己直接调用自己的函数
    #  递归函数的基本原理   测试
    
    
    def test01(n):
        print('test01:', n)  # 倒着打 4, 3, 2, 1, 0
        if n == 0:
            print('over')
        else:
            test01(n-1)  # 递归调用   无限制的 调用自己  最后栈满了就报错了
        # 一般要设置一个停止条件,每个栈帧
          # 这样的话  这一行 就不会 执行了,每次都没执行完,就  又生成 新的栈帧
    # 递归的时候  栈先进后出  挂起的时候
        print('test01***', n)  # 这里是   over之后  那个时候 n=0  所以打印 0,1,2,3,4
    
    
    def test02():
        print('test02')
        test02() # 这里会 一直无限打印 test02  直到 超过最大递归深度
    
    
    test01(4)
    
    In [19]: test01(4)
    test01: 4
    test01: 3
    test01: 2
    test01: 1
    test01: 0
    over
    test01*** 0
    test01*** 1
    test01*** 2
    test01*** 3
    test01*** 4
    
    # 线性迭代公共模式  累加的公共模式
    def public_iter_summation(term, a, _next, b):
        def iter(a, result=0):
            if a <= b:
                return iter(_next(a), result + term(a)) # 这个 地方 改一下 就可以变为累乘
    
            return result
    
    
        return iter(a)
    
    
    public_iter_summation(lambda x: x, 1, lambda y: y + 1, 100) # 连续求自然数的和
    public_iter_summation(lambda x: x*x, 1, lambda y: y + 1, 10) # 平方和
    
    In [361]: public_iter_summation(lambda x: x, 1, lambda y: y + 1, 100) # 连续求自然数的和
    Out[361]: 5050
    
    In [362]: public_iter_summation(lambda x: x*x, 1, lambda y: y + 1, 10) # 平方和
    Out[362]: 385
    
    # 公共模式 累积的 另一种 线性迭代 
    # 添加了一个  combiner 参数  。 
    # 可以指定  是 加 还是减 还是其他的处理
    # 这里的概念 不仅仅是 递归了
    # 还涉及到了  高阶函数 之后 会详细 讲解。。
    # 高阶函数  就是将 函数最为 参数 传递
    def pub_accumulate_iter(a, b, term, _next,null_value,combiner):
        total, n = null_value, a
        while n <= b:
            # a = _next(n)  这一步直接省略掉 , 把 _next 直接放进去计算
            total,n=combiner(total, _next(n)),term(n)
             
            # a,total,n=[_next(n),combiner(total,a),term(n)] 结果 是6 错误的 序列解包,相同变量名字  会 因为变量名的关系, 会 少计算, 像下面那样写就可以
            # a = _next(n)
            # total, n = combiner(total, a), term(n) # 结果 24 正确
            
        return total
    
    
    pub_accumulate_iter(1,4,lambda x:x+1,lambda y:y,1,lambda g,b:g*b)
    # combiner 函数 就是 用来 控制  是 相加 还是相乘 还是 进行 其他操作。
    # 这里是 相乘
    # 也就是 求阶乘 这几个参数加起来。 1到 4 的阶乘 
    In [367]: pub_accumulate_iter(1,4,lambda x:x+1,lambda y:y,1,lambda g,b:g*b)
    Out[367]: 24
    

    3

    #  递归小练习  计算阶乘   例如 5*4*3*2*1
    
    #  可以去找 分形几何  来  练习递归
    
    def factorial(n):
        if n == 1:
            return 1
        else:
            return n*factorial(n-1)
    
    
    result = factorial(5)
    print(result)
    
    

    测试递归算法

    import shutil
    import os
    
    
    # 自己调用自己就是递归
    # coding=utf-8
    
    '''
    递归是一种常见的解决问题的方法,即把问题逐渐简单化。递归的基本思想就是“自己
    调用自己”,一个使用递归技术的方法将会直接或者间接的调用自己。
    利用递归可以用简单的程序来解决一些复杂的问题。比如:斐波那契数列的计算、汉诺
    塔、快排等问题。
    递归结构包括两个部分:
     定义递归头。解答:什么时候不调用自身方法。如果没有头,将陷入死循环,也就
    是递归的结束条件。
     递归体。解答:什么时候需要调用自身方法。
    
    '''
    
    
    
    num = 1
    
    
    def a1():
        global num  # 如果要在函数内改变全局变量的值,增加global关键字声明一下
        num += 1
        print("a1")
        if num < 3:
            a1()
    
    
    def b1():
        print("b1")
    
    
    a1() # 小于 3 所以 打了两次 a1 出来
    
    In [21]: a1()
    a1
    a1
    
    

    树形递归(裴波那契)

    数列:
    0,1,1,2,3,5,8,13,21.........
    fib(n)=fib(n-2)+fib(n-1)

    也就是说两个数的和 等于 后面一个数

    def fib(n):
        if n == 1:
            return 0
        if n == 2:
            return 1
        return fib(n - 2) + fib(n - 1) # 这里调用 了 两次 自己  所以 有重复
        # 要解决的话可以加缓存
    # 树形递归(裴波那契)
    def fib(n):
        if n == 1:
            return 0
        if n == 2:
            return 1
        return fib(n - 2) + fib(n - 1)
    
    
    # 记忆功能
    # 递归缓存
    # 这种方式可以有效提高树形 递归的 效率。
    
    def memo(f):
        """ 返回一个缓存版单参数函数 f """
        cache = {}
    
        def memoized(n):
            if n not in cache:
                cache[n] = f(n)
                # 如果 要计算的 n 不在缓存字典中
                # 那么 计算
                # 如果在里面那么 返回 对应的值 
                # 大家可以用timeit 测试下速度。
            return cache[n]
    
        return memoized
    
    
    fib(6)  # 5
    fib_memo = memo(fib)
    
    fib_memo(40)  # 63245986 
    

    在这里插入图片描述

    尾递归

    因为需要 写一个 链表实现。此代码才能使用 。

    不过 主要是看思路。

    暂时不推荐 学习链表实现。 代码 贴出来了。 后期可以过来 看看

    实际上尾递归 可以定义为
    总能在常量空间中执行迭代型计算过程,即使这一计算是一个递归过程描述的。 具有这一特性的实现称为 尾递归

    当你写出一个 线性迭代的递归过程或者说函数的时候,那么这个可以称为尾递归。

    因为始终会在 尾部进行某个 数据的累积。

    而不用等到 函数 return 之后,返回上一层函数 才拿到相应数据 进行计算。

    # 普通递归
    def _length_1(lst):
        if lst.empty:
            return 0
        else:
            return 1 + _length_1(lst.rest)
    
    def _length_2(lst):
    	# if lst.empty:
    	if lst is Link.empty:
        	return 0
        return _length_2(lst.rest)+1
    
    # 尾递归  此函数 可以使用
    def tail_length(lst):
        def length_helper(lst,length=0):
            if lst is Link.empty:
                return length
            else:
                length+=1
                return length_helper(lst.rest,length)
        return length_helper(lst)
    
    
    
    
    # ------------------- 测试运行 ----------------------------
    In [375]: lnk1=Link(1,Link(2))
    
    In [376]: lnk1.first
    Out[376]: 1
    
    In [377]: lnk1.rest.first
    Out[377]: 2
    
    In [378]: lnk1.rest.rest is Link.empty
    Out[378]: True
    
    In [411]: _length_2(lnk1) # 普通递归 获取长度
    Out[411]: 2
    
    In [396]: aaa=tail_length(lnk1) # 尾递归获取长度
    
    In [397]: aaa
    Out[397]: 2
    

    我的理解就是前面一层一层 解开。 后面一个数一直累积

    # 尾递归  此函数 可以使用
    def tail_length(lst):
        def length_helper(lst,length=0):
            if lst is Link.empty:
                return length
            else:
                length+=1
                return length_helper(lst.rest,length)
                
        return length_helper(lst)
    
    # 过程
    length_helper(lst,0)
    length_helper(lst.rest,1)
    length_helper(lst.rest.rest,2)
    length_helper(lst.rest.rest.rest,3)
    
    # 这是我所理解的尾递归\
    
    # -------- 与普通阶乘递归作比较 ----------------
    def factorial(n):
        if n == 1:
            return 1
        else:
            return n*factorial(n-1)
            
    # 过程
    
    factorial(5) # 计算过程
    5*factorial(5-1)
    5*4*factorial(4-1)
    5*4*3*factorial(3-1)
    5*4*3*2*factorial(2-1)=120 # factorial(1) 里面判断 n=1 的时候 返回 1 
    
    

    单链表数据结构实现

    class Link:
        empty=()
        def __init__(self,first,rest=empty):
            assert rest is Link.empty or isinstance(rest,Link)
            self.first=first
            self.rest=rest
    
    
        def __repr__(self):
            if self.rest is Link.empty:
                return 'Link(' + self.first.__repr__()+')'
                # else 里面这种方法也是 可以的。 看自己 习惯哪种
            else:
                return 'Link('+ repr(self.first) +','+ repr(self.rest)+ ')'
    
    
        def __str__(self):
            s='<'
            while self.rest is not Link.empty:
                # 循环 fisrt  rest 最后加上 first和空 >
                s=s+self.first.__str__()+', ' 
                # 两种调用 str 的方法本质上没啥 区别
                self=self.rest
            return s + str(self.first)+'>'
    
    
        def __eq__(self,other):
            if self.fist != other.first:
                return False
            return self.rest==other.rest
            # 这也是一种办法。 还是满 使用的技巧。
            # 但是会导致传入一个 其他类 的实例 判断会出现错误
            return repr(self) == repr(other)
    
    
        def __contains__(self,x):
            # if self.first==x:
            #     return True
            # return self.first == x or x in self.rest
            return self.rest.__contains__(x) # 这种写法也是可以的。
        def __add__(self,other):
            '''
            连接  功能 不是加法。
            本质还是一个递归   哈哈  
            >>> Link(1,Link(2)) + Link(3,Link(4))
            Link(1,Link(2,Link(3,Link(4))))
            >>> Link(1) + Link(2)
            Link(1,Link(2))
            >>> Link(1) + Link(2,Link(3))
            Link(1,Link(2,Link(3)))
            >>> Link(1,Link(2)) + Link(3,Link(4))
            Link(1,Link(2,Link(3,Link(4))))
            '''
            if self.rest is Link.empty:
                if other.rest is Link.empty:
                    return Link(self.first,Link(other.first))
                else:
                    return Link(self.first,Link(other.first)+ other.rest )
            else:
                return Link(self.first,self.rest+other)
    
            def __mul__(self,num):
                '''
                >>> Link(1,Link(2))*2
                Link(1,Link(2,Link(1,Link(2))))
                >>> 2*Link(1,Link(2))
                NotImplemented
                '''
                temp=self
                for _ in range(num-1):
                    temp=temp+self
                return temp
    
            def __rmul__(self,num):
                '''
                >>> 2*Link(1,Link(2))
                Link(1,Link(2,Link(1,Link(2))))
                '''
                return self*nun
    
    # 处理链表
    def sum_link(lnk):
        if lnk is Link.empty:
            return 0
        return lnk.first+sum_link(lnk.rest)
    
    # 展示链表  和之前 写的 print 差不多
    def display_lnk(lnk):
        string="< "
        while lnk is not Link.empty:
            if isinstance(lnk.first,Link):
                elem=display_lnk(lnk.first)
            else:
                elem=str(lnk.first)
            string += elem + " "
            lnk=lnk.rest
        return string + ">"
    # map 映射
    def map_lnk(f,lnk):
        if lnk is Link.empty:
            return Link.empty
        else: 
            return Link(f(lnk.first),map_lnk(f,lnk.rest))
    def map_iter(f,lnk):
        new_lnk=Link.empty
        while lnk is not Link.empty:
            new_lnk=Link(f(lnk.first),new_lnk)
            print(display_lnk(new_lnk))
            lnk=lnk.rest
        return new_lnk
    
    def map_lnk_v2(f,lnk):# 可变的链表 操作。 不是新建对象。在原有对象上操作
        '''
        >>> lnk=Link(1,Link(2,Link(3)))
        >>> map_lnk_v2(lambda x: x*2)
        >>> print(display_link(lnk))
        <2, 4, 6>
        '''
        if lnk is Link.empty:
            return
        lnk.first=f(lnk.first)
        map_lnk_v2(lnk.rest,f)
    
    def map_lnk_v2_iter(f,lnk): 
        '''
        >>> lnk=Link(1,Link(2,Link(3)))
        >>> map_lnk_v2(lambda x: x*2)
        >>> print(display_link(lnk))
        <2, 4, 6>
        '''
        while lnk is not Link.empty:
            lnk.first=f(lnk.first)
            lnk=lnk.rest
    

    测试

    
    In [375]: lnk1=Link(1,Link(2))
    
    In [376]: lnk1.first
    Out[376]: 1
    
    In [377]: lnk1.rest.first
    Out[377]: 2
    
    In [378]: lnk1.rest.rest is Link.empty
    Out[378]: True
    

    如果有兴趣的话可以看我用 javascript 写的双链表 数据结构 - 这个和递归 没有 任何关系 这个双链表。

    高阶函数

    在后面会有一些 递归的例子。

    在进阶的 高阶函数 和 递归中。 不过还是不太 建议大家 提前去看。

    展开全文
  • Python之递归函数

    千次阅读 2018-10-14 20:07:16
    前言 说到递归,如果是从其他编程语言转到 Python 的...OK,废话多说,来看一下 Python 中递归函数的写法。 定义 所谓递归,就是调用函数自身。 简单的说就是函数自己调用自己。递归可能难以理解,也可能非常简...

    前言

    说到递归,如果是从其他编程语言转到 Python 的童鞋对这个词一定不会陌生,在很多情况下,使用递归可以提高程序的可读性,虽然可以完全避免编写递归函数,转而使用循环来代替,但是作为程序猿,至少必须要能够读懂其他人编写的递归算法和函数吧。OK,废话不多说,来看一下 Python 中递归函数的写法。

    定义

    所谓递归,就是调用函数自身。
    简单的说就是函数自己调用自己。递归可能难以理解,也可能非常简单,这取决于对它的熟悉程度。
    下面是一个递归函数的定义:

    >>> def recursion():
    ...     return recursion()
    

    这个递归定义显然什么都没有做,如果运行该函数的结果就是一段时间后程序就崩掉了。因为每次调用函数都将会消耗一些内存,当内存爆满就自然就挂了。
    这个函数中的递归成为无穷递归,就好比一个 while 死循环,从理论上说它将永远不会结束,这显然不是我们想要的结果。

    所以正常的递归函数通常包含以下两个部分;

    1.基线条件(针对最小的问题):满足这种条件时函数将直接返回一个值。
    2.递归条件:包含一个或多个调用,这些调用旨在解决问题的一部分。

    这里的关键是,通过将问题分解为较小的部分,可避免递归没完没了,因为问题终将被分解成基线条件可以解决的最小问题。

    OK,以上的定义和描述可能对于一个刚接触递归的人来说有些难以理解,接下来通过几个示例来看看递归的用法。

    递归经典案例

    计算阶乘

    阶乘定义:n 的阶乘为 n*(n-1)*(n-2)*…*1
    那么要计算阶乘,用传统的循环方式写法如下:

    def factorial(n):
    	result = n
    	for i in range(1,n):
    		result *= i
    	return result
    

    上述循环的思路大概是:首先将 result 设置成 n,然后通过循环,将 result 依次乘以1~(n-1)的每个数字,最后返回结果。

    而通过递归的方式如何实现呢,再看阶乘的算法,n 的阶乘其实相当于 n 乘以(n-1)的阶乘,而1的阶乘为1。
    通过以上分析,来看看通过递归来实现阶乘的写法:

    def factorial(n):
    	if n == 1:
    		return 1
    	else:
    		return n*factorial(n-1)
    

    很明显,通过递归来实现同样算法,代码非常简单,并且可读性也很好。这是前述定义的直接实现,只是别忘了函数调用factorial(n)和factorial(n-1) 是不同的实体。

    计算幂

    定义一个数字的整数次幂,有多种方式,先来看个简单的定义:power(x,n)(x 的 n 次幂)是将数字 x 自乘以 n-1次的结果,即将 n 个 x 相乘。
    传统的写法,通过循环来实现:

    def power(x,n):
    	result = 1
    	for i in range(n):
    		result *= x
    	return result
    

    这是一个非常简单的小型函数,可将定义修改成递归的形式:

    对于任何数字的0次幂都是1
    当 n 大于0时,power(x,n)为 x和 power(x,n-1)的乘积。

    那么来看看递归的写法:

    def power(x,n):
    	if n == 0:
    		return 1
    	else:
    		return x*power(x,n-1)
    

    二分法查找

    二分法查找,这是一个非常经典的查找算法,所谓的二分法,就是让每次查找的范围减半,这样查找效率非常的高,比如说一个猜数游戏,从1~100数字中猜出对方想好的一个数字,如果从1到100一个个的猜,肯定能猜对,最多会猜100次,那么最少需要猜多少次呢,通过二分法实际上只需要7次就能猜出正确答案。
    结合二分法的定义引出递归的定义和实现。

    1.如果上限和下限相同,就说明它们都指向数字所在的位置,因此将该数字返回。
    2.否则,找出区间的中间位置(上限和下限的平均值),再将数字确定是在左半部分还是有半部分,然后继续在数字所在的那部分中查找。

    OK,接下来看看递归实现二分法算法:

    def search(seq,number,lower = 0,upper = None):
    	if upper is None:
    		upper = len(seq) - 1
    		
    	if lower == upper:
    		assert number == seq[upper]
    		return upper
    	else:
    		middle = (lower + upper) // 2
    		if number > seq[middle]:
    			return search(seq,number,middle + 1,upper)
    		else:
    			return search(seq,number,lower,middle)
    

    这里将上限和下限值定义成可选,如果不指定上下限值,那么默认为序列的开头和结尾位置。该递归的实现完全由上面的定义一致。
    来看看效果:

    seq = [23,1,35,38,89,24,32,76]
    seq.sort()
    print(seq)
    print(search(seq,32))
    print(search(seq,89))
    

    返回结果:

    [1, 23, 24, 32, 35, 38, 76, 89]
    3
    7
    

    二分法在对于一个非常大的序列中使用效率非常高,如果使用循环的方式一个个的去找,对于序列中元素较少的情况下还好,如果数据量非常大,查询效率就很低了。

    由此可见,递归的写法非常简洁,合理使用递归程序的可读性将会大大的提高。

    展开全文
  • 开篇递归函数(二):编写递归函数的思路和技巧递归函数(三):归纳原理递归函数(四):全函数与计算的可终止性递归函数(五):递归集与递归可枚举集递归函数(六):最多有多少个程序递归函数(七):动点算子...
  • 你是指“递归函数”? 例如分享n。的递归函数。 fun(n) { if(n==0)return 1; return n*fun(n-1); }其实我好想听你说实话,你却总是为了让我难过说谎话关于oracle递归调用的自定义函数如何结束我爱你时,你说什么...
  • 1、关于递归函数描述,以下选项中正确的是A.包含一个循环结构B.函数比较复杂C.函数内部包含对本函数的再次调用D.函数名称作为返回值答案:D答案解析:递归函数是指函数内部包含对本函数的再次调用。2、关于递归...
  • 1关于递归函数描述,以下选项中正确的是A函数内部包含对本函数的再次调用B函数比较复杂C包含一个循环结构D函数名称作为返回值正确答案:A2关于递归函数基例的说明,以下选项中错误的是A递归函数必须有基例B每个...
  • 递归函数总结

    2018-04-01 20:42:20
    知识点递归函数定义直接或间接调用自身的函数.递归函数调用自身的目的是为了使复杂问题简单化,循环调用自身,直到问题可以直接被解决时,停止调用自身函数,也即是递归函数有递归终止条件.递归两个要素1.递归终止...
  • C++递归函数

    万次阅读 多人点赞 2018-03-28 15:22:12
    C++递归函数【递归,就是在运行的过程中调用自己】比如:(点击了下面的递归,搜索结果还是递归) A.构成递归需具备的条件: 1.子问题须与原始问题为同样的事,且更为简单。 2.能无限制的调用本身,必须有个...
  • 匿名用户1级2010-12-11 回答递归(recursion)就是子程序(或函数)直接调用自己或通过一系列调用语句间接调用自己,是一种描述问题和解决问题的基本方法。递归通常用来解决结构自相似的问题。所谓结构自相似,是指构成...
  • Python递归函数正确理解与使用

    千次阅读 2018-06-02 19:08:46
    先看一个题目:题面描述 小明很喜欢学数学,并且喜欢做一些奇怪的题,这天他想知道对于给定的 N ,有多少个 M 满足“ M&lt;=N, gcd(N,M)==1, M 是偶数”。请你编写程序帮助小明解决这个问题。 输入数据 输入数据...
  • 版权声明:本作品由九天雁翎创作,采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。... 递归是编程中一个相对难以理解但是却又很重要...
  • 递归: 在函数的调用中,有一种特殊的情况,比如一个函数直接的间接的调用自身,称其为函数递归调用。 递归调用有两种形式: 直接递归:在一个函数中调用自身 间接递归:在一个函数中...设计一个正确递归过..
  • 【C语言】【递归函数】递归实现指数函数题目描述输入输出样例输入样例输出带填充标签的C/C++原程序代码实现偷懒做法(你们都懂)正确做法 题目描述 本题要求实现一个计算xn(n>=0),计算结果用双精度double 输入...
  • 函数的递归调用是在调用一个函数的执行过程中,直接或间接地调用该函数本身,使用递归函数的程序结构清晰,简单、易懂。本文通过具体实例并利用图示对递归函数进行分析和讲解,使学生能够很好地理解和掌握递归函数的...
  • 一文读懂递归函数

    2020-11-24 23:39:17
    1、什么是递归函数递归函数就是直接或间接调用自身的函数。 2、什么情况下可以使用递归函数。 (1)存在限制条件,且当到达限制条件时递归便不再继续。 (2)每次递归之后越来越接近限制条件。 3、递归函数举例...
  • 6.递归函数

    2018-12-19 17:23:00
    python---------------递归函数 一、递归的定义 1.什么是递归:在一个函数里在调用这个函数本身 2.最大递归层数做了一个限制:997,但是也可以自己限制 1 def foo(): 2 print(n) 3 n+=1...
  • 函数递归

    2018-05-02 11:57:02
    程序调用自身的编程技巧称为递归递归通常是把一个大型的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策咯只需少量的程序就可描述出解题过程中所需要的多次重复计算,大大地减少了程序的代码量。...
  • 递归函数的文章汇集

    2014-09-02 20:00:07
    递归函数之所以难,是因为是一种过于抽象化的技术,写代码的时候无法直观的看出逻辑是否符合自己要求,因此想一次性写好递归函数,是一件很困难的事情,必须要程序运作起来执行递归函数的代码才能看出是否正确,而且...
  • 递归函数求解

    2016-03-28 19:30:22
    问题及描述; /* *Copyright (c) 2016,烟台大学计算机学院 *All rights reserved. *文件名称;... *问题描述; 用递归函数求解 *输入描述; 无 *输出描述; 输出答案 */ #include using namespa

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 72,691
精华内容 29,076
关键字:

关于递归函数描述不正确的是