{"id":1565,"date":"2016-02-05T17:37:28","date_gmt":"2016-02-05T16:37:28","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=1565"},"modified":"2022-12-03T22:58:51","modified_gmt":"2022-12-03T21:58:51","slug":"programmation-recursive","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/algorithmic\/recursive-programming\/","title":{"rendered":"Recursive programming"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"1565\" class=\"elementor elementor-1565\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-86fbe35 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"86fbe35\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-246832c\" data-id=\"246832c\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-06ec892 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"06ec892\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Algorithmic<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-678c955\" data-id=\"678c955\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-1c827b1 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"1c827b1\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Home page<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-2bfa5cd\" data-id=\"2bfa5cd\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-cf2c607 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"cf2c607\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Algorithme_r%C3%A9cursif\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-d0e57cc elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"d0e57cc\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-4bf8c4c0\" data-id=\"4bf8c4c0\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-d63ed6e elementor-widget elementor-widget-text-editor\" data-id=\"d63ed6e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/recursive-programming\/#Programmation-recursive\" >Recursive programming<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/recursive-programming\/#Recursivite-simple\" >Simple recursion<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/recursive-programming\/#Recursivite-multiple\" >Multiple recursion<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/recursive-programming\/#Autres-types\" >Other types<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/recursive-programming\/#Pile-dexecution\" >Execution stack<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/recursive-programming\/#Recursivite-terminale\" >Terminal recursion<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Programmation-recursive\"><\/span>Recursive programming<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Recursive programming is a programming technique that replaces loop instructions with function calls. The mechanism therefore consists, in the vast majority of cases, in creating a function which calls itself one or more times according to different criteria.<\/div>\n\n<p>The structure of a <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/\">algorithm<\/a> recursive is:<\/p>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<pre> algo () {condition 1 condition 2 ... condition n}<\/pre>\n<\/div>\n\n<p>The conditions are generally ifs, they include the stop conditions (does not return the function) or continuity conditions (relaunches the function or returns the function). The continuity conditions modify the inputs of the restarted function. A recursive function must have at least one stop condition.<\/p>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Recursivite-simple\"><\/span>Simple recursion<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">A simply recursive function calls itself at most once in each condition.<\/div>\n\n<p>The mathematical program is of the following type (example for the calculation of a power):<\/p>\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" class=\"alignnone wp-image-1623 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/puissance.png\" alt=\"recursive programming recursion terminal algorithmic power\" width=\"247\" height=\"71\" title=\"\"><\/figure>\n\n<p>Here is a simple example to calculate the factorial of n:<\/p>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<pre> int fact (n) {if (n == 0) return 1; else return n * fact (n-1); }<\/pre>\n<\/div>\n\n<p>Here we can see the fact that recursion behaves like a loop.<\/p>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Recursivite-multiple\"><\/span>Multiple recursion<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">A multiple recursive function can call itself multiple times in each condition.<\/div>\n\n<p>The mathematical program is of the following type (example for Pascal&#039;s relation):<\/p>\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" class=\"alignnone wp-image-1628 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/pascal.png\" alt=\"recursive programming algorithmic terminal recursion pascal multiple recursion\" width=\"357\" height=\"83\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/pascal.png 357w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/pascal-300x70.png 300w\" sizes=\"(max-width: 357px) 100vw, 357px\" \/><\/figure>\n\n<p>Will give for program:<\/p>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<pre> int pascal (n, p) {if (p == 0 || p == n) return 1; else return pascal (p, n-1) + pascal (p-1, n-1); }<\/pre>\n<\/div>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Autres-types\"><\/span>Other types<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p>Two algorithms are \u201cmutually\u201d recursive if one calls on the other and vice versa.<\/p>\n<p style=\"text-align: justify;\">An algorithm contains a &quot;nested&quot; recursion if a parameter of the recursion is a call to itself.<\/p>\n<\/div>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Pile-dexecution\"><\/span>Execution stack<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>The stack of execution of the current program is a memory location intended to memorize the parameters, the local variables as well as the return addresses of the functions being executed.<\/p>\n\n<p>This stack works according to the LIFO (last in first out) principle and has a fixed size. Here is the stack for the simple factorial, as soon as the program reads a method, it executes it, keeping the rest of the information on the stack, and it adds the new results to the top of the stack. Since it is LIFO, this last piece of information will then be read first, which is why it gives the impression of an execution pyramid:<\/p>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<pre>Call to fact (3) 3 * fact (2) Call to fact (2) 2 * fact (1) Call to fact (1) 1 * fact (0) Call to fact (0) Returns the value 1 Returns 1 * 1 Returns 2 * 1 Returns 3 * 2 Returns 6<\/pre>\n<\/div>\n\n<p>The Fibonacci sequence execution stack follows the same principle:<\/p>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<pre>int fibo (n) {return (n &lt;2)? 1: fibo (n-1) + fibo (n-2); }<\/pre>\n<\/div>\n<hr class=\"wp-block-separator\" \/>\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<pre>Fibo (3) Fibo (2) + wait Call to Fibo (2) Fibo (1) + wait Call to Fibo (1) Returns 1 1 + Fibo (0) Call to Fibo (0) Returns 1 Returns 1 + 1 2+ Fibo (1) Call to Fibo (1) Returns 1 Returns 2 + 1 Returns 3<\/pre>\n<\/div>\n\n<p>We clearly see here a roller coaster effect due to the successive popping of the function on the left as soon as it is encountered. It is easier to represent the stack of a multiple recursive function by a <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/traversal-of-graphs\/\">in-depth journey<\/a> (we go the farthest in the successors) of its recursive call tree:<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-1666 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/fibo.png\" alt=\"recursive programming recursion algorithmic terminal recursion multiple recursion Fibonacci call tree\" width=\"421\" height=\"339\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/fibo.png 421w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/fibo-300x242.png 300w\" sizes=\"(max-width: 421px) 100vw, 421px\" \/><\/figure>\n<\/div>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Recursivite-terminale\"><\/span>Terminal recursion<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">We say that a function is terminal recursive if the result of this call is the result of the function.<\/div>\n\n<p>Thus, the stack has nothing in memory throughout the recursion. This means that the returned value is directly the value obtained without there being any additional operation. Let us take the example of the factorial in a terminal recursive way:<\/p>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<pre> int fact (n, a) {if (n == 0) return a; else return fact (n-1, n * a); } \/\/ be careful, the value of a at the start is very important<\/pre>\n<\/div>\n\n<p>This is exactly the same as writing the following loop:<\/p>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<pre> while (n! = 0 {n * = a; n--;}<\/pre>\n<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>Algorithms Wiki homepage Recursive programming Recursive programming is a programming technique that replaces loop statements with function calls. The \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":1062,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1565","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1565","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=1565"}],"version-history":[{"count":4,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1565\/revisions"}],"predecessor-version":[{"id":17939,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1565\/revisions\/17939"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1062"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=1565"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}