一、背景
斐波那契数的定义:
二、分析
我引用两张表,大家一看便懂,
斐波那契数(C/C++,Scheme)
。1.递归
<code class="hljs" lisp="">(factorial 6)(* 6 (factorial 5))(* 6 (* 5 (factorial 4)))(* 6 (* 5 (* 4 (factorial 3))))(* 6 (* 5 (* 4 (* 3 (factorial 2)))))(* 6 (* 5 (* 4 (* 3 (2 (factorial 1))))))(* 6 (* 5 (* 4 (* 3 (* 2 1)))))(* 6 (* 5 (* 4 (* 3 2))))(* 6 (* 5 (* 4 6)))(* 6 (* 5 24))(* 6 120)720</code>
2.迭代
<code class="hljs" lisp="">(factorial 6)(factorial 1 1 6)(factorial 1 2 6)(factorial 2 3 6)(factorial 6 4 6)(factorial 24 5 6)(factorial 120 6 6)(factorial 720 7 6)720</code>
递归的核心在于:不断地回到起点。
迭代的核心在于:不断地更新参数。
在下面的代码中,递归的核心是sum的运算,sum不断的累乘,虽然运算的数值不同,但形式和意义一样。
而迭代的核心是product和counter的不断更新。如上表中,product就是factorial的前2个参数不断的累乘更新成第一个参数;而第二个参数则是counter,其不断的加1来更新自己。
product <- counter * product
counter < - counter + 1
三、代码
C语言版
<code class="hljs" perl="">#include<stdio.h>#include<stdlib.h>int factorialRecursive(int n);int factorialIteration(int product, int counter, int max_count);int main(){ int n; printf(Enter an integer: ); scanf(%d,&n); printf(%d,factorialRecursive(n)); printf(%d,factorialIteration(1,1,n)); return 0;}int factorialRecursive(int n){ int sum=1; if(n==1) sum*=1; else sum=n*factorialRecursive(n-1); return sum;}int factorialIteration(int product, int counter, int max_count){ int sum=1; if(counter>max_count) sum*=product; else factorialIteration((counter*product),(counter+1),max_count);}</stdlib.h></stdio.h></code>
C++语言版
<code class="hljs" cpp="">#include<iostream>using namespace std;int factorialRecursive(int n);int factorialIteration(int product, int counter, int max_count);int main(){ int n; cout<<enter an="" cin="">>n; cout<<factorialrecursive(n)<<endl; counter="" else="" int="" n="=1)" return="" sum="1;">max_count) sum*=product; else factorialIteration((counter*product),(counter+1),max_count);}</factorialrecursive(n)<<endl;></enter></iostream></code>
四、进阶
Scheme语言版
<code class="hljs" clojure="">(define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1)))))</code>
<code class="hljs" clojure="">(define (factorial n) (fact-iter 1 1 n))(define (fact-iter product counter max-count) (if (> counter max-count) product (fact-iter (* counter product) (+ counter 1) max-counter)))</code>