-
In week zero, when we tore the phonebook in half and half and half we were recursing through that problem.
当我们将电话簿划分为一半又一半的时候,其实就是利用递归在解决问题。
-
Well, the infinity mechanism, and many of you will be familiar with this from mathematics or computer science, is recursion.
这种无限机制是递归的,你们许多人会在数学与计算机科学中,熟悉这个词
-
What's the point of this? Again, now that I can think about things recursively, I can similarly break things down into simpler versions of the same problem. It could be one version.
这些的意思是什么呢？再一次我想说,我既然能够以递归的方式思考了,那么我就可以简单地把问题,转化为更简单的同类问题。
-
So, the curious thing about recursion is that pretty much always can you implement this idea of doing the same thing again and again and again but with smaller bytes each time.
可见，递归算法中新奇的一点是,为了实现一个想法,你可以一遍又一遍地做相同的事情,但每次的规模都会有所减小。
-
This sentence expands to a noun followed by a verb followed by a sentence and there you get recursion.
这个句子就扩展成了,一个名词,后跟一个动词,再接刚才的句子,这样就变成了递归
-
But that's also nice, it lets you see how the recursive thing is simply unwrapping but the complexity in terms of the amount of time it takes is going to be the same.
它让我们看到了，在复杂度依照时间总数来看,没有变化的情况下,递归是怎么一步步的展开的,我欠你一个糖，谢谢。
-
And I'm going to show you an example in a 1 second, just to drive this home, but notice the characteristics. In the first two cases, the problem reduced by 1 at each step.
在前面两个例子里,每一部问题的规模缩小了,不管是迭代的还是递归的，这表明这个问题的复杂性可能是线性的。
-
So this is very similar, this is a kind of recursive thinking we talked about earlier, where we take our problem and we make it smaller we solve a smaller problem, et cetera.
我们则跳过比猜想数小的那个区间,然后我们重复这一过程,跟之前我们讲过的，递归思想非常类似,我们解决问题的时候,先把问题一步步变小，然后解决小问题。
-
And the idea behind recursion I'm going to describe with a simple example. And then I'm going to show you how we can actually use it.
但是为了解释递归的意义,我想举个简单的例子,我将会给你们展示我们该如何使用它。
-
This is another way of doing exponentiation, but this one's a recursive function. All right?
但这是一种递归的方法对不对？,好，让我们看看这种方法？
-
And this too is where the power of recursion comes in in a programming language.
这也是在编程语言中,对递归很有影响的一点。
-
And I would suggest palindrome as a great example of that. That's easy to think about recursively. It's much harder to think about iteratively. And you want to get into the habit of deciding which is the right one for you to use. And with that, we'll see you next time.
其它的问题可能用递归的方式,可以更好的解决,而直接思考可能很困难,这时你就得养成做出,正确选择的好习惯了,下周再见。
-
And this is obviously a toy example but you could see the use of recursion in everyday life and in everyday use of language.
这只是个小例子,但在日常生活和日常用语中,递归的应用极为广泛
-
The last point I want to make to you is, you've started writing programs that you would think of as being inherently iterative.
能反映递归特性的程序，我最后一点想说的是,你已经开始编写你认为。
-
This is actually a piece of code that is really easy to think about recursively and is much more difficult to think about in other ways.
这确实是一段用递归思考起来非常容易,而其它方法特别麻烦的代码,这一段代码的意思就是。
-
There are other problems that are much more naturally thought of in a recursive fashion.
有一些问题不递归,也可以很简单的解决。
-
How do you know that your parents, at least one of your parents satisfies the definition? Well I've reduced the problem from am I a natural born US citizen to is one of my parents a natural born US citizen?
这是一个递归的定义，你怎么知道你的父母,至少其中一个是满足天生的美国公民,这个定义的呢？,我已经把我是一个天生的美国公民这个问题？
-
All right, I want to show you one last example of using recursion because we're going to come back to this. This is a classic example of using recursion. And that is dating from the 1200s and it is due to Fibonacci.
并且返回答案,我想给你看看递归的最后一个例子,因为我们还要再看一遍,这是一个递归的经典案例,它可以追溯到13世纪。
-
fib Roughly speaking, the analysis of fib is actually quite complex, of a recursive fib.
简单的说,递归的fib的分析实际上非常复杂。
-
Because the algorithm I proposed is going to leverage this idea of recursion which recall was just a piece of jargon we tossed out at the last-- at the end of last week's lecture, last time's lecture recursion really in this context refers to the act of a function calling it's self.
因为我提出的这种算法使用了,递归的思想，这是上周课程的最后,所提出的一个术语，上次的课程中，递归是指,函数的自我调用。
-
And the reason I want to show you this is to notice that the recursion can be doubled.
如果我来写斐波那契数列你可以看看这儿,原因是我想让你看看这部分的递归可以翻倍。
-
All right, this is what's called a recurrence relation, there are actually cool ways to solve them. We can kind of eyeball it.
好，这就是所谓的递归关系,也就是解决问题的相当好的办法,我们可以来看看。
-
But I want to stress again, as long as I do the base case right and my inductive or recursive step reduces it to a smaller version of the same problem, the code will in fact converge and give me out an answer.
就开心的去做吧,但是我想再次强调,只要基础事件处理正确而我的递归,或递推步骤能把它简化为更简单的同类问题,那么这段代码就可以收敛。
-
We're going to see variations of this, we're going to see a variation of it called recursion, a little later on, but for now we're just going to talk about how do we do iterations.
我们稍后会去，看它的变量,它的所谓的递归数的变量，但是现在我得先讲讲,怎么来实现迭代。
-
Not so easy to see. All right, but this is actually a great one of those educational moments. This is a great example to think recursively. If I wanted to think about this problem recursively- what do I mean by thinking recursively?
看不太出来，好，但实际上是一个有教育意义的时刻,这是一个很好的关于递归的例子,如果我用递归的思想,去考虑这个问题-,我该怎么用递归去解决这个问题呢？
-
How many of you have heard the term used before? How may have you heard the term used before in terms of programming languages? Great. For the rest you, don't sweat it. This is a highfalutin term that computer scientists use to try and make them look like they're smarter than they really are.
这里就要引入递归的概念了,你们中有多少人以前听过这个词？,你们中有多少人在编程语言中,用过这个词？,很好，剩下的同学也不要担心,这是电脑科学家们用来让自己,显得更聪明的夸张词汇。
-
It's actually a wonderful recursive definition.
这就是一个绝妙的递归定义。
-
Wonderful recursive definition.
很漂亮的递归定义。
-
So now, let's recurse together, let's dive in and hone in on what T of 8 is.
下面用递归的方法继续,看看T是多少。
-
Nobody in their right mind actually implements a recursive Fibonacci the way I did it originally.
没有谁真的在右脑中,按我最初讲的递归方法,计算Fibonacci数列。
应用推荐