我们可以增加递归函数的参数,让函数在递归的时候带走更多信息。像是费氏数列,就可以让递归函数多加两个参数,来保存每次递归时第 #{{ n - 1 }}# 项的值和第 #{{ n }}# 项的值。如此一来就可以在每次递归时计算出下一项的值,并将这个值又作为下一次递归调用时的第 #{{ n }}# 项的值,同时也将原本第 #{{ n }}# 项的值作为下一次第 #{{ n - 1 }}# 项的值。而原本的参数 n 就会变成计次用途了。
static int fibonacciRecursively(final int counter, final int init, final int accumulator) {
if (counter == 0) {
return init;
} else {
return fibonacciRecursively(counter - 1, accumulator, init + accumulator);
}
}
public static int fibonacci(final int n) {
return fibonacciRecursively(n, 0, 1);
}
static int fibonacciRecursively(final int counter, final int init, final int accumulator) {
while (true) {
if (counter == 0) {
return init;
} else {
return fibonacciRecursively(counter - 1, accumulator, init + accumulator);
}
break;
}
}
public static int fibonacci(final int n) {
return fibonacciRecursively(n, 0, 1);
}
pub fn fibonacci(n: u32) -> u32 {
let mut init = 0;
let mut accumulator = 1;
for _ in 0..n {
let temp = accumulator;
accumulator += init;
init = temp;
}
init
}
public static int fibonacci(final int n) {
int init = 0;
int accumulator = 1;
for (int counter = 0; counter < n; ++counter) {
final int temp = accumulator;
accumulator += init;
init = temp;
}
return init;
}
function fibonacci(n: number) {
let init = 0;
let accumulator = 1;
for (let counter = 0;counter < n;counter++) {
const temp = accumulator;
accumulator += init;
init = temp;
}
return init;
}
我们可以将阶乘的第 #{{ n }}# 项移出,使得 #{{n! = n \times (n - 1)!}}#。如何?明显又是个递归函数了吧!
由于阶乘函数比费氏数列函数还要简单,所以直接看以下代码吧!
pub fn factorial_1(n: u32) -> u32 {
if n <= 1 {
1
} else {
n * factorial_1(n - 1)
}
}
fn factorial_2_recursively(n: u32, accumulator: u32) -> u32 {
if n <= 1 {
accumulator
} else {
factorial_2_recursively(n - 1, n * accumulator)
}
}
pub fn factorial_2(n: u32) -> u32 {
factorial_2_recursively(n, 1)
}
fn factorial_3_recursively(n: u32, accumulator: u32) -> u32 {
loop {
if n <= 1 {
return accumulator;
} else {
return factorial_3_recursively(n - 1, n * accumulator);
}
break;
}
}
pub fn factorial_3(n: u32) -> u32 {
factorial_3_recursively(n, 1)
}
fn factorial_4_inner(mut n: u32, mut accumulator: u32) -> u32 {
loop {
if n <= 1 {
return accumulator;
} else {
accumulator = n * accumulator;
n -= 1;
continue;
}
break;
}
}
pub fn factorial_4(n: u32) -> u32 {
factorial_4_inner(n, 1)
}
pub fn factorial_5(n: u32) -> u32 {
let mut accumulator = 1;
for i in 2..=n {
accumulator *= i;
}
accumulator
}
public static int factorial1(final int n) {
if (n <= 1) {
return 1;
} else {
return n * factorial1(n - 1);
}
}
static int factorial2Recursively(final int n, final int accumulator) {
if (n <= 1) {
return accumulator;
} else {
return factorial2Recursively(n - 1, n * accumulator);
}
}
public static int factorial2(final int n) {
return factorial2Recursively(n, 1);
}
static int factorial3Recursively(final int n, final int accumulator) {
while (true) {
if (n <= 1) {
return accumulator;
} else {
return factorial3Recursively(n - 1, n * accumulator);
}
break;
}
}
public static int factorial3(final int n) {
return factorial3Recursively(n, 1);
}
static int factorial4Inner(int n, int accumulator) {
while (true) {
if (n <= 1) {
return accumulator;
} else {
accumulator *= n;
--n;
continue;
}
break;
}
}
public static int factorial4(final int n) {
return factorial4Inner(n, 1);
}
public static int factorial5(final int n) {
int accumulator = 1;
for (int i = 2; i <= n; ++i) {
accumulator *= i;
}
return accumulator;
}
function factorial1(n: number) {
if (n <= 1) {
return 1;
} else {
return n * factorial1(n - 1);
}
}
function factorial2Recursively(n: number, accumulator: number) {
if (n <= 1) {
return accumulator;
} else {
return factorial2Recursively(n - 1, n * accumulator);
}
}
function factorial2(n: number) {
return factorial2Recursively(n, 1);
}
function factorial3Recursively(n: number, accumulator: number) {
for (; ;) {
if (n <= 1) {
return accumulator;
} else {
return factorial3Recursively(n - 1, n * accumulator);
}
break;
}
}
function factorial3(n: number) {
return factorial3Recursively(n, 1);
}
function factorial4Inner(n: number, accumulator: number) {
for (; ;) {
if (n <= 1) {
return accumulator;
} else {
accumulator *= n;
--n;
continue;
}
break;
}
}
function factorial4(n: number) {
return factorial4Inner(n, 1);
}
function factorial5(n: number) {
let accumulator = 1;
for (let i = 2;i <= n;i++) {
accumulator *= i;
}
return accumulator;
}
func Factorial1(n int) int {
if n <= 1 {
return 1
} else {
return n * Factorial1(n-1)
}
}
func factorial2Recursively(n int, accumulator int) int {
if n <= 1 {
return accumulator
} else {
return factorial2Recursively(n-1, n*accumulator)
}
}
func Factorial2(n int) int {
return factorial2Recursively(n, 1)
}
func factorial3Recursively(n int, accumulator int) int {
for {
if n <= 1 {
return accumulator
} else {
return factorial3Recursively(n-1, n*accumulator)
}
break
}
}
func Factorial3(n int) int {
return factorial3Recursively(n, 1)
}
func factorial4Inner(n int, accumulator int) int {
for {
if n <= 1 {
return accumulator
} else {
accumulator *= n
n--
continue
}
break
}
}
func Factorial4(n int) int {
return factorial4Inner(n, 1)
}
func Factorial5(n int) int {
accumulator := 1
for i := 2; i <= n; i++ {
accumulator *= i
}
return accumulator
}
pub fn binary_search_1(array: &[i32], target_element: i32, start: usize, end: usize) -> Option<usize> {
let middle = (end + start) / 2;
let element = array[middle];
if element == target_element {
Some(middle)
} else if end <= start {
None
} else {
if target_element > element {
binary_search_1(array, target_element, middle + 1, end)
} else {
if middle > 0 {
binary_search_1(array, target_element, start, middle - 1)
} else {
None
}
}
}
}
pub fn binary_search_3(array: &[i32], target_element: i32, start: usize, end: usize) -> Option<usize> {
loop {
let middle = (end + start) / 2;
let element = array[middle];
if element == target_element {
Some(middle)
} else if end <= start {
None
} else {
if target_element > element {
binary_search_3(array, target_element, middle + 1, end)
} else {
if middle > 0 {
binary_search_3(array, target_element, start, middle - 1)
} else {
None
}
}
}
break;
}
}
pub fn binary_search_4(array: &[i32], target_element: i32, mut start: usize, mut end: usize) -> Option<usize> {
loop {
let middle = (end + start) / 2;
let element = array[middle];
if element == target_element {
Some(middle)
} else if end <= start {
None
} else {
if target_element > element {
start = middle + 1;
continue;
} else {
if middle > 0 {
end = middle - 1;
continue;
} else {
None
}
}
}
break;
}
}
pub fn binary_search_5(array: &[i32], target_element: i32, mut start: usize, mut end: usize) -> Option<usize> {
while end >= start {
let middle = (end + start) / 2;
let element = array[middle];
if element == target_element {
return Some(middle);
} else {
if target_element > element {
start = middle + 1;
} else {
if middle > 0 {
end = middle - 1;
} else {
return None;
}
}
}
}
None
}
public static int binarySearch1(final int[] array, final int targetElement, final int start, final int end) {
final int middle = (end + start) / 2;
final int element = array[middle];
if (element == targetElement) {
return middle;
} else if (end <= start) {
return -1;
} else {
if (targetElement > element) {
return binarySearch1(array, targetElement, middle + 1, end);
} else {
return binarySearch1(array, targetElement, start, middle - 1);
}
}
}
public static int binarySearch3(final int[] array, final int targetElement, final int start, final int end) {
while (true) {
final int middle = (end + start) / 2;
final int element = array[middle];
if (element == targetElement) {
return middle;
} else if (end <= start) {
return -1;
} else {
if (targetElement > element) {
return binarySearch3(array, targetElement, middle + 1, end);
} else {
return binarySearch3(array, targetElement, start, middle - 1);
}
}
break;
}
}
public static int binarySearch4(final int[] array, final int targetElement, int start, int end) {
while (true) {
final int middle = (end + start) / 2;
final int element = array[middle];
if (element == targetElement) {
return middle;
} else if (end <= start) {
return -1;
} else {
if (targetElement > element) {
start = middle + 1;
continue;
} else {
end = middle - 1;
continue;
}
}
break;
}
}
public static int binarySearch5(final int[] array, final int targetElement, int start, int end) {
while (end >= start) {
final int middle = (end + start) / 2;
final int element = array[middle];
if (element == targetElement) {
return middle;
} else {
if (targetElement > element) {
start = middle + 1;
} else {
end = middle - 1;
}
}
}
return -1;
}
static int step(final int n) {
return n * factorial(n - 1);
}
public static int factorial(final int n) {
if (n <= 1) {
return 1;
} else {
return step(n);
}
}
function step(n: number): number {
return n * factorial(n - 1);
}
function factorial(n: number) {
if (n <= 1) {
return 1;
} else {
return step(n);
}
}
func step(n int) int {
return n * Factorial(n-1)
}
func Factorial(n int) int {
if n <= 1 {
return 1
} else {
return step(n)
}
}
步骤二:拆解子进程的程序叙述
将子进程的步骤分为三大部份:递归调用(取得前项结果)、计算目前这项的结果,以及回传结果。
代码如下:
fn step(n: u32) -> u32 {
let previous_x = factorial(n - 1);
let x = n * previous_x;
x
}
pub fn factorial(n: u32) -> u32 {
if n <= 1 {
1
} else {
step(n)
}
}
static int step(final int n) {
final int previousX = factorial(n - 1);
final int x = n * previousX;
return x;
}
public static int factorial(final int n) {
if (n <= 1) {
return 1;
} else {
return step(n);
}
}
function step(n: number) {
const previousX = factorial(n - 1);
const x = n * previousX;
return x;
}
function factorial(n: number): number {
if (n <= 1) {
return 1;
} else {
return step(n);
}
}
func step(n int) int {
previousX := Factorial(n - 1)
x := n * previousX
return x
}
func Factorial(n int) int {
if n <= 1 {
return 1
} else {
return step(n)
}
}
fn step(n: u32, previous_x: Option<u32>) -> u32 {
let previous_x = if let Some(previous_x) = previous_x {
previous_x
} else {
factorial(n - 1)
};
let x = n * previous_x;
x
}
pub fn factorial(n: u32) -> u32 {
if n <= 1 {
1
} else {
step(n, None)
}
}
static int step(final int n, final Optional<Integer> previousX) {
final int iPreviousX;
if (previousX.isPresent()) {
iPreviousX = previousX.get();
} else {
iPreviousX = factorial(n - 1);
}
final int x = n * iPreviousX;
return x;
}
public static int factorial(final int n) {
if (n <= 1) {
return 1;
} else {
return step(n, Optional.empty());
}
}
function step(n: number, previousX?: number) {
if (typeof previousX !== "number") {
previousX = factorial(n - 1);
}
const x = n * previousX;
return x;
}
function factorial(n: number): number {
if (n <= 1) {
return 1;
} else {
return step(n);
}
}
func step(n int, previousX ...int) int {
var iPreviousX int
if len(previousX) > 0 {
iPreviousX = previousX[0]
} else {
iPreviousX = Factorial(n - 1)
}
x := n * iPreviousX
return x
}
func Factorial(n int) int {
if n <= 1 {
return 1
} else {
return step(n)
}
}
fn step(n: u32, previous_x: Option<u32>) -> (u32, u32) {
let previous_x = if let Some(previous_x) = previous_x {
previous_x
} else {
factorial(n - 1)
};
let x = n * previous_x;
(n + 1, x)
}
pub fn factorial(n: u32) -> u32 {
if n <= 1 {
1
} else {
step(n, None).1
}
}
static int[] step(final int n, final Optional<Integer> previousX) {
final int iPreviousX;
if (previousX.isPresent()) {
iPreviousX = previousX.get();
} else {
iPreviousX = factorial(n - 1);
}
final int x = n * iPreviousX;
return new int[]{n + 1, x};
}
public static int factorial(final int n) {
if (n <= 1) {
return 1;
} else {
return step(n, Optional.empty())[1];
}
}
function step(n: number, previousX?: number) {
if (typeof previousX !== "number") {
previousX = factorial(n - 1);
}
const x = n * previousX;
return [n + 1, x];
}
function factorial(n: number): number {
if (n <= 1) {
return 1;
} else {
return step(n)[1];
}
}
func step(n int, previousX ...int) (int, int) {
var iPreviousX int
if len(previousX) > 0 {
iPreviousX = previousX[0]
} else {
iPreviousX = Factorial(n - 1)
}
x := n * iPreviousX
return n + 1, x
}
func Factorial(n int) int {
if n <= 1 {
return 1
} else {
_, x := step(n)
return x
}
}
fn step(n: u32, previous_x: Option<u32>) -> (u32, u32) {
let previous_x = if let Some(previous_x) = previous_x {
previous_x
} else {
factorial(n - 1)
};
let x = n * previous_x;
(n + 1, x)
}
pub fn factorial(n: u32) -> u32 {
if n <= 1 {
1
} else {
let t = n;
let (mut n, mut previous_x) = (1, 1);
for _ in 0..t {
let (next_n, x) = step(n, Some(previous_x));
n = next_n;
previous_x = x;
}
previous_x
}
}
static int[] step(final int n, final Optional<Integer> previousX) {
final int iPreviousX;
if (previousX.isPresent()) {
iPreviousX = previousX.get();
} else {
iPreviousX = factorial(n - 1);
}
final int x = n * iPreviousX;
return new int[]{n + 1, x};
}
public static int factorial(final int n) {
if (n <= 1) {
return 1;
} else {
final int t = n;
int nn = 1;
int previousX = 1;
for (int i = 0; i < t; ++i) {
final int[] r = step(nn, Optional.of(previousX));
nn = r[0];
previousX = r[1];
}
return previousX;
}
}
function step(n: number, previousX?: number) {
if (typeof previousX !== "number") {
previousX = factorial(n - 1);
}
const x = n * previousX;
return [n + 1, x];
}
function factorial(n: number) {
if (n <= 1) {
return 1;
} else {
const t = n;
let nn = 1;
let previousX = 1;
for (let i = 0;i < t;i++) {
[nn, previousX] = step(nn, previousX);
}
return previousX;
}
}
func step(n int, previousX ...int) (int, int) {
var iPreviousX int
if len(previousX) > 0 {
iPreviousX = previousX[0]
} else {
iPreviousX = Factorial(n - 1)
}
x := n * iPreviousX
return n + 1, x
}
func Factorial(n int) int {
if n <= 1 {
return 1
} else {
t := n
nn := 1
previousX := 1
for i := 0; i < t; i++ {
nn, previousX = step(nn, previousX)
}
return previousX
}
}
步骤六:整理代码
观察我们目前写出来的代码,其实不难发现,因为一开始就有给子进程计算目前这项数值时会用到的前项数值,所以子进程完全不会进入递归调用的流程,所以这部份的代码可以直接拿掉了。再来就是递归关系数列的基础项,原先有用 if 等关键字事先判断,也可以视情况将其移除。
于是我们可以将代码整理如下:
fn step(n: u32, previous_x: u32) -> (u32, u32) {
let x = n * previous_x;
(n + 1, x)
}
pub fn factorial(n: u32) -> u32 {
let t = n;
let (mut n, mut previous_x) = (1, 1);
for _ in 0..t {
let (next_n, x) = step(n, previous_x);
n = next_n;
previous_x = x;
}
previous_x
}
static int[] step(final int n, final int previousX) {
final int x = n * previousX;
return new int[]{n + 1, x};
}
public static int factorial(final int n) {
final int t = n;
int nn = 1;
int previousX = 1;
for (int i = 0; i < t; ++i) {
final int[] r = step(nn, previousX);
nn = r[0];
previousX = r[1];
}
return previousX;
}
function step(n: number, previousX: number) {
const x = n * previousX;
return [n + 1, x];
}
function factorial(n: number) {
const t = n;
let nn = 1;
let previousX = 1;
for (let i = 0;i < t;i++) {
[nn, previousX] = step(nn, previousX);
}
return previousX;
}
func step(n int, previousX int) (int, int) {
x := n * previousX
return n + 1, x
}
func Factorial(n int) int {
t := n
nn := 1
previousX := 1
for i := 0; i < t; i++ {
nn, previousX = step(nn, previousX)
}
return previousX
}
pub fn factorial(n: u32) -> u32 {
let t = n;
let (mut n, mut previous_x) = (1, 1);
for _ in 0..t {
previous_x *= n;
n += 1;
}
previous_x
}
public static int factorial(final int n) {
final int t = n;
int nn = 1;
int previousX = 1;
for (int i = 0; i < t; ++i) {
previousX *= nn;
++nn;
}
return previousX;
}
function factorial(n: number) {
const t = n;
let nn = 1;
let previousX = 1;
for (let i = 0;i < t;i++) {
previousX *= nn;
nn += 1;
}
return previousX;
}
func Factorial(n int) int {
t := n
nn := 1
previousX := 1
for i := 0; i < t; i++ {
previousX *= nn
nn++
}
return previousX
}
步骤八:再次整理代码
内联之后的迭代函数,可能会有一些冗余的地方可以进行合并与删减。
整理一下后,代码最终会变成:
pub fn factorial(n: u32) -> u32 {
let mut previous_x = 1;
for i in 2..=n {
previous_x *= i;
}
previous_x
}
public static int factorial(final int n) {
int previousX = 1;
for (int i = 2; i <= n; ++i) {
previousX *= i;
}
return previousX;
}
function factorial(n: number) {
let previousX = 1;
for (let i = 2;i <= n;i++) {
previousX *= i;
}
return previousX;
}
func Factorial(n int) int {
previousX := 1
for i := 2; i <= n; i++ {
previousX *= i
}
return previousX
}
更多的转换例子
有递归关系的数列函数基本上都可以尝试使用上面的流程来转换成迭代函数,以下再举别的例子。
费氏数列
本篇文章最一开始就有详细说明费氏数列的递归函数转迭代函数的方式,现在则要改用第二种方式来进行转换。
直接看以下代码吧!
fn step_1(n: u32) -> u32 {
fibonacci_1(n - 1) + fibonacci_1(n - 2)
}
pub fn fibonacci_1(n: u32) -> u32 {
match n {
0 => 0,
1 => 1,
n => step_1(n),
}
}
fn step_2(n: u32) -> u32 {
let previous_x = fibonacci_2(n - 1);
let before_previous_x = fibonacci_2(n - 2);
let x = previous_x + before_previous_x;
x
}
pub fn fibonacci_2(n: u32) -> u32 {
match n {
0 => 0,
1 => 1,
n => step_2(n),
}
}
fn step_3(n: u32, previous_x: Option<u32>, before_previous_x: Option<u32>) -> u32 {
let previous_x = if let Some(previous_x) = previous_x {
previous_x
} else {
fibonacci_3(n - 1)
};
let before_previous_x = if let Some(before_previous_x) = before_previous_x {
before_previous_x
} else {
fibonacci_3(n - 2)
};
let x = previous_x + before_previous_x;
x
}
pub fn fibonacci_3(n: u32) -> u32 {
match n {
0 => 0,
1 => 1,
n => step_3(n, None, None),
}
}
fn step_4(n: u32, previous_x: Option<u32>, before_previous_x: Option<u32>) -> (u32, u32, u32) {
let previous_x = if let Some(previous_x) = previous_x {
previous_x
} else {
fibonacci_4(n - 1)
};
let before_previous_x = if let Some(before_previous_x) = before_previous_x {
before_previous_x
} else {
fibonacci_4(n - 2)
};
let x = previous_x + before_previous_x;
(n + 1, previous_x, x)
}
pub fn fibonacci_4(n: u32) -> u32 {
match n {
0 => 0,
1 => 1,
n => step_4(n, None, None).2,
}
}
fn step_5(n: u32, previous_x: Option<u32>, before_previous_x: Option<u32>) -> (u32, u32, u32) {
let previous_x = if let Some(previous_x) = previous_x {
previous_x
} else {
fibonacci_5(n - 1)
};
let before_previous_x = if let Some(before_previous_x) = before_previous_x {
before_previous_x
} else {
fibonacci_5(n - 2)
};
let x = previous_x + before_previous_x;
(n + 1, previous_x, x)
}
pub fn fibonacci_5(n: u32) -> u32 {
match n {
0 => 0,
1 => 1,
n => {
let t = n - 1;
let (mut n, mut previous_x, mut before_previous_x) = (2, 1, 0);
for _ in 0..t {
let (next_n, next_before_previous_x, x) = step_5(n, Some(previous_x), Some(before_previous_x));
n = next_n;
previous_x = x;
before_previous_x = next_before_previous_x;
}
previous_x
}
}
}
fn step_6(n: u32, previous_x: u32, before_previous_x: u32) -> (u32, u32, u32) {
let x = previous_x + before_previous_x;
(n + 1, previous_x, x)
}
pub fn fibonacci_6(n: u32) -> u32 {
match n {
0 => 0,
n => {
let t = n - 1;
let (mut n, mut previous_x, mut before_previous_x) = (2, 1, 0);
for _ in 0..t {
let (next_n, next_before_previous_x, x) = step_6(n, previous_x, before_previous_x);
n = next_n;
previous_x = x;
before_previous_x = next_before_previous_x;
}
previous_x
}
}
}
pub fn fibonacci_7(n: u32) -> u32 {
match n {
0 => 0,
n => {
let t = n - 1;
let (mut n, mut previous_x, mut before_previous_x) = (2, 1, 0);
for _ in 0..t {
let x = previous_x + before_previous_x;
n += 1;
before_previous_x = previous_x;
previous_x = x;
}
previous_x
}
}
}
pub fn fibonacci_8(n: u32) -> u32 {
match n {
0 => 0,
n => {
let (mut previous_x, mut before_previous_x) = (1, 0);
for _ in 1..n {
let x = previous_x + before_previous_x;
before_previous_x = previous_x;
previous_x = x;
}
previous_x
}
}
}
static int step1(final int n) {
return fibonacci1(n - 1) + fibonacci1(n - 2);
}
public static int fibonacci1(final int n) {
switch (n) {
case 0:
return 0;
case 1:
return 1;
default:
return step1(n);
}
}
static int step2(final int n) {
final int previousX = fibonacci2(n - 1);
final int beforePreviousX = fibonacci2(n - 2);
final int x = previousX + beforePreviousX;
return x;
}
public static int fibonacci2(final int n) {
switch (n) {
case 0:
return 0;
case 1:
return 1;
default:
return step2(n);
}
}
static int step3(final int n, final Optional<Integer> previousX, final Optional<Integer> beforePreviousX) {
final int iPreviousX, iBeforePreviousX;
if (previousX.isPresent()) {
iPreviousX = previousX.get();
} else {
iPreviousX = fibonacci3(n - 1);
}
if (beforePreviousX.isPresent()) {
iBeforePreviousX = beforePreviousX.get();
} else {
iBeforePreviousX = fibonacci3(n - 2);
}
final int x = iPreviousX + iBeforePreviousX;
return x;
}
public static int fibonacci3(final int n) {
switch (n) {
case 0:
return 0;
case 1:
return 1;
default:
return step3(n, Optional.empty(), Optional.empty());
}
}
static int[] step4(final int n, final Optional<Integer> previousX, final Optional<Integer> beforePreviousX) {
final int iPreviousX, iBeforePreviousX;
if (previousX.isPresent()) {
iPreviousX = previousX.get();
} else {
iPreviousX = fibonacci4(n - 1);
}
if (beforePreviousX.isPresent()) {
iBeforePreviousX = beforePreviousX.get();
} else {
iBeforePreviousX = fibonacci4(n - 2);
}
final int x = iPreviousX + iBeforePreviousX;
return new int[]{n + 1, iPreviousX, x};
}
public static int fibonacci4(final int n) {
switch (n) {
case 0:
return 0;
case 1:
return 1;
default:
return step4(n, Optional.empty(), Optional.empty())[2];
}
}
static int[] step5(final int n, final Optional<Integer> previousX, final Optional<Integer> beforePreviousX) {
final int iPreviousX, iBeforePreviousX;
if (previousX.isPresent()) {
iPreviousX = previousX.get();
} else {
iPreviousX = fibonacci5(n - 1);
}
if (beforePreviousX.isPresent()) {
iBeforePreviousX = beforePreviousX.get();
} else {
iBeforePreviousX = fibonacci5(n - 2);
}
final int x = iPreviousX + iBeforePreviousX;
return new int[]{n + 1, iPreviousX, x};
}
public static int fibonacci5(final int n) {
switch (n) {
case 0:
return 0;
case 1:
return 1;
default:
final int t = n - 1;
int nn = 2;
int previousX = 1;
int beforePreviousX = 0;
for (int i = 0; i < t; ++i) {
final int[] r = step5(nn, Optional.of(previousX), Optional.of(beforePreviousX));
nn = r[0];
previousX = r[2];
beforePreviousX = r[1];
}
return previousX;
}
}
static int[] step6(int n, final int previousX, final int beforePreviousX) {
final int x = previousX + beforePreviousX;
return new int[]{n + 1, previousX, x};
}
public static int fibonacci6(final int n) {
switch (n) {
case 0:
return 0;
default:
final int t = n - 1;
int nn = 2;
int previousX = 1;
int beforePreviousX = 0;
for (int i = 0; i < t; ++i) {
final int[] r = step6(nn, previousX, beforePreviousX);
nn = r[0];
previousX = r[2];
beforePreviousX = r[1];
}
return previousX;
}
}
public static int fibonacci7(final int n) {
switch (n) {
case 0:
return 0;
default:
final int t = n - 1;
int nn = 2;
int previousX = 1;
int beforePreviousX = 0;
for (int i = 0; i < t; ++i) {
final int x = previousX + beforePreviousX;
++nn;
beforePreviousX = previousX;
previousX = x;
}
return previousX;
}
}
public static int fibonacci8(final int n) {
switch (n) {
case 0:
return 0;
default:
int previousX = 1;
int beforePreviousX = 0;
for (int i = 1; i < n; ++i) {
final int x = previousX + beforePreviousX;
beforePreviousX = previousX;
previousX = x;
}
return previousX;
}
}
function step1(n: number) {
return fibonacci1(n - 1) + fibonacci1(n - 2);
}
function fibonacci1(n: number): number {
switch (n) {
case 0:
return 0;
case 1:
return 1;
default:
return step1(n);
}
}
function step2(n: number) {
const previousX = fibonacci2(n - 1);
const beforePreviousX = fibonacci2(n - 2);
const x = previousX + beforePreviousX;
return x;
}
function fibonacci2(n: number): number {
switch (n) {
case 0:
return 0;
case 1:
return 1;
default:
return step2(n);
}
}
function step3(n: number, previousX?: number, beforePreviousX?: number) {
if (typeof previousX !== "number") {
previousX = fibonacci3(n - 1);
}
if (typeof beforePreviousX !== "number") {
beforePreviousX = fibonacci3(n - 2);
}
const x = previousX + beforePreviousX;
return x;
}
function fibonacci3(n: number): number {
switch (n) {
case 0:
return 0;
case 1:
return 1;
default:
return step3(n);
}
}
function step4(n: number, previousX?: number, beforePreviousX?: number) {
if (typeof previousX !== "number") {
previousX = fibonacci4(n - 1);
}
if (typeof beforePreviousX !== "number") {
beforePreviousX = fibonacci4(n - 2);
}
const x = previousX + beforePreviousX;
return [n + 1, previousX, x];
}
function fibonacci4(n: number): number {
switch (n) {
case 0:
return 0;
case 1:
return 1;
default:
return step4(n)[2];
}
}
function step5(n: number, previousX?: number, beforePreviousX?: number) {
if (typeof previousX !== "number") {
previousX = fibonacci5(n - 1);
}
if (typeof beforePreviousX !== "number") {
beforePreviousX = fibonacci5(n - 2);
}
const x = previousX + beforePreviousX;
return [n + 1, previousX, x];
}
function fibonacci5(n: number) {
switch (n) {
case 0:
return 0;
case 1:
return 1;
default: {
const t = n - 1;
let nn = 2;
let previousX = 1;
let beforePreviousX = 0;
for (let i = 0;i < t;i++) {
[nn, beforePreviousX, previousX] = step5(nn, previousX, beforePreviousX);
}
return previousX;
}
}
}
function step6(n: number, previousX: number, beforePreviousX: number) {
const x = previousX + beforePreviousX;
return [n + 1, previousX, x];
}
function fibonacci6(n: number) {
switch (n) {
case 0:
return 0;
default: {
const t = n - 1;
let nn = 2;
let previousX = 1;
let beforePreviousX = 0;
for (let i = 0;i < t;i++) {
[nn, beforePreviousX, previousX] = step6(nn, previousX, beforePreviousX);
}
return previousX;
}
}
}
function fibonacci7(n: number) {
switch (n) {
case 0:
return 0;
default: {
const t = n - 1;
let nn = 2;
let previousX = 1;
let beforePreviousX = 0;
for (let i = 0;i < t;i++) {
const x = previousX + beforePreviousX;
nn += 1;
beforePreviousX = previousX;
previousX = x;
}
return previousX;
}
}
}
function fibonacci8(n: number) {
switch (n) {
case 0:
return 0;
default: {
let previousX = 1;
let beforePreviousX = 0;
for (let i = 1;i < n;i++) {
const x = previousX + beforePreviousX;
beforePreviousX = previousX;
previousX = x;
}
return previousX;
}
}
}
func step1(n int) int {
return Fibonacci1(n-1) + Fibonacci1(n-2)
}
func Fibonacci1(n int) int {
switch n {
case 0:
return 0
case 1:
return 1
default:
return step1(n)
}
}
func step2(n int) int {
previousX := Fibonacci2(n - 1)
beforePreviousX := Fibonacci2(n - 2)
x := previousX + beforePreviousX
return x
}
func Fibonacci2(n int) int {
switch n {
case 0:
return 0
case 1:
return 1
default:
return step2(n)
}
}
func step3(n int, previous ...int) int {
var previousX, beforePreviousX int
if len(previous) > 0 {
previousX = previous[0]
} else {
previousX = Fibonacci3(n - 1)
}
if len(previous) > 1 {
beforePreviousX = previous[1]
} else {
beforePreviousX = Fibonacci3(n - 2)
}
x := previousX + beforePreviousX
return x
}
func Fibonacci3(n int) int {
switch n {
case 0:
return 0
case 1:
return 1
default:
return step3(n)
}
}
func step4(n int, previous ...int) (int, int, int) {
var previousX, beforePreviousX int
if len(previous) > 0 {
previousX = previous[0]
} else {
previousX = Fibonacci4(n - 1)
}
if len(previous) > 1 {
beforePreviousX = previous[1]
} else {
beforePreviousX = Fibonacci4(n - 2)
}
x := previousX + beforePreviousX
return n + 1, previousX, x
}
func Fibonacci4(n int) int {
switch n {
case 0:
return 0
case 1:
return 1
default:
_, _, x := step4(n)
return x
}
}
func step5(n int, previous ...int) (int, int, int) {
var previousX, beforePreviousX int
if len(previous) > 0 {
previousX = previous[0]
} else {
previousX = Fibonacci5(n - 1)
}
if len(previous) > 1 {
beforePreviousX = previous[1]
} else {
beforePreviousX = Fibonacci5(n - 2)
}
x := previousX + beforePreviousX
return n + 1, previousX, x
}
func Fibonacci5(n int) int {
switch n {
case 0:
return 0
case 1:
return 1
default:
t := n - 1
nn := 2
previousX := 1
beforePreviousX := 0
for i := 0; i < t; i++ {
nn, beforePreviousX, previousX = step5(nn, previousX, beforePreviousX)
}
return previousX
}
}
func step6(n int, previousX int, beforePreviousX int) (int, int, int) {
x := previousX + beforePreviousX
return n + 1, previousX, x
}
func Fibonacci6(n int) int {
switch n {
case 0:
return 0
default:
t := n - 1
nn := 2
previousX := 1
beforePreviousX := 0
for i := 0; i < t; i++ {
nn, beforePreviousX, previousX = step6(nn, previousX, beforePreviousX)
}
return previousX
}
}
func Fibonacci7(n int) int {
switch n {
case 0:
return 0
default:
t := n - 1
nn := 2
previousX := 1
beforePreviousX := 0
for i := 0; i < t; i++ {
x := previousX + beforePreviousX
nn++
beforePreviousX = previousX
previousX = x
}
return previousX
}
}
func Fibonacci8(n int) int {
switch n {
case 0:
return 0
default:
previousX := 1
beforePreviousX := 0
for i := 1; i < n; i++ {
x := previousX + beforePreviousX
beforePreviousX = previousX
previousX = x
}
return previousX
}
}
以上这种递归函数的结构是最简单的,我们只需要先用总是可以被运行的循环来将原本递归函数主体中的所有程序叙述包起来,然后在这个循环外的上方创建一个堆栈空间,把传进递归函数的参数 push 到堆栈空间中(只需存会有变化的参数)。接着在刚才加上的循环内,一开始的时候去 pop 这些参数,用这些参数去做原本该做的事,最后反转(因为堆栈是先进后出)递归调用的部份,并且将递归调用的程序叙述都改成把递归调用时的参数 push 到堆栈空间中。若循环一开始无法从堆栈空间中 pop 到参数,就跳出循环。
所以之后形成的迭代函数看起来会像以下这样:
void f(param1, param2, ..., paramN) {
stack = Empty Stack;
push param1, param2, ..., paramN to stack
loop {
pop param1, param2, ..., paramN from stack, if pop nothing then break
// do something
push aaa, bbb, ..., nnn to stack // recursive call n
// ...
push aa, bb, ..., nn to stack // recursive call 2
push a, b, ..., n to stack // recursive call 1
}
}
在第一部份的循环内,一开始要先去 pop 第一个堆栈空间中的这些参数,接着将递归调用的程序叙述都改成把递归调用时的参数 push 到堆栈空间中,最后再把参数 push 进第二个堆栈空间内。若循环一开始无法从第一个堆栈空间中 pop 到参数,就跳出循环。
而在第二部份的循环内,一开始要先去 pop 第二个堆栈空间中的参数,并用这些参数去做原本该做的事。若循环一开始无法从第二个堆栈空间中 pop 到参数,就跳出循环。
所以之后形成的迭代函数看起来会像以下这样:
void f(param1, param2, ..., paramN) {
stack1 = Empty Stack;
stack2 = Empty Stack;
push param1, param2, ..., paramN to stack1
loop {
pop param1, param2, ..., paramN from stack1, if pop nothing then break
push a, b, ..., n to stack1 // recursive call 1
push aa, bb, ..., nn to stack1 // recursive call 2
// ...
push aaa, bbb, ..., nnn to stack1 // recursive call n
push param1, param2, ..., paramN to stack2
}
loop {
pop param1, param2, ..., paramN from stack2, if pop nothing then break
// do something
}
}