source: public/doc/gnu-c/Iterative-Fibonacci.html@ 02598c2

Last change on this file since 02598c2 was 02598c2, checked in by Mikhail Kirillov <w96k@…>, on Oct 6, 2022 at 12:36:29 PM

Add gnu-c
  • Property mode set to 100644
File size: 10.1 KB
Line 
1<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
2<html>
3<!-- Copyright (C) 2022 Richard Stallman and Free Software Foundation, Inc.
4
5(The work of Trevis Rothwell and Nelson Beebe has been assigned or
6licensed to the FSF.)
7
8Permission is granted to copy, distribute and/or modify this document
9under the terms of the GNU Free Documentation License, Version 1.3 or
10any later version published by the Free Software Foundation; with the
11Invariant Sections being "GNU General Public License," with the
12Front-Cover Texts being "A GNU Manual," and with the Back-Cover
13Texts as in (a) below. A copy of the license is included in the
14section entitled "GNU Free Documentation License."
15
16(a) The FSF's Back-Cover Text is: "You have the freedom to copy and
17modify this GNU manual. Buying copies from the FSF supports it in
18developing GNU and promoting software freedom." -->
19<!-- Created by GNU Texinfo 6.7, http://www.gnu.org/software/texinfo/ -->
20<head>
21<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
22<title>Iterative Fibonacci (GNU C Language Manual)</title>
23
24<meta name="description" content="Iterative Fibonacci (GNU C Language Manual)">
25<meta name="keywords" content="Iterative Fibonacci (GNU C Language Manual)">
26<meta name="resource-type" content="document">
27<meta name="distribution" content="global">
28<meta name="Generator" content="makeinfo">
29<link href="index.html" rel="start" title="Top">
30<link href="Symbol-Index.html" rel="index" title="Symbol Index">
31<link href="index.html#SEC_Contents" rel="contents" title="Table of Contents">
32<link href="The-First-Example.html" rel="up" title="The First Example">
33<link href="Complete-Program.html" rel="next" title="Complete Program">
34<link href="Stack.html" rel="prev" title="Stack">
35<style type="text/css">
36<!--
37a.summary-letter {text-decoration: none}
38blockquote.indentedblock {margin-right: 0em}
39div.display {margin-left: 3.2em}
40div.example {margin-left: 3.2em}
41div.lisp {margin-left: 3.2em}
42kbd {font-style: oblique}
43pre.display {font-family: inherit}
44pre.format {font-family: inherit}
45pre.menu-comment {font-family: serif}
46pre.menu-preformatted {font-family: serif}
47span.nolinebreak {white-space: nowrap}
48span.roman {font-family: initial; font-weight: normal}
49span.sansserif {font-family: sans-serif; font-weight: normal}
50ul.no-bullet {list-style: none}
51-->
52</style>
53
54
55</head>
56
57<body lang="en">
58<span id="Iterative-Fibonacci"></span><div class="header">
59<p>
60Previous: <a href="Stack.html" accesskey="p" rel="prev">Stack</a>, Up: <a href="The-First-Example.html" accesskey="u" rel="up">The First Example</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Symbol-Index.html" title="Index" rel="index">Index</a>]</p>
61</div>
62<hr>
63<span id="Example_003a-Iterative-Fibonacci"></span><h3 class="section">1.3 Example: Iterative Fibonacci</h3>
64<span id="index-iterative-Fibonacci-function"></span>
65<span id="index-Fibonacci-function_002c-iterative"></span>
66
67<p>Here&rsquo;s a much faster algorithm for computing the same Fibonacci
68series. It is faster for two reasons. First, it uses <em>iteration</em>
69(that is, repetition or looping) rather than recursion, so it doesn&rsquo;t
70take time for a large number of function calls. But mainly, it is
71faster because the number of repetitions is small&mdash;only <code><var>n</var></code>.
72</p>
73
74<div class="example">
75<pre class="example">int
76fib (int n)
77{
78 int last = 1; /* <span class="roman">Initial value is <code>fib (1)</code>.</span> */
79 int prev = 0; /* <span class="roman">Initial value controls <code>fib (2)</code>.</span> */
80 int i;
81
82 for (i = 1; i &lt; n; ++i)
83 /* <span class="roman">If <code>n</code> is 1 or less, the loop runs zero times,</span> */
84 /* <span class="roman">since <code>i &lt; n</code> is false the first time.</span> */
85 {
86 /* <span class="roman">Now <code>last</code> is <code>fib (<code>i</code>)</code></span>
87 <span class="roman">and <code>prev</code> is <code>fib (<code>i</code> - 1)</code>.</span> */
88 /* <span class="roman">Compute <code>fib (<code>i</code> + 1)</code>.</span> */
89 int next = prev + last;
90 /* <span class="roman">Shift the values down.</span> */
91 prev = last;
92 last = next;
93 /* <span class="roman">Now <code>last</code> is <code>fib (<code>i</code> + 1)</code></span>
94 <span class="roman">and <code>prev</code> is <code>fib (<code>i</code>)</code>.</span>
95 <span class="roman">But that won&rsquo;t stay true for long,</span>
96 <span class="roman">because we are about to increment <code>i</code>.</span> */
97 }
98
99 return last;
100}
101</pre></div>
102
103<p>This definition computes <code>fib (<var>n</var>)</code> in a time proportional
104to <code><var>n</var></code>. The comments in the definition explain how it works: it
105advances through the series, always keeps the last two values in
106<code>last</code> and <code>prev</code>, and adds them to get the next value.
107</p>
108<p>Here are the additional C features that this definition uses:
109</p>
110<dl compact="compact">
111<dt>Internal blocks</dt>
112<dd><p>Within a function, wherever a statement is called for, you can write a
113<em>block</em>. It looks like <code>{ <span class="roman">&hellip;</span> }</code> and contains zero or
114more statements and declarations. (You can also use additional
115blocks as statements in a block.)
116</p>
117<p>The function body also counts as a block, which is why it can contain
118statements and declarations.
119</p>
120<p>See <a href="Blocks.html">Blocks</a>.
121</p>
122</dd>
123<dt>Declarations of local variables</dt>
124<dd><p>This function body contains declarations as well as statements. There
125are three declarations directly in the function body, as well as a
126fourth declaration in an internal block. Each starts with <code>int</code>
127because it declares a variable whose type is integer. One declaration
128can declare several variables, but each of these declarations is
129simple and declares just one variable.
130</p>
131<p>Variables declared inside a block (either a function body or an
132internal block) are <em>local variables</em>. These variables exist only
133within that block; their names are not defined outside the block, and
134exiting the block deallocates their storage. This example declares
135four local variables: <code>last</code>, <code>prev</code>, <code>i</code>, and
136<code>next</code>.
137</p>
138<p>The most basic local variable declaration looks like this:
139</p>
140<div class="example">
141<pre class="example"><var>type</var> <var>variablename</var>;
142</pre></div>
143
144<p>For instance,
145</p>
146<div class="example">
147<pre class="example">int i;
148</pre></div>
149
150<p>declares the local variable <code>i</code> as an integer.
151See <a href="Variable-Declarations.html">Variable Declarations</a>.
152</p>
153</dd>
154<dt>Initializers</dt>
155<dd><p>When you declare a variable, you can also specify its initial value,
156like this:
157</p>
158<div class="example">
159<pre class="example"><var>type</var> <var>variablename</var> = <var>value</var>;
160</pre></div>
161
162<p>For instance,
163</p>
164<div class="example">
165<pre class="example">int last = 1;
166</pre></div>
167
168<p>declares the local variable <code>last</code> as an integer (type
169<code>int</code>) and starts it off with the value 1. See <a href="Initializers.html">Initializers</a>.
170</p>
171</dd>
172<dt>Assignment</dt>
173<dd><p>Assignment: a specific kind of expression, written with the &lsquo;<samp>=</samp>&rsquo;
174operator, that stores a new value in a variable or other place. Thus,
175</p>
176<div class="example">
177<pre class="example"><var>variable</var> = <var>value</var>
178</pre></div>
179
180<p>is an expression that computes <code><var>value</var></code> and stores the value in
181<code><var>variable</var></code>. See <a href="Assignment-Expressions.html">Assignment Expressions</a>.
182</p>
183</dd>
184<dt>Expression statements</dt>
185<dd><p>An expression statement is an expression followed by a semicolon.
186That computes the value of the expression, then ignores the value.
187</p>
188<p>An expression statement is useful when the expression changes some
189data or has other side effects&mdash;for instance, with function calls, or
190with assignments as in this example. See <a href="Expression-Statement.html">Expression Statement</a>.
191</p>
192<p>Using an expression with no side effects in an expression statement is
193pointless except in very special cases. For instance, the expression
194statement <code>x;</code> would examine the value of <code>x</code> and ignore it.
195That is not useful.
196</p>
197</dd>
198<dt>Increment operator</dt>
199<dd><p>The increment operator is &lsquo;<samp>++</samp>&rsquo;. <code>++i</code> is an
200expression that is short for <code>i = i + 1</code>.
201See <a href="Increment_002fDecrement.html">Increment/Decrement</a>.
202</p>
203</dd>
204<dt><code>for</code> statements</dt>
205<dd><p>A <code>for</code> statement is a clean way of executing a statement
206repeatedly&mdash;a <em>loop</em> (see <a href="Loop-Statements.html">Loop Statements</a>). Specifically,
207</p>
208<div class="example">
209<pre class="example">for (i = 1; i &lt; n; ++i)
210 <var>body</var>
211</pre></div>
212
213<p>means to start by doing <code>i = 1</code> (set <code>i</code> to one) to prepare
214for the loop. The loop itself consists of
215</p>
216<ul>
217<li> Testing <code>i &lt; n</code> and exiting the loop if that&rsquo;s false.
218
219</li><li> Executing <var>body</var>.
220
221</li><li> Advancing the loop (executing <code>++i</code>, which increments <code>i</code>).
222</li></ul>
223
224<p>The net result is to execute <var>body</var> with 0 in <code>i</code>,
225then with 1 in <code>i</code>, and so on, stopping just before the repetition
226where <code>i</code> would equal <code>n</code>.
227</p>
228<p>The body of the <code>for</code> statement must be one and only one
229statement. You can&rsquo;t write two statements in a row there; if you try
230to, only the first of them will be treated as part of the loop.
231</p>
232<p>The way to put multiple statements in those places is to group them
233with a block, and that&rsquo;s what we do in this example.
234</p></dd>
235</dl>
236
237<hr>
238<div class="header">
239<p>
240Previous: <a href="Stack.html" accesskey="p" rel="prev">Stack</a>, Up: <a href="The-First-Example.html" accesskey="u" rel="up">The First Example</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Symbol-Index.html" title="Index" rel="index">Index</a>]</p>
241</div>
242
243
244
245</body>
246</html>
Note: See TracBrowser for help on using the repository browser.