
English: 
Most of you probably ran into the Fibonacci sequence of numbers,
named after filius Bonacci in a previous computer science class.
It's a great way to teach recursion.
Here I've written out a Python definition for the Fibonacci sequence.
To get the Nth Fibonacci number, well, if N is less than or equal to 2,
we just return 1, otherwise, we return the sum of the 2 previous entries.
So we're going to get 1, 1, 2 -- 1 + 1 = 2.
1 + 2 = 3.
2 + 3 = 5.
3 + 5 = 8.
5 + 8 = 11. That sort of thing. Did I do that correctly? Let's imagine. [Laughs]
No, I totally didn't do that correctly. Man, you can't take me anywhere.
[Singing--hmm, hmm, hmm] Basic math. Don't mind me. There we go.
This looks a lot better. You saw nothing.
Alright, so there's our Fibonacci sequence.
In an incredible surprise move, it actually shows up a lot in nature--
for example, in the patterns of seeds in a sunflower or in the whirls in a clamshell

Portuguese: 
A maioria de vocês já conhece a sequência de números de Fibonacci,
cujo nome se deve a Fillus Bonacci, como vimos em outro curso.
É uma ótima maneira de introduzir recursão.
Escrevi aqui uma definição para a sequência de Fibonacci, em Python.
Para obter o n-ésimo número de Fibonacci, bem, se n<2,
simplesmente retornamos 1; caso contrário, retornamos a soma das 2 entradas anteriores.
Portanto, vou obter, 1,1,2 -- 1+1 = 2,
1+2 = 3,
2+3 = 5,
3 + 5 = 8,
5 + 8 = 11... Eu fiz isso certo? Vamos imaginar que sim :-)
Não! Eu não fiz certo! Isso me faz perder a cabeça.
Hmm, humm, humm. Matemática básica. Não se importe. Aqui vamos.
Isso está melhor. Você não viu nada.
Ok, Aqui está a sequência de Fibonacci.
Surpreendentemente, ela ocorre com frequência na natureza.
Por exemplo, em padrões de sementes de girassol, ou nas voltas de um caracol,

Japanese: 
以前コンピュータ・サイエンスのクラスを
受けた方は
フィボナッチ数列について学んだかと思います
再帰を学ぶにはとてもいい方法です
PythonでN番目のフィボナッチ数列の
数を得る関数fiboを定義します
もしNが2以下であれば
1を返します
それ以外の場合は2つ前の数を足して返します
この場合1、1、2、1＋1＝2
1＋2＝3
2＋3＝5
3＋5＝8
5＋8＝11となります
これで正しいでしょうか？　見直してみましょう
やっぱり間違っていましたね
単純な計算ミスです　気にしないでください
これが正解ですね
さっきのことは忘れてください
フィボナッチ数列です
この数列は自然界でよく見られるんです
例えばヒマワリの種の配列やハマグリの模様や

English: 
or in yellow chamomile plants or all that good stuff.
However, Fibonacci involves a huge amount of work.
Let's go see what goes on when we call Fibonacci.
I'm going to abbreviate it with an f--Fibonacci of 5.
Well, that's going to be based on Fibonacci of 4 and Fibonacci of 3.
Now 4 is based on 3 and 2. 2 is a base case, so we're done. 3 is based on 2 and 1.
Over here, 3 is based on Fibonacci of 2 and Fibonacci of 1.
If you look carefully, a lot of these get repeated many times.
We end of calling Fibonacci of 2--once, twice, 3 times I called it.
Similarly, Fibonacci of 3 is called multiple times.
We're redoing work.
We're computing the value of Fibonacci of 2 and Fibonacci of 3 over and over again.

Japanese: 
カモミールの管状花などです
フィボナッチ数列には膨大な作業が必要です
実際に関数を呼んでみます
フィボナッチを省略してｆとして
f（5）を考えてみます
これはf（4）とｆ（3）から求められます
f（4）はf（3）とf（2）、f（2）はベースケースです
f（3）はf（2）とf（1）で計算
こちら部分のf（3）はf（2）とf（1）で求められます
よく見てみると
これらは繰り返し使われていますね
f（2）は1、2、3回使用されています
ｆ（3）に関しても繰り返し使われています
同じ作業が繰り返されており
ｆ（2）とｆ（3）を何度も計算しています
これは無駄な作業なので避けたいですね

Portuguese: 
ou em plantas de camomila amarela e várias coisas boas.
Entratanto, fibo envolve um bocado de trabalho.
Vamos ver o que acontece quando chamamos fibo --
vou abreviar como f -- f(5).
Bem, isto é baseado em f(4) e f(3).
Agora, f(4) é basedo em f(3) e f(2). 2 é um caso base, portanto terminamos. f(3) é baseado em f(2) e f(1).
Aqui, f(3) é baseado em f(2) e f(1).
Se você olhar com cuidado, verá que grande parte disso é repetida muitas vezes.
Acabamos chamando f(2) , 1,2,3 vezes.
De modo análogo, f(3) é chamado múltiplas vezes.
Estamos refazendo trabalho:
estamos computando o valor de f(2) e f(3) de novo, e de novo.

English: 
That is wasted work. We want to be lazy and avoid that.

Portuguese: 
Isso é trabalho perdido. Queremos ser preguiçosos e evitar isso.
