範例之遞回

• 優點
  遞回使程式碼看起來更加整潔、優雅
  可以用遞回將複雜任務分解成更簡單的子問題
  使用遞回比使用一些巢狀迭代更容易

• 缺點
  遞回邏輯很難偵錯，遞回條件處理不好容易造成程式無法結束，直到達到最大遞回錯誤
  遞回佔用大量記憶體，耗費計算機資源

漢諾塔

#include <stdio.h>

//hanoi函數的意思就是把第一個字元型（x）移到第三個字元型（z）。
void hanoi(int n, char x, char y, char z);

void hanoi(int n, char x, char y, char z)
{
	if (n == 1)
	{
		printf("%c --> %c\n", x, z);
	}
	else
	{
		hanoi(n - 1, x, z, y); // 把x的放到y上，因爲（n-1），所以剩下一個
		printf("%c -- > %c\n", x, z); // x剩下的一個放到z上
		hanoi(n - 1, y, x, z); // 把y的放到z上
        //不需要套用回圈條件，只要是把自身呼叫結束了就相當於多次回圈了
	}
}

int main()
{
	int n;

	printf("scanf_s one number:");

	scanf_s("%d", &n);

	hanoi(n, &#39;X&#39;, &#39;Y&#39;, &#39;Z&#39;);

	return 0;
}

快速排序

#include <stdio.h>

void quick_sort(int array[], int left, int right)
{
	int i = left, j = right;
	int temp;
	int pivot;

	pivot = array[(left + right) / 2];

	while (i <= j)
	{
		// 從左到右找到大於基準點的元素
		while (array[i] < pivot)
		{
			i++;
		}
		// 從左到有找到小於基準點的元素
		while (array[j] > pivot)
		{
			j--;
		}
		// 如果i <= j，則互換
		if (i <= j)
		{
			temp = array[i];
			array[i] = array[j];
			array[j] = temp;
			i++;
			j++;
		}
	}

	if (left < j)
	{
		quick_sort(array, left, j);
	}

	if (i < right)
	{
		quick_sort(array, i, right);
	}
}

int main()
{
	int array[] = {4, 1, 5, 7, 8, 3, 2, 9, 10, 6 };
	int i, length;

	length = sizeof(array) / sizeof(array[0]);
	quick_sort(array, 0, length - 1);

	return 0;
}

斐波那契數列

法1

#include <stdio.h>
#include <string.h>
#define N 20

int f[N + 1];

int fib(int n)

{
    if(f[n])
        return f[n];
    else if(n == 1 || n == 2)
        return f[n] = 1;
    else {
        if(f[n - 2] == 0) f[n - 2] = fib(n - 2);
        if(f[n - 1] == 0) f[n - 1] = fib(n - 1);
        return f[n] = f[n - 2] + f[n - 1];
    }
}

int main(void)
{
    memset(f, 0, sizeof(f));
    int n, a;
    scanf("%d", &n);
    while(n--) {
        scanf("%d", &a);
        printf("%d\n", fib(a));
    }
    return 0;
}

法2

#include <stdio.h>

int fib(int n)
{
    return(n == 1 || n == 2) ? 1 : fib(n-2) + fib(n-1);
}

int main()
{

    int n, a;
    scanf("%d", &n);
    while(n--){
    scanf("%d", &a);
    
    printf("%d\n", fib(a));
}
return 0;
}

模擬實現 樹形結構的遍歷

import os #引入檔案操作模組
def findFile(file_Path):
    listRs = os.listdir(file_Path) # 得到該路徑下所有的資料夾
    for eachitem in listRs:
        full_path = os.path.join(file_Path, eachitem) # 獲取完整的檔案路徑
        if os.path.isdir(full_path): # 判斷是否是資料夾
            findFile(full_path) # 如果是一個資料夾 再次去遞回
            pass
        else:
            print(eachitem)
            pass
        pass
    else:
        return
    pass

# 呼叫搜尋資料夾物件
findFile('D:\\Study\\computer\\Python演示文件')