【ソフト/セルフテスト】アルゴリズムの実用テクニック——再帰VS反復

1435 ワード

反復と再帰は、アルゴリズムの中でよく使われていますね.アルゴリズムの中で欠かせない実用的なテクニックです.調べてみましょう.
再帰:プログラム呼び出し自体のプログラミングテクニックを再帰(recursion)と呼ぶ.
反復:反復は、通常、必要なターゲットまたは結果に近づくための反復フィードバックプロセスのアクティビティです.プロシージャの各ペアの繰り返しを反復と呼び、各反復の結果は次の反復の初期値として使用されます.
【再帰VS反復】
再帰と反復はいずれもループの一種である.
再帰は、繰り返し呼び出し関数自体がループを実現することである.反復は、関数内のセグメントコード実装ループです.
再帰ループでは,終了条件が満たされた場合にレイヤ毎に戻って終了する.反復はカウンタを使用してループを終了します.多くの場合、複数のサイクルを混合して採用されています.
例:再帰関数はnを求めます!
#include<stdio.h>
long f(int n)
{
    if(n==0)  return 1;
    else  return n*f(n-1);
}
main()
{
    int m,n=3;
    m=f(n);
    printf("%d!=%d
",n,m); }

f(n)は再帰関数であり,その関数体にそれ自体が用いられる.
【反復VS通常ループ】
反復ループコードで演算に関与する変数は、結果を保存する変数であり、現在保存されている結果は、次のループ計算の初期値として使用されます.
下のコードは反復です.
for(i=1;i<=n;i++)
{
    temp=temp*i;  /temp*=i;         ,    。
    s=s+temp;     /s+=temp;
}

tempもsも演算に参加し,演算結果も保存し,次のループは演算に参加し続ける.
【一時変数の借用】
1、配列中に存在する2つの位置を交換する
例:1次元配列逆置きアルゴリズムの1つから.
for(i=0;i<n/2-1;i++)
{
    temp=a[i];
    a[i]=a[n-1-i];
    a[n-1-i]=temp;
}

2、単一チェーンテーブル挿入操作
例:単一チェーンテーブルからノードアルゴリズムを挿入します.
p-data=x;
p->next=head->next;
head->next=p;

アルゴリズムの勉強が続き、まとめがどんどん新しくなっていくので楽しみにしていてください.