[第999关] 递归算法

递归

https://blog.csdn.net/sinat_38052999/article/details/73303111

## 三要素

• 明确递归终止条件
• 给出递归终止时的处理方法
• 提取重复的逻辑，缩小问题规模

## 算法模型
在递去的过程中解决问题

在归去的过程中解决问题

## 递归与循环
* 递归问题一般都可以转换为循环问题处理
* 循环比递归效率更高

## 例子
### 阶乘问题
描述 
F(n) = n * (n-1) * (n-2) *…1
F(n-1) = (n-1) * (n – 2) * … 1
F(n) = n * F(n-1)

递归实现
autohotkey v2

#include <log4ahk> ;https://www.autoahk.com/archives/36659

loop(10)
{
    log.info(f(A_Index))
    log.info(f1(A_Index))
}

;递归实现
f(n)
{
    if(n == 1)
        return 1
    return n * f(n - 1)
}
;非递归实现
f1(n)
{
    result := 1
    loop(n)
        result *= A_Index
    return result
}

结果

### 斐波那契数列
Description: 斐波纳契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……

在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）。

两种递归解法：经典解法和优化解法
两种非递归解法：递推法和数组法

autohotkey v2

;autohotkey v2
#include <log4ahk> ;https://www.autoahk.com/archives/36659
ar := []
ar1 := []
loop(10)
{
    ar.push(fb(a_index))
    ar1.push(fb1(a_index))
}
log.info(ar)
log.info(ar1)

;递归
fb(n)
{
    if(n == 1 || n == 2)
        return 1
    return fb(n - 1) + fb(n - 2)
}
;非递归
fb1(n)
{
    result := -1
    first := 1
    second := 1
    if(n == 1 || n == 2)
        return 1
    loop(n - 2)
    {
        result := first + second
        first := second
        second := result
    }
    return result
}