Welcome, guest | Sign In | My Account | Store | Cart

Simple recursive function to non-recursive function (Python recipe) by Sunjay Varma
ActiveState Code (http://code.activestate.com/recipes/577724/)

This recipe is a simple solution for turning a recursive function into a non-recursive function.

Python, 26 lines
Download
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import os

def recursive(path):
	"""Move through all files, directories, and subdirectories of a path"""
	yield path
	for name in os.listdir(path):
		fullpath = os.path.join(path, name)
		if os.path.isdir(fullpath):
			for subpath in recursive(fullpath):
				yield subpath
		else:
			yield fullpath


def nonrecursive(path):
	"""Move through all files, directories, and subdirectories of a path"""
	paths = [path]
	while paths:
            dpath = paths.pop(0)
            yield dpath
            for name in os.listdir(dpath):
                    fullpath = os.path.join(path, name)
                    if os.path.isdir(fullpath):
                            paths.append(fullpath)
                    else:
                            yield fullpath

Recursive can mean calling a function within a function. So if you have function func and you call func within itself, your function is recursive. Sometimes you have a problem where the easiest way to solve it is to make the function act this way. This can lead to problems where Python gives you an error if you recur to deeply.

A solution to this would be to use a list. A list of items which need to be run through the same code again. By wrapping the code to run again in a loop, the task of running through all the objects in that list becomes trivial.

Tags: function, list, recursive, substitute

2 comments

mohamed nabil 11 years, 7 months ago  # | flag

This 2nd method (nonrecursive) is not working properly but the 1st one is working good ..

example :

a path like that :

ls -l /root/test/best/hist/fest/ total 8 drwxr-xr-x 2 root root 4096 2012-09-10 18:20 hest drwxr-xr-x 2 root root 4096 2012-09-10 18:20 test

the output of the two functions :

In [101]: list(recursive('/root/test'))
Out[101]: ['/root/test', '/root/test/best', '/root/test/best/hist', '/root/test/best/hist/fest', '/root/test/best/hist/fest/hest', '/root/test/best/hist/fest/test']

In [102]: list(nonrecursive("/root/test")) Out[102]: ['/root/test', '/root/test/best', '/root/test/hist']

mohamed nabil 11 years, 7 months ago  # | flag

Okay i solved the bug in the 2nd function it should be

def nonrecursive(path): """Move through all files, directories, and subdirectories of a path""" paths = [path] while paths: dpath = paths.pop(0) yield dpath for name in os.listdir(dpath): fullpath = os.path.join(dpath, name) if os.path.isdir(fullpath): paths.append(fullpath) else: yield fullpath

note that : fullpath = os.path.join(dpath, name) # not path as that was the bug