Entrekursivierung

Entrekursivierung bezeichnet in der Informatik das Umwandeln einer rekursiven Funktion in eine iterative Funktion.

Rekursionen sind eine Technik, die häufig in der Informatik eingesetzt werden, um eine Funktion durch sich selbst zu definieren. Dafür löst die rekursive Funktion das gegebene Problem zuerst teilweise oder teilt es in mehrere Teilprobleme auf und ruft sich selbst dann mit diesen neuen Teilproblemen auf. Dies geschieht so lange, bis das Problem vollständig gelöst ist oder die Lösung in triviale Einzelteile zerlegt ist.

Rekursive Lösungen sind oft eleganter und einfacher zu finden sowie einfacher auf ihre Korrektheit zu prüfen (z. B. mittels Mathematischer Induktion) als iterative Funktionen,[1] sind aber aufgrund der vielen Funktionsaufrufe je nach verwendeter Programmiersprache weniger performant,[2] weswegen es sich bei Performance-kritischen Programmteilen oft auszahlt, eine rekursive Funktion zu entrekursivieren. Da Rekursionen und Iterative Funktionen gleich mächtig sind, gibt es für jede Rekursion ein iteratives Äquivalent.[3]

Lineare Rekursion auflösen

Lineare Rekursionen sind Rekursionen, bei denen es pro Rekursionsschritt maximal einen Rekursionsaufruf gibt. Die Berechnung läuft hierbei entlang einer Kette von Aufrufen. Lineare Rekursionen lassen sich sehr leicht auflösen.[4] Als Beispiel hierzu eine rekursive Funktion, die die Fakultät einer Zahl berechnet. 

int fac(int x) {
	if (x = 0) {
		return 1;
	} else {
		return x * fac(x - 1);
	}
}

Das Erste, was hier notwendig ist, ist die getrennten Return-Werte auf einen Return-Wert zu reduzieren: 

int fac(int x) {
	int value;
	if (x = 0) {
		value = 1;
	} else {
		value = x * fac(x - 1);
	}
	return value;
}

Als Letztes wird der Return-Befehl durch einen Akkumulator und die Rekursion durch eine Schleife ersetzt: 

int fac(int x) {
	int accumulator = 1;
	bool running = true;
	while (running) {
		int value;
		if (x = 0) {
			value = 1;
			running = false; //Hier endet die Rekursionskette
					 //im ursprünglichen Algorithmus.
					 //Äquivalent zu return(1);
		} else {
			value = x;
			x = x-1;	 //Hier geht die Rekursionskette weiter.
			running = true;	 //Äquivalent zu return x*fac(x-1);
		}
		accumulator = accumulator * value;
	}
	return accumulator;
}

Diese Funktion lässt sich dann noch optimieren, indem unnötige Zuweisungen ausgelassen werden, die durch die Umwandlung entstanden sind.

Einzelnachweise

  1. ↑ G. Pomberger, H. Dobler: Algorithmen und Datenstrukturen. Abgerufen am 17. Juni 2014.
  2. ↑ Algorithmen und Datenstrukturen 04 (PDF). Technische Fakultät der Universität Erlangen; abgerufen am 17. Juni 2014.
  3. ↑ Algorithmen und Datenstrukturen 06 Entrekursivierung@1@2Vorlage:Toter Link/www.swe.uni-linz.ac.at (Seite nicht mehr abrufbar, festgestellt im April 2018. Suche in Webarchiven)  Info: Der Link wurde automatisch als defekt markiert. Bitte prüfe den Link gemäß Anleitung und entferne dann diesen Hinweis. (PDF). Institut für Wirtschaftsinformatik und Software Engineering der Universität Linz; abgerufen am 17. Juni 2014.
  4. ↑ H. Peter Gumm: Programmieren und Beweisen. (PDF; 189 kB) Abgerufen am 17. Juni 2014.

Read other articles:

Josh O'Connor

Josh O'ConnorO'Connor at the 2015 Odessa International Film FestivalLahir20 Mei 1990 (umur 33)Cheltenham, InggrisAlmamaterBristol Old Vic Theatre SchoolPekerjaanAktorTahun aktif2012–sekarang Josh O'Connor (lahir 20 Mei 1990) adalah aktor asal Britania Raya. Ia paling dikenal karena perannya sebagai Johnny Saxby pada film tahun 2017 God's Own Country, disutradarai oleh Francis Lee, dimana ia memenangkan penghargaan British Independent Film Award for Best Actor.[1] Filmogra...

 

ADiTV

ADiTVPT Arah Dunia TelevisiSleman, Daerah Istimewa YogyakartaIndonesiaSaluranDigital: 29 UHFVirtual: 811 Magelang 806 YogyakartaSloganPencerahan Bagi SemuaPemrogramanAfiliasiTempo TVKepemilikanPemilikPP Muhammadiyah dan Yayasan Budi Mulia DuaRiwayatSiaran perdana18 Juli 2009Bekas nomor kanal44 UHF (analog)Bekas afiliasiCity TV NetworkSpacetoonTV EdukasiBBS TVMakna tanda panggilArah Dunia TelevisiInformasi teknisOtoritas perizinanKementerian Komunikasi dan Informatika Republik IndonesiaPranala...

 

Karolyn Grimes

Karolyn GrimesGrimes di It's a Wonderful Life, 1946Lahir4 Juli 1940 (umur 83)Hollywood, California, A.S.PekerjaanAktrisTahun aktif1945–1954Karya terkenalIt's a Wonderful Life (1946) dan The Bishop's Wife (1947)Suami/istriHal Barnes(m. 19??; div. 19??) Mike Wilkerson ​ ​(m. 1968; meninggal 1993)​Anak4 Karolyn Grimes (lahir 4 Juli 1940) adalah seorang aktris Amerika. Dia terkenal karena perannya sebagai Zuzu Bailey dalam film klasik k...

Kuli

Kuli di Zhenjiang, Tiongkok. Kuli (Belanda: koeliecode: nl is deprecated , Inggris: cooliecode: en is deprecated ) adalah orang yang bekerja dengan mengandalkan kekuatan fisiknya, seperti untuk membongkar muatan kapal atau mengangkut barang dari stasiun, dengan memindahkan barang dari satu tempat ke tempat lain. Istilah lain digunakan untuk menyebut kuli sebagai pekerja kasar.[1] Sekitar tahun 1600-an, istilah tersebut muncul ketika orang Eropa menyebut pekerja asli yang dipekerjakan ...

 

Lot's Wife (crag)

Deserted island in the Philippine Sea Lot's WifeNative name: Sōfu IwaGeographyLocationIzu IslandsCoordinates29°47′39″N 140°20′31″E / 29.79417°N 140.34194°E / 29.79417; 140.34194ArchipelagoIzu IslandsArea0.0037 km2 (0.0014 sq mi)Length84 m (276 ft)Width56 m (184 ft)Highest elevation99 m (325 ft)AdministrationJapanPrefectureTokyoSubprefectureHachijō SubprefectureDemographicsPopulation0 Lot's Wife (孀婦岩,...

 

Chiara d'Assisi

Disambiguazione – Santa Chiara rimanda qui. Se stai cercando la santa del 17 agosto, vedi Chiara da Montefalco. Questa voce o sezione sull'argomento santi italiani non cita le fonti necessarie o quelle presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Santa Chiara d'AssisiSanta Chiara in un affresco di Giotto Fondatrice delle Clarisse  NascitaAssisi, 16 luglio 1194 MorteAss...

Weiler-Simmerberg

Weiler-Simmerberg Balai kota Weiler-Simmerberg Lambang kebesaranLetak Weiler-Simmerberg di Lindau NegaraJermanNegara bagianBayernWilayahSchwabenKreisLindauPemerintahan • MayorKarl-Heinz RudolphLuas • Total31,30 km2 (1,210 sq mi)Ketinggian tertinggi900 m (3,000 ft)Ketinggian terendah630 m (2,070 ft)Populasi (2013-12-31)[1] • Total6.115 • Kepadatan2,0/km2 (5,1/sq mi)Zona waktuWET/WMPET...

 

Pembicaraan Pengguna:AdhiOK

Halo, AdhiOK. Selamat datang di Wikipedia bahasa Indonesia! Memulai Bacalah halaman Pengantar Wikipedia terlebih dahulu. Baca juga informasi tentang berkontribusi di Wikipedia. Lihat pula aturan yang disederhanakan sebelum melanjutkan. Tips Selalu tanda tangani pertanyaan Anda di Warung Kopi atau halaman pembicaraan dengan mengetikkan ~~~~ pada akhir kalimat Anda. Jangan takut! Anda tidak perlu takut salah ketika menyunting atau membuat halaman baru, menambahkan, atau menghapus kalimat. Ada ...

 

Yurihonjō, Akita

Yurihonjō 由利本荘市KotaBalai Kota Yurihonjō BenderaEmblemLokasi Yurihonjō di Prefektur AkitaYurihonjōLokasi di JepangKoordinat: 39°23′09″N 140°02′56″E / 39.38583°N 140.04889°E / 39.38583; 140.04889Koordinat: 39°23′09″N 140°02′56″E / 39.38583°N 140.04889°E / 39.38583; 140.04889Negara JepangWilayahTōhokuPrefektur AkitaPemerintahan • WalikotaTakanobu MinatoLuas • Total1.209,59...

Karlinah Djaja Atmadja Wirahadikusumah

Karlinah Djaja Atmadja Istri Wakil Presiden Indonesia ke-4Masa jabatan11 Maret 1983 – 11 Maret 1988Wakil PresidenUmar WirahadikusumahPendahuluNelly MalikPenggantiRatu Emma Norma Informasi pribadiLahirKarlinah Djaja Atmadja30 Juli 1930 (umur 93)Bandung, Hindia BelandaSuami/istriUmar WirahadikusumahAnak2Alma mater Voorbereidend Hogere Onderwijs (VHO), Bandung Belajar bahasa Prancis di Alliance Francaise. Sempat mengikuti Colombo Plan. Pekerjaan Aktivis Komis pada Kantor Pusa...

 

Salina Cruz

City in the state of Oaxaca, Mexico For the station, see Salina Cruz railway station. Municipality and town in Oaxaca, MexicoSalina CruzMunicipality and town Coat of armsLocation of the municipality in OaxacaSalina CruzLocation in MexicoCoordinates: 16°10′N 95°12′W / 16.167°N 95.200°W / 16.167; -95.200CountryMexicoStateOaxacaArea • Total131.9 km2 (50.9 sq mi) • Town31.7 km2 (12.2 sq mi)Population (2020 ...

 

Cornwall Railway viaducts

This article is about viaducts built by the Cornwall Railway Company (1859 to 1889). For viaducts built by other railway companies in Cornwall, see List of railway bridges and viaducts in the United Kingdom. Map all coordinates using OpenStreetMap Download coordinates as: KML GPX (all coordinates) GPX (primary coordinates) GPX (secondary coordinates) The 70 miles (110 km) of the Cornwall Railway included 42 wooden viaducts, such as Carvedras viaduct in Truro The Cornwall Railway company ...

Kodi Ramakrishna

Kodi RamakrishnaKodi Ramakrishna Nagabharanam Movie Audio Launch, 2017Lahir(1949-07-23)23 Juli 1949Palakollu, Andhra Pradesh, IndiaMeninggal22 Februari 2019(2019-02-22) (umur 69)Hyderabad, IndiaKebangsaanIndiaPekerjaanSutradara, penulis, aktorTahun aktif1982-2019Kota asalHyderabadSitus webwww.kodiramakrishna.in Kodi Ramakrishna (bahasa Telugu: కోడి రామకృష్ణ; 23 Juli 1949 – 22 Februari 2019) adalah seorang sutradara dan penulis film I...

 

Natrium sulfit

Natrium sulfit anhydrous hydrate Nama Nama IUPAC Natrium sulfit Nama lain Hypo clear (photography)E221 Penanda Nomor CAS 7757-83-7 Y Model 3D (JSmol) Gambar interaktif 3DMet {{{3DMet}}} ChEBI CHEBI:86477 N ChemSpider 22845 Y Nomor EC PubChem CID 24437 Nomor RTECS {{{value}}} UNII VTK01UQK3G Y CompTox Dashboard (EPA) DTXSID2044260 InChI InChI=1S/2Na.H2O3S/c;;1-4(2)3/h;;(H2,1,2,3)/q2*+1;/p-2 YKey: GEHJYWRUCIMESM-UHFFFAOYSA-L YInChI=1/2Na.H2O3S/c;;1-4(2)3/h;;(...

 

حقيقة غير مريحة (فيلم)

حقيقة غير مريحةAn Inconvenient Truth (بالإنجليزية) ملصق فيلم لحقيقة مزعجةمعلومات عامةالصنف الفني فيلم وثائقي[2][3][4] تاريخ الصدور 24 مايو 2006مدة العرض 94 داللغة الأصلية ‍الإنكليزيةالبلد الولايات المتحدةصيغة الفيلم فيلم 16 ملم الجوائز  القائمة ...  Broadcast Film Critics Association ...

Judo at the 2004 Summer Olympics

Judo competition Judoat the Games of the XXVIII OlympiadVenueAno Liossia Olympic HallDates14–20 August 2004← 20002008 → Judo at the2004 Summer OlympicsMenWomen60 kg48 kg66 kg52 kg73 kg57 kg81 kg63 kg90 kg70 kg100 kg78 kg+100 kg+78 kgvte Judo at the 2004 Summer Olympics took place in the Ano Liossia Olympic Hall and featured 368 judoka competing for 14 gold medals with seven different weight categories in both the men's and women's competitions. Japan dominated the even...

 

Lothar von Trotha

Lothar von Trotha Naissance 3 juillet 1848Magdebourg, Prusse Décès 31 mars 1920 (à 71 ans)Bonn, Allemagne Allégeance Royaume de Prusse (1865–1871) Empire allemand (1871–1906) Arme Armée prussienne Grade Général Années de service 1865 – 1906 Conflits Guerre austro-prussienneGuerre franco-prussienneRévolte des BoxersGénocide des Hereros Distinctions Pour le Mérite modifier  Lothar von Trotha en 1903 dans son uniforme du 9e bataillon de chasseurs à pied (de...

 

Michael Essien

Ghanaian association football player Michael Essien Essien in 2018Personal informationFull name Michael Kojo Essien[1]Date of birth (1982-12-03) 3 December 1982 (age 41)[2]Place of birth Accra, GhanaHeight 1.78 m (5 ft 10 in)[3]Position(s) MidfielderTeam informationCurrent team Nordsjælland (assistant coach)Youth career1998–1999 Liberty ProfessionalsSenior career*Years Team Apps (Gls)2000–2003 Bastia 66 (11)2003–2005 Lyon 71 (7)2005–2014 Ch...

Fageol Truck & Coach Company

Fageol Motors CompanyFageol Truck & Coach Company Rechtsform Company Gründung 1916 Auflösung 1939 Sitz Oakland, Kalifornien, USA Branche Kraftfahrzeuge Aktie der Fageol Motors Company vom 10. November 1921 Lkw von 1932 Bus Traktor von 1920 Fageol Truck & Coach Company, vorher Fageol Motors Company, war ein US-amerikanischer Hersteller von Kraftfahrzeugen.[1][2] Inhaltsverzeichnis 1 Unternehmensgeschichte 2 Fahrzeuge 3 Literatur 4 Weblinks 5 Einzelnachweise Unternehm...