CH 07 Programming with Recursion

75565 ワード

python データ構造 C テキストリンク

Recursive Call

Recursion

呼び出しのボディは呼び出しのオブジェクトと同じ

である.

ダイレクトリカバリ:関数fダイレクトコール関数f

Indirect Recursion:関数fで実行する関数gにおいて関数f

を間接的に呼び出す.

Recursive CallとLoop互換

Recursive Callは反復ソリューションよりも効率が低い

Recursive Callを使用すると、コードがわかりやすくなります

Some Definition

Base Case:Recursion使用時に

を終了

General Case:Recursionを実行すると

になります.

Recursive Algorithm: Base Case + General Case

で処理するインスタンスは、基本インスタンス

を指す必要があります.
戻り値

は、

とは反対の方向に戻ります.

Example

Factorial

Base Case: 1!

General Case: n! = n * (n-1)!

Factorial Function

int Factorial(int num) {
	if (num == 1) 
   		return 1;
 	else
  		return Factorial(num - 1);
 }

Combination

Base Case

Combination(n, 1) = n

Combination(n, n) = 1

General Case: Combination (c, k) = Combination(n-1, k) + Combination(n-1, k-1)

Combination Function

int Combination(int n, int k) {
	if (k == 1)
		return n;
	else if (k == n)
 		return 1;
 	else
  		return Combination(n-1, k) + Combination(k-1, n-1);
 }

ValueInList

関数

配列に値があるかどうかを検索

Base Case:値が見つからない場合は

General Case: n! = value値が見つからない場合は、startIndexの後に

のみ検索されます.

ValueInList Function

bool ValueInList(ListType list, int value, int startIndex) {
	if(list->info[startIndex] == value)
		return true;
	else if (startIndex == list.length - 1)
 		return false;
	else
 		return ValueInList(list, startIndex - 1);
 }

RevPrint

listの終了要素から出力を開始する関数

Base Case: listPtr == NULL

General Case: listPtr != NULL

Factorial Function

int RevPrint(NodeType* listPtr) {
	if(listPrt != NULL):
		RevPrint(listPtr->next);
		std::cout << listPtr->info << std::endl;
 }

BinarySearch

Base Case:start>終了またはアイテムが見つかった場合は

General Case:start

BinarySearch Function

bool BinarySearch(int info[], int item, int start, int end) {
	int mid = (start + end) / 2;
	if (start > end)
		return false;
	else if (info[mid] == item)
		return true;
	else {
		if (info[mid] > item) 
			BinarySearch(info, item, start, mid - 1);
		else 
			BinarySearch(info, item, mid + 1, end);
	}
}

Runtime Stack Activation Record

Function Call

プログラムを実行すると、上からコード

を行毎に実行する.

void h() {
	f();
 
}

void g() {
	f();
}

f()が戻った後、機械はh()の後に並ぶべきかg()の後に並ぶべきか分からない
したがって、

は、関数呼び出しを行う際に、どこに戻るべきか、戻りアドレスのように

を送信する.

Stack Activation Frame

関数呼び出しおよび戻りスタック管理

f呼後呼gは

である.
call fcall gg()f()f()

ラックに格納各関数のサイズは、ローカル変数の数

に依存する.

関数の動作が完了すると、1つの動作点を下げる必要があるが、関数ごとに定義されたサイズが異なるため、

を格納するためにどれだけの情報を下げる必要があるかを示す.

関数call=アクティブレコードインスタンスをスタック

にプッシュ

Activation Record Instance

実際の関数を呼び出すとスタックのitemインスタンス

にプッシュされる

構成

Return Address:関数を呼び出すline

Parameter

Local variable

Return value
functionActivation Record InastanceReturn valuef()Local variableParameterReturn Addreaa

Recorseveを実行するたびに関数が呼び出されるため、

Activation Recordインスタンスが作成されます.

Recursive Callの効率低下の原因は

である.

Direction of Recursion

Tail Recursion

関数の最後の再帰構造

サイクル

への変換が容易である.

Example: ValueInList function

bool ValueInList(ListType list, int value, int startIndex) {
	if(list->info[startIndex] == value)
		return true;
	else if (startIndex == list.length - 1)
 		return false;
	else
 		return ValueInList(list, startIndex - 1);
 }

Invert iteration version

bool ValueInList(ListType list, int value, int startIndex) {
	bool found = false;
	while (!found) {
		if (list->info[startIndex] == value)
			found = true;
		else
			startIndex++;
		return found;
	}
}

Reverse Recursion

行動の前に

回復が実行される場合、

反復に変換するには、スタック

が必要です.

Example: RevPrint function

int RevPrint(NodeType* listPtr) {
	if(listPrt != NULL):
		RevPrint(listPtr->next);
		std::cout << listPtr->info << std::endl;
 }

Invert Iteratoin version

int RevPrint(NodeType* listPtr) {
	StackType<ItemType> stack;
	listPtr = listData;
	while (listPtr != NULL) {
		stack.push(listPtr->info);
		listPtr = listPtr->next;
	}
	while (!stack.IsEmpty()) {
		std::cout << stack.top() << std::endl;
		stack.pop();
	}
}

Additional Algorithm

Quick Sort Algorithm

ブロック大問題を解決

SplitValに対して、小項目は前に移動し、大項目は後ろに移動する

Recursive QuickSort Function

int Split(int values[], int first, int last) {
	int pivot, temp;
	int low, high;

	low = first + 1;
	high = last;
	pivot = values[first];

	while (low < high) {
		while (low <= last && values[low] < pivot)
			low++;
		while (high >= first && values[high] > pivot)
			high--;
		if (low < high) {
			temp = values[low];
			values[low] = values[high];
			values[high] = temp;
		}
	}
	temp = values[first];
	values[first] = values[high];
	values[high] = temp;
	return high;
}

void QuickSort(int values[], int first, int last) {
	if (first < last) {
		int splitPoint = Split(values, first, last);
		QuickSort(values, first, splitPoint - 1);
		QuickSord(values, splitPoint + 1, last);
	}
}

Sorted List InserItem

Base Case

new itemが最初のitemである場合

new itemが一番小さくて、一番前の時は

を入れる場所が見つかった場合、

General Case: Insert(locaion->next, item)

InsertItem function

template<class ItemType>
void Insert(NodeType<ItemType>* location, ItemType item) {
	if ((location == NULL) || (item < location->info) {
		NodeType<ItemType>* temp = location;
		location = new NodeType<ItemType>;
		location->info = item;
		location->next = temp;
	}
	else
		Insert(locaion->next, item);
}

template<class ItemType>
void SortedType::InsertItem(ItemType item) {
	Insert(listData, item);
}

Sorted List DeleteItem

Base Case:削除する子供を探している場合、

General Case: Delete(location->next, item)

DeleteItem function

template<class ItemType>
void Delete(NodeType<ItemType>* location, ItemType item) {
	if (location->info == item) {
		NodeType<ItemType>* temp = locaion;
		location = location->next;
		delete temp;
	}
	else
		Delete(location->next, item);
}

template<class ItemType>
void SortedType::DeleteItem(ItemType item) {
	Delete(listData, item);
}

LAB

Fibonacci

フィボナッチ数列は、次の整数の連続です.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 …

この整数の連続性は、これから始まる2つの数の和

である.

Base Case: Fib(0) = 0

General Case: Fib(N) = Fib(N-2)+Fib(N-1)

Recursive version

int Fibonacci(int n) {
	if (n == 0 || n == 1)
		return n;
	else
		return Fibonacci(n - 2) + Fibonacci(n - 1);
}

Iteration version

int Fibonacci(int n) {
	if (n == 0 || n == 1)
		return n;
	int result;
	int num1 = 0;
	int num2 = 1;
	for (int i = 1;  i < n; i++) {
		result = num1 + num2;
		num1 = num2;
		num2 = result;
	}
	return result;
}

SqurRoot

の下には、与えられた近似答え(近似値)と指定された許容値(tol)内の数値の平方根近似値を計算する関数

があります.

number:平方根の数

を求めます

近似:平方根の近似値

tol:平方根の近似値範囲

Recursion version

#include <iostream>
#include <cmath>
using namespace std;

float SqrRoot(float number, float approx, float tol) {
	if (fabs(approx * approx - number) <= tol)
		return approx;
	else
		return SqrRoot(number, (approx * approx + number) / (2 * approx), tol);
}

Iteration version

#include <iostream>
#include <cmath>
using namespace std;

float SqrRoot(float number, float approx, float tol) {
	while (fabs(approx * approx - number) > tol) {
		approx = (approx * approx + number) / (2 * approx);
	}
	return approx;
}

NumPath

2 Dメッシュ(1、1)から(N、N)までの移動可能パス数

行N*Nを算出する

単位方向、右に1マスしか移動できません

(r,c)で1つのセルのみを移動する場合、

は右シフトと上シフトの2つの場合にのみ存在する.
従って、(r,c)~(n,n)への経路数(r+1,c)~(n,n)への(r,c++1)~(n,n)の合計はである.
現在位置のrまたはcがnである場合(

)、経路の
数量は

(1,1)~(n,n)への移動可能経路を計算するNumPaths関数

を実現する.

#include <iostream>
using namespace std;

int NumPaths(int row, int col, int n) {
	if ((row == n) || (col == n))
		return 1;
	else
		return NumPaths(row + 1, col, n) + NumPaths(row, col + 1, n);
}

Aにおいて実施する方法は、同じセルからn、nへの経路を再計算することであるので、2次元マトリクスを用いる

の再計算を回避するためにアルゴリズムを修正する.

#include <iostream>
using namespace std;

int NumPaths(int row, int col, int n) {
	if ((row == n) || (col == n))
		return 1;
	else
		return NumPaths(row + 1, col, n) + NumPaths(row, col + 1, n);
}

#define MAXROWS 50
#define MAXCOLS 50

int mat[MAXROWS][MAXCOLS];
int NumPathsMatrix(int row, int col, int n) {
	if (mat[row][col] == -1) {
		if (row == col) {
			mat[row][col] = 0;
			return 0;
		}
		else if ((row == n) || (col == n)) {
			mat[row][col] = 1;
			return 1;
		}
		else {
			mat[row][col] = NumPaths(row + 1, col, n) + NumPaths(row, col + 1, n);
			return mat[row][col];
		}
	}
}

MinLoc

次の2つの再帰ルーチンのポインタ

は、重複しない順序付けされていない数字からなる単一の接続リストを指す

リストの各ノードはinfo(数値)とnext(次のノードへのポインタ)のメンバーからなる:

はメンバー関数MINLOCを実施し、最小値

のノード

を返す.

#include <iostream>
#include <new>
using namespace std;

template<class ItemType>
NodeType<ItemType>* UnsortedType<ItemType>::MinLoc(NodeType<ItemType>* location) {
	if (location == NULL)
		return NULL;
	else if (location->next == NULL)
		return location;
	else {
		NodeType<ItemType>* minPtr = MinLoc(location->next);
		if (location->info < minPtr->info)
			minPtr = location;
		return minPtr;
	}
}

要素の並べ替えを実現したメンバー関数Sort

#include <iostream>
#include <new>
using namespace std;

template<class ItemType>
NodeType<ItemType>* UnsortedType<ItemType>::Sort(NodeType<ItemType>* location) {
	NodeType<ItemType>* min;
	ItemType temp;
	if (location != NULL) {
		min = MinLoc(location, location);
		temp = min->info;
		min->info = location->info;
		location->info = temp;
		Sort(location->next)
	}
}

PP

Binary Search

出力例
13 is not in the list
20 is in the list

BinarySearch

def binary_search(info, item, fromLocation, toLocation):
    if fromLocation > toLocation:
        return False
    else:
        midPoint = int((fromLocation + toLocation) / 2)
        if item < info[midPoint]:
            return binary_search(info, item, fromLocation, midPoint-1)
        elif item == info[midPoint]:
            return True
        else:
            return binary_search(info, item, midPoint+1, toLocation)

test

from BinSearch import *

if __name__ == '__main__':
    arr = [1,3, 5, 6, 7, 10, 17, 20]
    item = 13
    if  binary_search(arr, item, 0, len(arr) - 1) == True:
        print(f'{item} is in the list.')
    else:
         print(f'{item} is not in the list.')
    item = 20
    if  binary_search(arr, item, 0, len(arr) - 1) == True:
        print(f'{item} is in the list.')
    else:
         print(f'{item} is not in the list.')

Combination

出力例
C(10, 3): 120
C(5, 1): 5
C(45, 6): 8145060

Combination

def combinations(group, members):
    if(members == 1):
        return group
    elif (members == group):
        return 1
    else:
        return(combinations(group-1, members-1) + combinations(group-1, members))

test

from ComBin import *

if __name__ == '__main__':
    print(f"C(10,3) : {combinations(10, 3)}")
    print(f"C(5,1) : {combinations(5, 1)}")
    print(f"C(45,6) : {combinations(45, 6)}")

Factorial

出力例
7! : 120
17! : 355687428096000
50! : 30414093201713378043612608166064768844377641568960512000000000000

Factorial

def factorial(number):
    if (number == 1):
        return 1
    else:
        return number*factorial(number-1)

test

from Factorial import *

if __name__ == '__main__':
    print(f'7! : {factorial(5)}')
    print(f'17! : {factorial(17)}')
    print(f'50! : {factorial(50)}')

QuickSort

出力例
Before
[9, 8, 7, 6, 5, 4, 3, 2, 1]
After
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Before
[1, 8, 5, 7, 3, 2, 6, 4, 9]
After
[1, 2, 3, 4, 5, 6, 7, 8, 9]

QuickSort

def split(values, first, last):
    splitvalue = values[first]
    saveFirst = first
    onCorrectside = True
    first += 1
    while(first <= last):
        while(onCorrectside):
            if(values[first]>splitvalue):
                onCorrectside = False
            else:
                first += 1
                onCorrectside = (first <= last)
            
        onCorrectside = (first <= last)

        while(onCorrectside):
            if(values[last] < splitvalue):
                onCorrectside = False
            else:
                last -= 1
                onCorrectside = (first <= last)

        if(first <= last):
            values[first], values[last] = values[last], values[first]
            first += 1
            last -= 1
    
    splitPoint = last
    values[saveFirst], values[splitPoint] = values[splitPoint], values[saveFirst]
    return splitPoint
    
def quick_sort(values, first, last):
    if(first < last):
        splitPoint = split(values, first, last)

        quick_sort(values, first,splitPoint-1 )
        quick_sort(values, splitPoint+1, last)
    return values

test

from QuickSort1 import *

if __name__ == '__main__':
    arr01 = [9, 8, 7, 6, 5, 4, 3, 2, 1]
    arr02 = [1, 8, 5, 7, 3, 2, 6, 4, 9]
    print("Before")
    print(arr01)
    print("After")
    print(quick_sort(arr01, 0, len(arr01) - 1))
    print("\nBefore")
    print(arr02)
    print("After")
    print(quick_sort(arr02, 0, len(arr02) - 1))

Reference

この問題について(CH 07 Programming with Recursion), 我々は、より多くの情報をここで見つけました https://velog.io/@morion002/CH-07-Programming-with-Recursion

テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。

Collection and Share based on the CC Protocol

【FFmpegのAVOption】エンコーディングオプション設定

アルゴリズム→ソートの選択