什么是递归?

什么是递归?
匿名|2024-02-26 09:13:08

  递归(recursion)是程序调用自身的编程技巧,它作为一种算法在程序设计语言中广泛应用。简单地说,递归就是一个函数直接或间接调用自身的一种方法。


什么是递归.jpg


  在数学定义中,递归指由一种(或多种)简单的基本情况定义的一类对象或方法,并规定其他所有情况都能被还原为其基本情况。


  例如,斐波纳契数列(Fibonacci Sequence),又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21......斐波纳契数列是典型的递归案例:


  Fib(0)=1[基本情况]Fib(1)=1[基本情况]对所有u003cb的整数:Fib(n)=(Fib(n-1)+Fib(n-2))[递归定义]尽管有许多数学函数均可以递归表示,但在实际应用中,递归定义的高开销往往会让人望而却步。


  又如,阶乘(1)=1[基本情况]对所有nu003e1的整数:阶乘(n)=(n*阶乘(n-1))[递归定义]一种便于理解的心理模型,是认为递归定义对对象的定义是按照“先前定义的”同类对象来定义的。比如:你怎样才能移动100个箱子?答案:你首先移动一个箱子,并记下它移动到的位置,然后再去解决较小的问题:你怎样才能移动99个箱子?最终,你的问题将变为怎样移动一个箱子,而这时你已经知道该怎么做的。


  如此的定义在数学中十分常见。集合论对自然数的正式定义是:1是一个自然数,每个自然数都有一个后继,这一个后继也是自然数。可见,递归关系就是实体自己和自己建立关系。


  再如,在两面相对的镜子之间放一根正在燃烧的蜡烛,我们会从其中一面镜子里看到一根蜡烛,蜡烛后面又有一面镜子,镜子里面又有一根蜡烛……这也是递归的表现。


  递归在数学和计算机科学中十分常用。它可以用于解决许多问题,包括搜索、排序、树遍历和图遍历等;它是一种强大的工具,但也需要注意一些最佳实践,以确保它的正确性和性能。


  文/冯萍(作者单位:天津师范大学继续教育学院)


本文属原作者授权投稿专栏,须取得本网站的书面授权,未经授权严禁转载或用于其它商业用途

等你来答