tags: FoShiShi

遞迴

What

就跟數學中的遞迴一樣
只是用程式做出來

遞迴(recursion) 的函式包含以下兩種性質

  1. 該函式包含自己:會在函式中呼叫自己,並一直步步接近終止條件
  2. 該函式有一定的終止條件:呼叫函式的最後會終止(不然他就會無限的跑下去然後爛掉)

例:費氏數列(Fibonacci Sequence)

費氏數列的性質如下

Fib(n)={1if  n=11if  n=2Fib(n1)+Fib(n2)else

  1. 該函式包含自己:在else的時候會呼叫自己兩次
  2. 該函式有一定的終止條件:在n = 1 or n = 2時會終止並回傳1

可以想像成一個樹狀圖(以求

Fib(4)為例)

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

When

當我們問題本身的答案需要他子問題的答案來得知的時候
例:費氏數列(數列中前兩項相加)、階乘(n! = n * (n - 1)! and 1! = 1)

How

這裡先用階乘的實作來做說明

首先我們需要一個有引入值的函式

int f(int x) { ; }

再來宣告終止條件

int f(int x) { if(x == 1) { return 1; } }

然後讓遞迴式包含自己並使其趨近終止條件

int f(int x) { if(x == 1) { return 1; } else { return x * f(x - 1); } }

以上就是階乘的遞迴式

之後就可以在主函式呼叫這個遞迴式

#include<iostream> using namespace std; int f(int x) { if(x == 1) { return 1; } else { return x * f(x - 1); } } int main() { cout << f(1) << endl; // 1 cout << f(5) << endl; // 120 }

補充:費氏數列數列遞迴式

int fib(int x) { if(x == 1 || x == 2) { return 1; } else { return fib(x - 1) + fib(x - 2); } }

實際應用

題目1

建構一個遞迴函式
符合此遞迴式:

Fib(n)={1if  n=12if  n=23if  n=3Fib(n1)+Fib(n2)Fib(n3)else

solution

照著上述遞迴式
設定終止條件與包含自己

#include<iostream> using namespace std; int Fib(int n) { if(n == 1) { return 1; } if(n == 2) { return 2; } if(n == 3) { return 3; } else { return Fib(n - 1) + Fib(n - 2) * Fib(n - 3); } } int main() { ... }