{"entities":{"Q519902":{"pageid":521669,"ns":120,"title":"Item:Q519902","lastrevid":62455689,"modified":"2026-04-11T06:12:48Z","type":"item","id":"Q519902","labels":{"en":{"language":"en","value":"A difference in complexity between recursion and tail recursion"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6699121"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q519902$190ACD01-A453-4043-A1F2-D6180E3C1D32","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d5a4b09adb5ebfadd509f660145642c1d63f3f4c","datavalue":{"value":{"text":"A difference in complexity between recursion and tail recursion","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q519902$61805000-E9AF-4961-BAD1-B4858F4B8284","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"20775a510e6b0eccda8153e4660931ce895379a6","datavalue":{"value":"1380.03038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q519902$E9AB5E3D-C8C4-41F4-8D4F-AE2BE9ACE7DC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"18346fb575f1fa261ddb649d2ee83123aa0f7398","datavalue":{"value":{"entity-type":"item","numeric-id":519901,"id":"Q519901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q519902$E9DCEA09-B4CD-4F10-9F44-1C2B1ADC42D9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b559743f011d61696dff04b2ecd3408df2541e49","datavalue":{"value":{"entity-type":"item","numeric-id":169698,"id":"Q169698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q519902$9E3CB738-8864-4449-A211-0A1D1E03B75F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"72c0e07ad537fb33330a33ecd7818cc14403de47","datavalue":{"value":{"time":"+2017-03-31T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q519902$0FD8F62F-1B2E-442C-8686-A98B563E3F2C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4c9a634fb89aadda3035a09d4fbfd874d8b80edb","datavalue":{"value":"Two types of recursive programs over abstract structures are considered in this paper -- the most general recursive programs and tail recursive programs (which are equivalent to iterative programs). There are structures over which these two types determine one and the same class of computable functions. However, is the price of the computations one and the same? The author answers this question negatively. He presents an example of an abstract structure, over which recursive and tail recursive definitions have the same expressive power. At the same time, a function over this structure is constructed that is computed by a general recursive program more efficiently than by any tail recursive program with respect to some natural complexity measure.","type":"string"},"datatype":"string"},"type":"statement","id":"Q519902$82AFFA41-FCDF-4A68-80BD-BCEA71E328C8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5a03c77f7b094c62085e038e7319825eeca971a4","datavalue":{"value":{"entity-type":"item","numeric-id":593174,"id":"Q593174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q519902$B05CC631-20BA-4DB6-B975-72E33A033395","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"bacc42d4ab28169bcab125a394e2c486e425337a","datavalue":{"value":"03D75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q519902$BA6E6CA5-F552-4DCD-8E9A-C29CAA98A8BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q519902$30E99455-582E-4DAA-9F89-C1CF27F3EE8A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"84742f3b6f6631df4d9d937e6c223c53bd3ffade","datavalue":{"value":"6699121","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q519902$FD0E89FE-9576-4DC7-AC9C-CD284C4B6DA6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a77e01832b964d31cfe6c22c73a1f5c8cd110d2d","datavalue":{"value":"abstract recursion theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q519902$F71FFDDA-256E-40CF-A1E3-0C76D6A692C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"062f1d1df6512c5ef0786155cc75df38da63705b","datavalue":{"value":"tail recursion","type":"string"},"datatype":"string"},"type":"statement","id":"Q519902$1A4E604F-037F-4910-B467-E31FE34E5DC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q519902$182E3628-A8FA-4376-98DB-E4BD0913C073","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be1268b65fc1d6781eb5c0f1073a98e5cb46f217","datavalue":{"value":"arithmetic","type":"string"},"datatype":"string"},"type":"statement","id":"Q519902$D7ADD648-A803-44ED-B128-7F00AD0BED69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q519902$1ECD3392-DE36-4F7B-9D3C-01E909580F2C","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q519902$B9F811BC-6698-40C4-AA01-C3EC785F724D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"28d7118ee3196ea0b9fdf08ecdb7418f7dac15f5","datavalue":{"value":"https://doi.org/10.1007/s00224-016-9673-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q519902$99DC5563-38B2-4380-9AD7-D8847F2292F6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"eb9fb1bb1469f98a2799e46839b4412bf7312bd3","datavalue":{"value":"W2310420552","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q519902$2F52FDD2-1778-495E-B77E-0CED4BE76F76","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"061a19ee3234aac047c04e00d7e240966a8f446a","datavalue":{"value":{"entity-type":"item","numeric-id":4018437,"id":"Q4018437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q519902$0B1B2CF1-2727-4ECA-BDFA-3FE6E5937B19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac3af2a5d6d90fc35dbcdf27c89fba0731ef592c","datavalue":{"value":{"entity-type":"item","numeric-id":1233308,"id":"Q1233308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q519902$A5B1B17A-97AE-4972-B084-76A1EBD630C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"931066bde4a90c03b20e2f09b6d6c97d36c11578","datavalue":{"value":{"entity-type":"item","numeric-id":3853126,"id":"Q3853126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q519902$E2045E8E-FDD2-4CE6-9E23-7BF1AE9EA3EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4de1f7c72b6bac648aba95904a5c8d4456301691","datavalue":{"value":{"entity-type":"item","numeric-id":1362906,"id":"Q1362906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q519902$BA12F416-AD87-42AD-8276-0B41DE45CA69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21f75da3bacd9ac00775278764ea7f958cad51be","datavalue":{"value":{"entity-type":"item","numeric-id":3860819,"id":"Q3860819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q519902$A0ABE09E-90FD-4195-8BFB-32B28AB322FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a52ac5bbffd41a566848fbe9bfbcc662e91a8615","datavalue":{"value":{"entity-type":"item","numeric-id":5659061,"id":"Q5659061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q519902$B8D9932B-B99A-478C-88A3-811873315CBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e25b37b725ad06028ceea57d7c456d1b9707a011","datavalue":{"value":{"entity-type":"item","numeric-id":5717061,"id":"Q5717061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q519902$C6EC71F1-461A-464D-BB8F-D1D51486EAA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6d1a80d5f402d5ea12dc856d29173fd95c38a09","datavalue":{"value":{"entity-type":"item","numeric-id":5277820,"id":"Q5277820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q519902$77707101-4DFF-413B-B95B-DF180EBC8B5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7091303a5936a3d2add9212809debc0350ec7c45","datavalue":{"value":{"entity-type":"item","numeric-id":4185781,"id":"Q4185781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q519902$9FAF6A1A-6B09-4406-AA30-6A103956476F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f388943e0d1d18afd6c344ca3a910cf335fce264","datavalue":{"value":{"entity-type":"item","numeric-id":1117214,"id":"Q1117214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q519902$C8A7FB2A-4ED8-4493-ACC8-1F7AFAB4AD38","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"89499df7558c4bf8d6d255a5b9ffd338dfe41520","datavalue":{"value":"10.1007/S00224-016-9673-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q519902$D8E832FF-B9F5-4DE2-9D98-BD72E2538338","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f3b6c5d192e1199c3d6ccd04095276789ced252","datavalue":{"value":{"entity-type":"item","numeric-id":1683704,"id":"Q1683704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cb5c81c79df5c6084ef628d442a7953856e0198","datavalue":{"value":{"amount":"+0.7441681027412415","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q519902$F6EE5237-2924-462A-A6CD-7B0970D34499","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c4591180b2d02b40e176873238da259d4069d29","datavalue":{"value":{"entity-type":"item","numeric-id":4842542,"id":"Q4842542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4af0bf50a27642a3aabf412cc80e5cbc5646fdd6","datavalue":{"value":{"amount":"+0.7282360196113586","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q519902$A66A827E-D770-49DF-8556-145529676FC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f16d9b5507c1ace1fc05034dd368f552a6668634","datavalue":{"value":{"entity-type":"item","numeric-id":4858828,"id":"Q4858828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46cc28e07ae77c7051572bcdcf6021014d666c38","datavalue":{"value":{"amount":"+0.7216584086418152","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q519902$768A0510-431B-4808-8D65-9A3996E20739","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93831ff863dbe876051fa89a948234e6e53da0e1","datavalue":{"value":{"entity-type":"item","numeric-id":1193596,"id":"Q1193596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60c9a798fe0e21004964113568020eb275def793","datavalue":{"value":{"amount":"+0.7146466374397278","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q519902$2855D37C-2DBB-4C83-971A-9CEAD05D5F29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb6a428810b63d9a8e9b31e51db48c75b9d37e25","datavalue":{"value":{"entity-type":"item","numeric-id":5220181,"id":"Q5220181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"524fd3c4bf8051553fa94f899fd109546559b699","datavalue":{"value":{"amount":"+0.7133694291114807","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q519902$82244F16-BCC1-4BB2-8CC4-4F8D47307869","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A difference in complexity between recursion and tail recursion","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_difference_in_complexity_between_recursion_and_tail_recursion"}}}}}