Ostatnio próbuję zrozumieć, jak działa algorytm rekurencyjny w łamigłówce Wieże Hanoi. (Z czasem widzę pewien postęp).
Przeczytałem kilka wątków na Stack Overflow oraz kilka innych stron, w tym Wikipedię polską i angielską. (Z napotkanych algorytmów poza rekurencyjnym oraz z dowodów matematycznych niewiele zrozumiałem, przyznaję). Obejrzałem dwa wideo (uznałem, że oglądanie więcej będzie stratą czasu z uwagi na nikłe szanse odmienności materiału). Przejrzałem wszystkie kody na Wikipedii polskiej/angielskiej oraz kilka na Rosetta Code. (Na Rosetta Code jest, jak wynika ze spisu treści, 150 implementacji. Do tego nazwy wielu języków, zdaje się, pierwszy raz widziałem. Przeglądanie więc wszystkich implementacji tam uznałem za stratę czasu).
Ponieważ samo czytanie/słuchanie/oglądanie nie przyczyniło się do całkowitego zrozumienia (choć, jak napisałem, widzę postęp), zabrałem się za implementowanie samemu. Napisałem trzy implementacje w JavaScripcie (w tym jedną działającą zgodnie z opisami). (Liczę, że obecnie mam dwie, bo drugą upodobniłem do pierwszej). Przy czym: chyba żadna implementacja, jaką widziałem, nic nie przenosi faktycznie (wypisuje jedynie); mnie natomiast wydaje się, że najłatwiej będzie mi to zrozumieć, gdy program będzie faktycznie coś przenosił. Tak więc wszystkie moje implementacje przenoszą liczby.
Nadal jednak mam wrażenie, że nie do końca wszystko rozumiem.
Do tej pory udało mi się wyróżnić dwa kluczowe aspekty zrozumienia: jak działa sam algorytm oraz jak działa sama rekurencja (w sensie wywołań programu). Algorytm wydaje mi się oczywisty, a złożony zarazem. Nie wiem więc, czy go rozumiem, czy nie. Przez większość chwil mam wrażenie, że go rozumiem. Rekurencja wydaje mi się prosta, niemniej nieoczywista. Przez większość chwil mam wrażenie, że coś mi umyka.
Pytanie więc moje: pomoże ktoś zrozumieć?
Nie wiem, czy łatwiej będzie komuś wytłumaczyć mi to w teorii czy w praktyce, dlatego w razie czego załączam obecne dwie własne implementacje: działającą oraz niedziałającą. Docelowo chciałbym zarówno zrozumieć algorytm oraz rekurencję, jak i uczynić niedziałającą implementację działającą. Co do implementacji niedziałającej, stawiam jej dwa wymagania: (1) niekorzystanie z zewnętrznego stanu (czyli przeciwnie do implementacji działającej); (2) korzystanie z rekurencji ogonowej (także przeciwnie do implementacji działającej). (Myślę, że z punktem nr 2 nie będę mieć problemu. Z punktem nr 1 nie mogę sobie na razie poradzić. Mam nadzieję, że albo zrozumienie samego algorytmu, albo samej rekurencji, albo ostatecznie obu naraz przyczyni się do znalezienia przeze mnie rozwiązania).
Implementacja działająca:
// JavaScript
exports.toh3
= (n, stk, tmp, res) => {
console.debug(
`${stk.name}: [${stk.value}], `
+ `${tmp.name}: [${tmp.value}], `
+ `${res.name}: [${res.value}]`
);
if (n > 0) {
// The purpose of this invokation seems to be to tell from which peg
// to move to which WHEN UNWINDING THE STACK
exports.toh3(n - 1, stk, res, tmp);
console.debug(`Moving ${n} from ${stk.name} to ${res.name}`);
res.value.unshift(
stk.value.shift()
);
exports.toh3(n - 1, tmp, stk, res);
}
};
// Test
const globalStateToh3 = [
new Peg("stk", [1, 2, 3]),
new Peg("tmp", []),
new Peg("res", [])
];
exports.toh3(3, globalStateToh3[0], globalStateToh3[1], globalStateToh3[2]);
console.debug();
console.debug("stk === ", globalStateToh3[0]);
console.debug("tmp === ", globalStateToh3[1]);
console.debug("res === ", globalStateToh3[2]);
Implementacja NIEdziałająca:
// JavaScript
const Peg
= class {
/**
* @param {string} name
* @param {number[]} value
*/
constructor(name, value) {
this.name = name;
this.value = value;
}
};
const State
= class {
/**
* @param {Peg} stk
* @param {Peg} tmp
* @param {Peg} res
*/
constructor(stk, tmp, res) {
this.stk = stk;
this.tmp = tmp;
this.res = res;
}
};
exports.toh2
= (n, state) => {
console.debug(
`${state.stk.name}: [${state.stk.value}], `
+ `${state.tmp.name}: [${state.tmp.value}], `
+ `${state.res.name}: [${state.res.value}]`
);
if (n === 1) {
console.debug(
`Moving ${n} from ${state.stk.name} to ${state.res.name}`
);
return new State(
new Peg("stk", state.stk.value.slice(1)),
state.tmp,
new Peg("res", [state.stk.value[0]].concat(state.res.value))
);
} else {
let newState
= exports.toh2(
n - 1, new State(state.stk, state.res, state.tmp)
);
newState = exports.toh2(
1, new State(newState.stk, newState.tmp, newState.res)
);
newState = exports.toh2(
n - 1, new State(newState.tmp, newState.stk, newState.res)
);
return newState;
}
};
// Test
const resultSt
= exports.toh2(
3,
new State(
new Peg("stk", [1, 2, 3]),
new Peg("tmp", []),
new Peg("res", [])
)
);
console.debug();
console.debug("stk === ", resultSt.stk);
console.debug("tmp === ", resultSt.tmp);
console.debug("res === ", resultSt.res);