c#で再帰関数を使った順列の求め方

[チンパンジーのマーチ]

Unityでゲームを製作中なのですが、AIなどのルート検索にバックトラックと言うものがあると知り、再帰関数を
知って実践しようと、まずは簡単な順列をと思ったのですが、試行錯誤してもうまく行かずに悩んでおります。
やりたいことは、ABCDという文字列の順列を作ることで、手法としてはList ABCDの中に並べ替える文字を入れ、resultの中に
結果を入れていく。樹形図の選択肢のように、選択できる文字列は減っていくために消去していく。
resultの文字数が4文字になったら再帰をやめ、結果を出力
症状としては、4回再帰したあと、樹形図の末端から一つ戻って
for(int i =0; i <ABCD.Count; i++)
この部分の i の値が1となってとなるはずが、ループせずにresultを4回出力して終わってしまうという状況です。
また、出力結果はa b c dが4回表示されるだけです。

コード:

using UnityEngine;
using System.Collections;
using System.Linq;
using System.Collections.Generic;

public class test : MonoBehaviour {

	// Use this for initialization
	void Start () {

        List<string> result = new List<string>();
        List<string> ABCD = new List<string>() { "a","b","c","d"};

        permutation(ABCD, result);
	
	}

    void permutation(List<string> ABCD,List<string> result)
    {
        for(int i =0; i <ABCD.Count; i++)
        {
            result.Add(ABCD[i]);
            ABCD.RemoveAt(i);

            if(result.Count != 4)
            {
                permutation(ABCD, result);
            }
        }

        string[] tmp = result.ToArray();
        Debug.Log(string.Join(",",tmp));

    }
}

[みけCAT]

樹形図の末端から一つ戻って

このときに、使った文字をresultからABCDに戻さないとダメですね。

また、出力結果はa b c dが4回表示されるだけです。

順列が完成していないときにもその時点での順列を出力しているから、重複しているのですね。

[チンパンジーのマーチ]

回答ありがとうございます。
確かに樹形図の枝を一つ戻る際、選択肢も戻さなければいけないため書き戻しが必要でした。
みけCATさんに教えていただいたとおり書いてみたところ、無事やりたいことが出来ました。
しかし、書き戻しの際にちょっと思い通りに行かなくて試行錯誤して気が付き、出力部分にも書き換えコードを追加したのですが。

関数に変数を渡した場合、関数内で値を変えても変化しませんが、文字列やリストや配列の場合、
書き換えられてしまうのは普通のことなのでしょうか？
例えば以下の場合、aは書き換えられずに10が表示され、b[0]は15に書き換えられて表示されるということです。

コード:

 static void Main()
    {
        int a = 10;
        Test(a);
        Console.WriteLine(a);

        int[] b = new int[] { 10, 11, 12 };
        Tester(b);
        Console.WriteLine(b[0]);
    }

    static void Test(int a)
    {
        a = 15;
    }

    static void Tester(int[] b)
    {
        b[0] = 15;
    }

以下は無事に書き換えして順列を作る事に成功したコードです。

コード:

using UnityEngine;
using System.Collections;
using System.Linq;
using System.Collections.Generic;

public class test : MonoBehaviour {

	// Use this for initialization
	void Start () {

        List<string> result = new List<string>();
        List<string> ABCD = new List<string>() { "a","b","c","d"};
        permutation(ABCD, result);
        
	
	}
    void permutation(List<string> ABCD,List<string> result)
    {
        int count = ABCD.Count;

        for(int i =0; i < count; i++)
        {
            result.Add(ABCD[i]);
            ABCD.RemoveAt(i);

            if(count >= 2)
            {
                permutation(ABCD, result);
                ABCD.Insert(i, result[result.Count-1]);
                result.RemoveAt(result.Count-1);
            }

            if (count == 1)
            {
                string[] tmp = result.ToArray();
                Debug.Log(string.Join(",", tmp));
                ABCD.Insert(i, result[result.Count - 1]);
                result.RemoveAt(result.Count - 1);
            }


        }

    }
}

[YuO]

関数に変数を渡した場合、関数内で値を変えても変化しませんが、文字列やリストや配列の場合、
書き換えられてしまうのは普通のことなのでしょうか？

値型にしろ参照型にしろ，refやoutを伴わない限り，メソッド呼び出しにおいて変数の指すオブジェクトは変化しません。
変数の値自体がメソッドにコピーされるためです。

さて，その上でint (System.Int32) は値型です。
この場合，「変数の値」とは「オブジェクトそのもの」になります。
また，メソッド中で引数のオブジェクトのメソッドを呼び出して状態を変更しても，元のオブジェクトの状態は変更されません。

しかし，string (System.String) やList (System.Collections.Generic.List<T>) や配列 (System.Array) は参照型です。
この場合，「変数の値」とは「オブジェクトへの参照」になります。
このため，メソッド中で引数のオブジェクトのメソッドを呼び出して状態を変更した場合，元のオブジェクトの状態は変更されます。

さて，Stringは参照型ですが実装としてimmutableです。
このため，Stringを変更することはできません。

しかし，ListやArrayはmutableな実装になっています。
このため，[]演算子を使うなどしてオブジェクトの状態を変更することができます。

オフトピック

unsafeな話などは無視

[チンパンジーのマーチ]

YuOさん、丁寧な回答ありがとうございました。
ちゃんと理解できたのですっきりしました。