什么是递归的一个很好的例子不是生成Fibonacci序列等？ [英] What is a good example of recursion other than generating a Fibonacci sequence?

问题描述

可能显示的文件：
  的真实世界的例子递归
  递归函数

Possible Duplicates:
Real-world examples of recursion
Examples of Recursive functions

我看到，大多数编程语言教程教递归通过一个简单的例子是如何产生Fibonacci序列，我的问题是，是否有另一个很好的例子不是生成Fibonacci序列等来解释如何递归工作？

I see that most programming language tutorial teach recursion by using a simple example which is how to generate fibonacci sequence, my question is, is there another good example other than generating fibonacci sequence to explain how recursion works?

推荐答案

经典的是二进制树搜索：

The classic is the binary tree search:

def findval (node,val):
    if node == null:
        return null
    if node.val = val:
        return node
    if node.val > val:
        return findval (node.left,val)
    return findval (node.right,val)

findval (root,thing_to_find)

这可能是一个小比一个简单的公式比较复杂的，但它的面包和黄油使用递归的，它说明了最好的地方使用它，但如递归级别降到最低。

That may be a little more complex than a simple formula but it's the "bread and butter" use of recursion, and it illustrates the best places to use it, that where the recursion levels are minimised.

我的意思是：你的可以的补充两个非负数有：

By that I mean: you could add two non-negative numbers with:

def add (a,b):
    if b == 0:
        return a
    return add (a+1,b-1)

但你会发现自己跑出来的堆栈空间pretty的快速的大量的（除非编译器优化过程中的尾端递归，但你可能应该忽略教学的你关心的水平）。

but you'd find yourself running out of stack space pretty quickly for large numbers (unless the compiler optimised tail-end recursions of course, but you should probably ignore that for the level of teaching you're concerned with).

这篇关于什么是递归的一个很好的例子不是生成Fibonacci序列等？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！