<script language="javascript">
var hanoi = function (disc, src, aux, dst){
if (disc > 0) {
hanoi(disc-1, src, dst, aux);
document.write('Move disc ' + disc +' from ' + src + ' to ' + dst+'<br>');
hanoi(disc-1, aux, src, dst);
}
}
hanoi(3, 'Src', 'Aux', 'Dst');
</SCRIPT>
結果輸出:
Move disc 1 from Src to Dst
Move disc 2 from Src to Aux
Move disc 1 from Dst to Aux
Move disc 3 from Src to Dst
Move disc 1 from Aux to Src
Move disc 2 from Aux to Dst
Move disc 1 from Src to Dst
請問各位先進,可以幫我解釋上述的javascript遞歸程式嗎(從頭至尾的運作),本人實在不解,謝謝?
你都把解法過程印出來了...你可以自己追蹤函數執行的過程阿,例如用另一個document.write在函數一開始的時候把傳進來的參數印出來並且標示是剛進入函數,同時在函數結尾的地方做一次並且標示是離開函數前,你就會比較清楚執行過程了。
這位先進,我有試過這個方法,但不解的是disc明明呼叫時都是減1的狀態,可是為何if(disc > 0)最後應該會結束,但還是會列出Move disc 1 from Src to Dst,而且會跳過我之前要輸出值的程式碼,不知我這樣說明先進清不清楚。
你的問題是在下方執行結果的第3,8,14,19列
以第3列來看
以disc=1執行呼叫後進入函數內部
第4列disc-1=0
第6列disc-1=0
而第5列就是原來的disc
也就是 move 1 過去
<pre class="c" name="code">
<HTML>
<script language="javascript">
var cnt=0;
var hanoi = function (disc, src, aux, dst){
document.write(++cnt + '.' + 'calling hanoi disc:' + disc + ' from:' + src + ' to:' + dst + ' </br>');
if (disc > 0) {
hanoi(disc-1, src, dst, aux);
document.write(++cnt + '.' + '-----Move disc ' + disc +' from ' + src + ' to ' + dst+'<br>');
hanoi(disc-1, aux, src, dst);
}
}
hanoi(3, 'Src', 'Aux', 'Dst');
</SCRIPT>
</HTML>
<pre class="c" name="code">
執行結果
1.calling hanoi disc:3 from:Src to:Dst
2.calling hanoi disc:2 from:Src to:Aux
3.calling hanoi disc:1 from:Src to:Dst
4.calling hanoi disc:0 from:Src to:Aux
5.-----Move disc 1 from Src to Dst
6.calling hanoi disc:0 from:Aux to:Dst
7.-----Move disc 2 from Src to Aux
8.calling hanoi disc:1 from:Dst to:Aux
9.calling hanoi disc:0 from:Dst to:Src
10.-----Move disc 1 from Dst to Aux
11.calling hanoi disc:0 from:Src to:Aux
12.-----Move disc 3 from Src to Dst
13.calling hanoi disc:2 from:Aux to:Dst
14.calling hanoi disc:1 from:Aux to:Src
15.calling hanoi disc:0 from:Aux to:Dst
16.-----Move disc 1 from Aux to Src
17.calling hanoi disc:0 from:Dst to:Src
18.-----Move disc 2 from Aux to Dst
19.calling hanoi disc:1 from:Src to:Dst
20.calling hanoi disc:0 from:Src to:Aux
21.-----Move disc 1 from Src to Dst
22.calling hanoi disc:0 from:Aux to:Dst
另一種觀察,遞迴深度:
<pre class="c" name="code">
<script language="javascript">
var depth = 0;
var hanoi = function (disc, src, aux, dst){
depth++;
if (disc > 0) {
hanoi(disc-1, src, dst, aux);
document.write('depth:'+depth+', Move disc ' + disc +' from ' + src + ' to ' + dst+'<br>');
hanoi(disc-1, aux, src, dst);
}
depth--;
}
hanoi(3, 'Src', 'Aux', 'Dst');
</script>
大師一出手,就知有沒有。
謝謝先進的指教,我已看的懂1-6行輸出結果,但7.-----Move disc 2 from Src to Aux這個輸出結果的disc 2從哪裡來,本人真的太愚笨了,請先進可否再次解除疑惑。
其實你沒有看懂...
我換個方式解釋看看
基本上
這個函數f(n)是由三個部份組成
n>0時,f(n)是f(n-1)及一列'Move..'及f(n-1)
n=0時,f(n)什麼事都不做
以下我列出各階層三個部份的列號
提供您參考看看
hanoi(3)=(2-11)(12)(13-22)
hanoi(2)=(3-6)(7)(8-11)
hanoi(1)=(4-6)
hanoi(1)=(9-11)
hanoi(2)=(14-17)(18)(19-22)
hanoi(1)=(15-17)
hanoi(1)=(20-22)
您可以先試著把簡單的FOR迴圈改成用遞迴寫看看, 如果這是您看的第一個遞迴程式, 那是有一點難.