CS 345 Homework 5

Due Tuesday Feb 21 at 9pm. Upload to Desire 2 Learn dropbox for homework 5.

Basic Recursion Solution

Sample Code Snippets from Lecture

# Useful code for using os.walk(path)

os.chdir('/path/to/some/directory')
print os.getcwd() 					# display current working directory
tree_gen = os.walk(os.getcwd()) 	# generate file structure starting at os.getcwd()
tree_seq = list(tree_gen) 			# convert generator object to python list.

# print data list in reverse order.
def print_rev(data):
	if not data:
		return
	
	print_rev(data[1:])
	print data[0],

# print data list in natural order.
def print_fwd(data):
	if not data:
		return
	
	print data[0],
	print_fwd(data[1:])


# Test the recursive functions above.

d = [i for i in range(0, 10, 2)] # generates even numbers between 2 and 8
print_fwd(d)
print_rev(d)

Description

Exercises from Chapter 4:

C-4.9, C-4.16, P-4.27

NOTE: P-4.27 – instead of implementing your own version of walk() function, I would like you to use the walk() function to print the entire file tree rooted at some directory given by walk(). Something similar to the following:

.
├── a
│   ├── aa
│   ├── ab
│   │   ├── aaa
│   │   ├── readthis.txt
│   │   └── readthistoo.txt
│   └── ac
├── b
│   ├── ba
│   └── bb
├── c
│   └── ca
└── t.json

Each exercise must be implemented as a function in one source code file. PLEASE indicate the exercise number for each function in a comment.

The first two exercises REQUIRE recursion.

Resources

DSAP Chapter 4

generators? lazy evaluation?

A potentially useful Python resource ==> Learn Python the Hard Way

What to Turn In?

Your submission will contain:

each of the three functions indicated above.
a call to each function

Solution

# This Python file uses the following encoding: utf-8
# hw-5 solution.py

import os

dash = '──'
bar_l = '└'
bar_t = '├'
bar = '│'

"""C-4.9 Write a short recursive Python function that finds the minimum and max- imum values in a sequence without using any loops.
"""
def minmax(seq, mn, mx):
	if not seq:  # base case
		return (mn, mx)
	if seq[0] < mn:
		mn = seq[0]
	if seq[0] > mx:
		mx = seq[0]
	return minmax(seq[1:], mn, mx)

"""C-4.16 Write a short recursive Python function that takes a character string s and outputs its reverse. For example, the reverse of pots&pans would be snap&stop.
"""
def revstr(s):
	if not s:
		return ''
	return revstr(s[1:]) + s[0] 


"""P-4.27 A version of walk(). You may also have a version that USES walk() to print the file tree. This shows recursive version.
"""
def showtree(p, level):
	
	if os.path.isfile(p):
		print '    ' * level + bar_t + dash + ' ' + os.path.basename(p)
		return None
	
	print '    ' * level + bar_l + dash + ' ' + os.path.basename(p)
	for i in os.listdir(p):
		showtree(os.path.join(p, i), level+1)


if __name__ == '__main__':
	sequence = [5, 3, 9, 1, 0, 8, 20, 2, 88]
	if sequence:
		initial = sequence[0]
		mn, mx = minmax(sequence[1:], initial, initial)
		print '\nMINIMAX OF', sequence, 'is', mn, 'and', mx

	forward_str = 'pots&pans'
	print '\n\nREVERSE OF', forward_str, revstr(forward_str)

	curr_path = os.getcwd()

	print '\n\nFILE TREE OF', os.path.basename(curr_path)
	showtree(curr_path, 0)