軼代和遞迴Iterative and Recursive

遞迴的整體概念是把同樣類似重複的工作,分拆到最小的單位來做,然後慢慢把小單位的結果集合成大單位的結果,然後成為答案.
遞迴要有兩個要素:1.基本元素,也可說是終止條件 2.遞迴判斷條件,
例如:2^0 =1; 2^1=2*2^0; 2^2=2*2^1, 2^3=2*2^2,到最後我們可以歸納為
x^0=1,這個就是基本條件, 又若n>0的話, x^n=x*x^n-1;這個就是遞迴條件.
以下是以n的幾次方分別用用遞迴和軼代的方式來實作的程式碼:

#include <iostream>
using namespace std;

int recursive(int, int);

int main() {
 cout << recursive(2,3);
 return 0;
 
}

int recursive(int x, int n){
 if(n==0){
  return 1;
 }else{
  return x*recursive(x, n-1);
 }
}

所有的遞迴和Iterative都可以互換,跑出同樣的結果,把上列程式用Iterative來寫變成:

#include <iostream>
using namespace std;

int recursive(int, int);

int main() {
 cout << recursive(2, 3);
 return 0;

}

int recursive(int x, int n) {
 int answer=1;
 if (n==0) {
  return answer;
 } else {
  for (int i=0; i<n; i++) {
   answer *=x;
  }
 }
 return answer;
}

但遞迴較佔記憶體空間.

divide and conquer with recursive

遞迴常被使用在分割-處理的使用上,很多二分(Binary)相關的演算法都是用recursive實作