StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The idea behind the Fibonacci sequence is shown in the following Python code:</p> <pre><code>def fib(n): if n == 1: return 1 elif n == 0: return 0 else: return fib(n-1) + fib(n-2) </code></pre> <p>This means that fib is a function that can do one of three things. It defines fib(1) == 1, fib(0) == 0, and fib(n) to be:</p> <p>fib(n-1) + fib(n-2)</p> <p>Where n is an arbitrary integer. This means that fib(2) for example, expands out to the following arithmetic:</p> <pre><code>fib(2) = fib(1) + fib(0) fib(1) = 1 fib(0) = 0 # Therefore by substitution: fib(2) = 1 + 0 fib(2) = 1 </code></pre> <p>We can calculate fib(3) the same way with the arithmetic shown below:</p> <pre><code>fib(3) = fib(2) + fib(1) fib(2) = fib(1) + fib(0) fib(2) = 1 fib(1) = 1 fib(0) = 0 # Therefore by substitution: fib(3) = 1 + 1 + 0 </code></pre> <p>The important thing to realize here is that fib(3) can't be calculated without calculating fib(2), which is calculated by knowing the definitions of fib(1) and fib(0). Having a function call itself like the fibonacci function does is called recursion, and it's an important topic in programming.</p> <p>This sounds like a homework assignment so I'm not going to do the start/end part for you. Python is a wonderfully expressive language for this though, so this should make sense if you understand math, and will hopefully teach you about recursion. Good luck!</p> <p>Edit: One potential criticism of my code is that it doesn't use the super-handy Python function yield, which makes the fib(n) function a lot shorter. My example is a little bit more generic though, since not a lot of languages outside Python actually have yield. </p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload