Popular Python recipes tagged "recursion"http://code.activestate.com/recipes/langs/python/tags/recursion/2016-03-01T20:41:13-08:00ActiveState Code RecipesComputing simple list functions recursively (Python) 2016-03-01T20:41:13-08:00Vasudev Ramhttp://code.activestate.com/recipes/users/4173351/http://code.activestate.com/recipes/580617-computing-simple-list-functions-recursively/ <p style="color: grey"> Python recipe 580617 by <a href="/recipes/users/4173351/">Vasudev Ram</a> (<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/algorithms/">algorithms</a>, <a href="/recipes/tags/lists/">lists</a>, <a href="/recipes/tags/python/">python</a>, <a href="/recipes/tags/python2/">python2</a>, <a href="/recipes/tags/recursion/">recursion</a>, <a href="/recipes/tags/recursive/">recursive</a>). </p> <p>This recipe shows how to compute some simple list functions (functions that operate on lists) using simple recursive algorithms. Simple non-recursive algorithms exist for these tasks; this recipe is just for illustrative purposes. However, the principles described can be used for more complex recursive algorithms, for which non-recursive algorithms might be more complex than the recursive ones.</p> RecursionError exception: concise and informative output (Python) 2015-07-05T23:46:59-07:00elazarhttp://code.activestate.com/recipes/users/4187847/http://code.activestate.com/recipes/578660-recursionerror-exception-concise-and-informative-o/ <p style="color: grey"> Python recipe 578660 by <a href="/recipes/users/4187847/">elazar</a> (<a href="/recipes/tags/debugging/">debugging</a>, <a href="/recipes/tags/exception/">exception</a>, <a href="/recipes/tags/handler/">handler</a>, <a href="/recipes/tags/recursion/">recursion</a>). Revision 3. </p> <p>Replaces the default exception hook with one that, upon "infinite recursion", removes the last cycle. This results in a significantly cleaner and shorter error message.</p> <p>Usage: simply import &lt;module&gt; as _</p> <p>For more details see the descussion here: <a href="https://mail.python.org/pipermail/python-ideas/2013-September/023190.html" rel="nofollow">https://mail.python.org/pipermail/python-ideas/2013-September/023190.html</a></p> Recursive Mandelbrot Generation (Python) 2013-08-11T03:46:46-07:00Bill Picketthttp://code.activestate.com/recipes/users/4174028/http://code.activestate.com/recipes/578635-recursive-mandelbrot-generation/ <p style="color: grey"> Python recipe 578635 by <a href="/recipes/users/4174028/">Bill Pickett</a> (<a href="/recipes/tags/mandelbrot/">mandelbrot</a>, <a href="/recipes/tags/pygame/">pygame</a>, <a href="/recipes/tags/recursion/">recursion</a>). Revision 12. </p> <p>This program recursively generates a Mandelbrot set using Python and PyGame. The size of the window must be a power of two or you will get rendering errors in the final image. It was written as an exercise in recursion, primarily to further my own understanding of that.</p> Recursive find and replace in all files in directory with regex (Python) 2013-03-21T12:33:44-07:00ccpizzahttp://code.activestate.com/recipes/users/4170754/http://code.activestate.com/recipes/578312-recursive-find-and-replace-in-all-files-in-directo/ <p style="color: grey"> Python recipe 578312 by <a href="/recipes/users/4170754/">ccpizza</a> (<a href="/recipes/tags/directory/">directory</a>, <a href="/recipes/tags/recursion/">recursion</a>, <a href="/recipes/tags/regular_expressions/">regular_expressions</a>, <a href="/recipes/tags/replace/">replace</a>). </p> <p>Search and replace files recursively in a given directory. Accepts regular expressions as search and replacement patterns.</p> <p><strong>Example usage</strong>:</p> <pre class="prettyprint"><code>python find_replace_regex.py ".", "&lt;span[^&gt;]*&gt;", "&lt;div&gt;", "*.html" backup </code></pre> <p><strong>Note</strong>: On win32 the <code>&lt;</code> and <code>&gt;</code> symbols are interpreted by the shell as input/output redirection even when they are surrounded with single or double quotes, and therefore need to be escaped with the caret character <code>^</code>.</p> Recursively print (nested) dictionaries (Python) 2012-04-04T15:20:42-07:00Mauricio Dada Fonseca de Freitashttp://code.activestate.com/recipes/users/4179701/http://code.activestate.com/recipes/578094-recursively-print-nested-dictionaries/ <p style="color: grey"> Python recipe 578094 by <a href="/recipes/users/4179701/">Mauricio Dada Fonseca de Freitas</a> (<a href="/recipes/tags/dictionary/">dictionary</a>, <a href="/recipes/tags/print/">print</a>, <a href="/recipes/tags/recursion/">recursion</a>). </p> <p>Snippet of code that uses recursion to print nested dictionaries. It does not sort the entries!</p> Permutation and combination using recursive generator (Python) 2011-10-04T05:44:19-07:00Shao-chuan Wanghttp://code.activestate.com/recipes/users/4168519/http://code.activestate.com/recipes/577890-permutation-and-combination-using-recursive-genera/ <p style="color: grey"> Python recipe 577890 by <a href="/recipes/users/4168519/">Shao-chuan Wang</a> (<a href="/recipes/tags/combinatorics/">combinatorics</a>, <a href="/recipes/tags/generators/">generators</a>, <a href="/recipes/tags/permutation/">permutation</a>, <a href="/recipes/tags/recursion/">recursion</a>). Revision 2. </p> <p>This recipes demonstrates how to use recursive generator to implement permutation and combination.</p> Recursive Functional State Machine (Python) 2011-05-20T13:46:48-07:00Stefan Tunschhttp://code.activestate.com/recipes/users/4178042/http://code.activestate.com/recipes/577709-recursive-functional-state-machine/ <p style="color: grey"> Python recipe 577709 by <a href="/recipes/users/4178042/">Stefan Tunsch</a> (<a href="/recipes/tags/functional/">functional</a>, <a href="/recipes/tags/recursion/">recursion</a>, <a href="/recipes/tags/state_machine/">state_machine</a>). </p> <p>This is a simple state machine that takes a functional approach. It requires trampoline from pysistence.func to avoid the recursion limit.</p> <p>Namedtuples are used to define the different states. globals() is used to reference the states. (This could also be done putting states into a separate module and getting them through getattr.)</p> <p>In this recipe the functions called in the different states need to return a boolean, which defines the success or failure event.</p> Destroying Directories (Python) 2011-04-21T02:55:31-07:00Stephen Chappellhttp://code.activestate.com/recipes/users/2608421/http://code.activestate.com/recipes/577670-destroying-directories/ <p style="color: grey"> Python recipe 577670 by <a href="/recipes/users/2608421/">Stephen Chappell</a> (<a href="/recipes/tags/delete/">delete</a>, <a href="/recipes/tags/directory/">directory</a>, <a href="/recipes/tags/recursion/">recursion</a>). </p> <p>When files and directories need to be securely deleted, there are many tools in existence that people can turn to for their needs. While there are many ways one might go about manually deleting files and removing directories, this recipe provides a sample implementation of what may be considered throughout the process. This destructive command line program takes the path to a directory as a command line argument and does its best to render it and its contents unrecoverable. There are much better and inclusive applications than this one, but those wishing to write their own utilities may take some inspiration from this recipe while writing their own tools.</p> <p>If there are any recommendation for this recipe or if anyone wishes to down-vote this recipe, please provide corrective criticism showing the the program's faults and give suggestions on how you would fix any problems that it might have.</p> converting numbers to their alphabetical style (Python) 2011-03-17T06:57:06-07:00amir naghavihttp://code.activestate.com/recipes/users/4177294/http://code.activestate.com/recipes/577607-converting-numbers-to-their-alphabetical-style/ <p style="color: grey"> Python recipe 577607 by <a href="/recipes/users/4177294/">amir naghavi</a> (<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/recursion/">recursion</a>, <a href="/recipes/tags/string/">string</a>). Revision 4. </p> <p>converts numbers to alphabetical numbers </p> Recoursive File Moving (Python) 2010-09-28T19:01:24-07:00shawnhttp://code.activestate.com/recipes/users/4175099/http://code.activestate.com/recipes/577411-recoursive-file-moving/ <p style="color: grey"> Python recipe 577411 by <a href="/recipes/users/4175099/">shawn</a> (<a href="/recipes/tags/files/">files</a>, <a href="/recipes/tags/recursion/">recursion</a>). Revision 3. </p> <p>This script is placed in a location then run. All files underneath the root will be propagated to the top level, while deleting any old directory's.</p> <p>Problems: If you have large files in nested folders you will be copying them multiple times.</p> <p>p.s. shoulda used walk() but i'm newb</p> Minimalistic Memoization (Python) 2010-05-06T16:59:52-07:00Ahmed El Deebhttp://code.activestate.com/recipes/users/4173897/http://code.activestate.com/recipes/577219-minimalistic-memoization/ <p style="color: grey"> Python recipe 577219 by <a href="/recipes/users/4173897/">Ahmed El Deeb</a> (<a href="/recipes/tags/caching/">caching</a>, <a href="/recipes/tags/memoization/">memoization</a>, <a href="/recipes/tags/recursion/">recursion</a>). </p> <p>Minimalistic Memoization in python, just works, doesn't take care of cleaning up the cache however.</p> Simple regex engine, elementary Python (Python) 2010-07-10T10:43:30-07:00Joost Behrendshttp://code.activestate.com/recipes/users/4174081/http://code.activestate.com/recipes/577251-simple-regex-engine-elementary-python/ <p style="color: grey"> Python recipe 577251 by <a href="/recipes/users/4174081/">Joost Behrends</a> (<a href="/recipes/tags/cached/">cached</a>, <a href="/recipes/tags/parse/">parse</a>, <a href="/recipes/tags/parsing/">parsing</a>, <a href="/recipes/tags/recursion/">recursion</a>, <a href="/recipes/tags/regular_expressions/">regular_expressions</a>). Revision 40. </p> <p>A short engine for testing against a regex, understanding the 3 common quantifiers ?,+,* (non-greedy) working on characters, ., [...], [^...], \s, \S, bracketed patterns and group designators \N. Accepts unicode objects and fixed-width encoded strings (but problems with eventual comparisons of trailing bytes in multi-byte utf-letters). Captures up to 10 groups ( (?:...) implemented), which can be used for back referencing and in xreplace(). Captured groups are accessible after the search in the global list xGroups. | is supported, but only in groups and needing nested=True. nested=False is making '(' and ')' common letters.</p> <p>This is not about Python or for Python, there it has little use beside re. But regarding that re needs about 6,000 lines you might agree with the author, that these 176 lines are powerful. This was the reason to publish it as a recipe - as a kind of (fairly complete) minimal example of a regex tester and as an example for corresponding recursive structures in data (TokenListCache) and code.</p> <p>Working on this improved the author's understanding of regular expressions - especially of their eventual "greed". "Greedy" quantifiers are a concept, which has to be explained seperately and is coming unexpected: Whoever is scanning a text for <code>'&lt;.*&gt;'</code>, s/he will search SGML tags, not the whole text. Even with the star's "greediness" the code has to take care, that <code>'.*'</code> doesn't eat the whole text finding no match for <code>'&lt;.*&gt;'</code> at all. Thus the standard syntax with greedy quantifiers cannot be simpler to implement than this with its mere 3 lines 101, 111 and 121 preventing any greed. Perhaps it is faster - otherwise it is difficult to understand, why the concept "greed" is existing at all.</p> <p>This engine might be useful here and then under circumstances with nothing else available. Its brevity eases translation to other languages and it can work with arbitrary characters for STAR or PERHAPS (for example).</p> Sudoku solver in functional-programming style (Python) 2010-04-23T12:35:13-07:00Arnau Sanchezhttp://code.activestate.com/recipes/users/4173270/http://code.activestate.com/recipes/577188-sudoku-solver-in-functional-programming-style/ <p style="color: grey"> Python recipe 577188 by <a href="/recipes/users/4173270/">Arnau Sanchez</a> (<a href="/recipes/tags/functional/">functional</a>, <a href="/recipes/tags/recursion/">recursion</a>, <a href="/recipes/tags/sudoku/">sudoku</a>). Revision 10. </p> <p>A simple brute-force Sudoku solver written in functional-programming style. This code is not aimed for speed, the goal is to write a clear, compact and (hopefully) pedagogical functional solution.</p> Recursive file/folder cleaner (Python) 2011-02-12T20:30:59-08:00Alia Khourihttp://code.activestate.com/recipes/users/4169084/http://code.activestate.com/recipes/576643-recursive-filefolder-cleaner/ <p style="color: grey"> Python recipe 576643 by <a href="/recipes/users/4169084/">Alia Khouri</a> (<a href="/recipes/tags/cleaner/">cleaner</a>, <a href="/recipes/tags/cleaning/">cleaning</a>, <a href="/recipes/tags/files/">files</a>, <a href="/recipes/tags/folder/">folder</a>, <a href="/recipes/tags/pyc/">pyc</a>, <a href="/recipes/tags/recursion/">recursion</a>, <a href="/recipes/tags/svn/">svn</a>). Revision 24. </p> <p>This script recursively scans a given path and applies a cleaning 'action' to matching files and folders. By default files and folders matching the specified (.endswith) patterns are deleted. Alternatively, _quoted_ glob patterns can used with the '-g' or '--glob' option.</p> <p>By design, the script lists targets and asks permission before applying cleaning actions. It should be easy to extend this script with further actions and also more intelligent pattern matching functions.</p> <p>The getch (single key confirmation) functionality comes courtesy of <a href="http://code.activestate.com/recipes/134892/" rel="nofollow">http://code.activestate.com/recipes/134892/</a></p> <p>To use it, place the script in your path and call it something like 'clean':</p> <pre class="prettyprint"><code>Usage: clean [options] patterns deletes files/folder patterns: clean .svn .pyc clean -p /tmp/folder .svn .csv .bzr .pyc clean -g "*.pyc" clean -ng "*.py" converts line endings from windows to unix: clean -e .py clean -e -p /tmp/folder .py Options: -h, --help show this help message and exit -p PATH, --path=PATH set path -n, --negated clean everything except specified patterns -e, --endings clean line endings -g, --glob clean with glob patterns -v, --verbose </code></pre> Lazy, recursive generator function (Python) 2008-12-14T10:04:29-08:00Don Sawatzkyhttp://code.activestate.com/recipes/users/4168423/http://code.activestate.com/recipes/576585-lazy-recursive-generator-function/ <p style="color: grey"> Python recipe 576585 by <a href="/recipes/users/4168423/">Don Sawatzky</a> (<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/generator/">generator</a>, <a href="/recipes/tags/lazy_evaluation/">lazy_evaluation</a>, <a href="/recipes/tags/recursion/">recursion</a>). Revision 4. </p> <p>This procedure was proposed as a challenge to Python and other languages as the most concise coding. See Icon programming on the web. This is a lazy, recursive generator. It can be implemented several ways in Python with lists, iteration, and recursion. However, the lists increase in size exponentially with each iteration and recursion plus they are saved in every recursion. This recipe develops a lazy generator function.</p> Matlab code for displaying 'struct' details (Python) 2008-09-05T13:31:54-07:00Kaushik Ghosehttp://code.activestate.com/recipes/users/4166965/http://code.activestate.com/recipes/576489-matlab-code-for-displaying-struct-details/ <p style="color: grey"> Python recipe 576489 by <a href="/recipes/users/4166965/">Kaushik Ghose</a> (<a href="/recipes/tags/matlab/">matlab</a>, <a href="/recipes/tags/recursion/">recursion</a>, <a href="/recipes/tags/structure/">structure</a>, <a href="/recipes/tags/tree/">tree</a>). </p> <p>This code, when passed a MATLAB structure, will recursively go into it and print out the form of the struct.</p>