Info 2, Tizenharmadik heti előadás: rekurzió

Utolsó módosítás: 2009. május 7.

Vissza az Info 2 tárgy főoldalára.

Számjegyek

r = 3
n = Integer(readline())
jegy = []
(0 ... n).each {|k|
        jegy[k] = 0
}
stop = false
while !stop
        jegy.each {|j| 
                print j, " "
        }
        print "\n"
        k = n - 1
        while 0 <= k && r - 1 <= jegy[k]
                jegy[k] = 0
                k -= 1
        end
        if 0 <= k
                jegy[k] += 1
        else
                stop = true
        end
end

Például ha ezt lefuttatjuk és bemenetnek a 3-at adjuk, akkor kiírja az összes háromjegyű hármas számrendszerbeli számot:

0 0 0 
0 0 1 
0 0 2 
0 1 0 
0 1 1 
0 1 2 
0 2 0 
0 2 1 
0 2 2 
1 0 0 
1 0 1 
1 0 2 
1 1 0 
1 1 1 
1 1 2 
1 2 0 
1 2 1 
1 2 2 
2 0 0 
2 0 1 
2 0 2 
2 1 0 
2 1 1 
2 1 2 
2 2 0 
2 2 1 
2 2 2 

Mármost ha csak a háromjegyű számokra lennénk kíváncsiak, akkor egyszerűen használhatnánk három egymásba ágyazott ciklust (pl. sokan így oldották meg a háromszögszámos feladatot). Letöltés: hdg1.rb.

r = 3
(0 ... r).each {|j0|
        (0 ... r).each {|j1|
                (0 ... r).each {|j2|
                        print j0, " ", j1, " ", j2, "\n";
                }
        }
}

Mit csináljunk azonban, ha nem három, hanem n jegyű számokat keresünk? Nem rakhatunk egymásba n darab ciklust. Vagy mégis?

Sok ilyen esetben jó megoldás lehet a rekurzió, ami azt jelenti, hogy egy függvény önmagát hívja meg (közvetlenül vagy másik függvényen keresztül). Természetesen egy rekurziónak valahogy véget is kell érnie, így általában egy rekurzív függvény csak egy feltételes kifejezésben vagy ciklusban hívja meg önmagát.

Ha a függvény törzsében lokális változókat deklarálunk, akkor a függvény minden hívásakor külön létrejön egy-egy példány ezekből a változókból, és ezekre csak a függvény törzsében az aktuális hívásnál lehet hivatkozni. A ruby-ban lokális változót háromféleképp lehet deklarálni: függvény paramétereként (lent az m), értékadás bal oldalán, vagy blokk paramétereként (lent a j). A ruby-ban a lokális változók kisbetűvel (vagy aláhúzással) kezdődnek, a globális változók dollárjellel.

Letöltés: hdg2.rb

$n = Integer(readline())
$r = 3
$jegy = []
def szamol(m)
        if $n <= m
                $jegy.each {|j|
                        print j, " "
                }
                print "\n"
        else
                (0 ... $r).each {|j|
                        $jegy[m] = j
                        szamol(1 + m)
                }
        end
end
szamol(0)

A fenti tulajdonképpen kölcsönös (közvetett) rekurzió, mert a szamol függvény nem közvetlenül hívja magát, hanem az each függvényen, majd a blokkon keresztül. Ez nem lényegi kérdés, a fentit a következőképpen is írhatnánk. Letöltés: hdg3.rb

$n = Integer(readline())
$r = 3
$jegy = []
def szamol(m)
        if $n <= m
                k = 0
                while k < $n
                        print $jegy[k], " "
                        k += 1
                end
                print "\n"
        else
                j = 0
                while j < $r
                        $jegy[m] = j
                        szamol(1 + m)
                        j += 1
                end
        end
end
szamol(0)

A ruby hibaüzenetei

Rakjunk egy kis hibát a fenti programba: hdg4.rb

$n = Integer(readline())
$r = 3
$jegy = []
def szamol(m)
        if $n <= m
                $jegy.each {|j|
                        rpint j, " "
                }
                print "\n"
        else
                (0 ... $r).each {|j|
                        $jegy[m] = j
                        szamol(1 + m)
                }
        end
end
szamol(0)

Ha leftuttatjuk, és bemenetnek 5-öt adunk, a következő hibaüzenetet kapjuk:

../code/hdg4.rb:7:in `szamol': undefined method `rpint' for main:Object (NoMethodError)
	from ../code/hdg4.rb:6:in `each'
	from ../code/hdg4.rb:6:in `szamol'
	from ../code/hdg4.rb:13:in `szamol'
	from ../code/hdg4.rb:11:in `each'
	from ../code/hdg4.rb:11:in `szamol'
	from ../code/hdg4.rb:13:in `szamol'
	from ../code/hdg4.rb:11:in `each'
	from ../code/hdg4.rb:11:in `szamol'
	 ... 6 levels...
	from ../code/hdg4.rb:13:in `szamol'
	from ../code/hdg4.rb:11:in `each'
	from ../code/hdg4.rb:11:in `szamol'
	from ../code/hdg4.rb:17