CMSC 121 - 14 - Recursion

recursion_notes

### CMSC 12100
### Recursion

Consider the factorial. 

This is an iterative solution:

	def factorial_iterative(n):
		rv = 1 
		for val in range(2, n+1):
			rv = rv * val 
		return rv 

For a recursive solution, we have a base case and a recursive case. The base case has input 1 and recursive case has input n

	def factorial(n):
		if n == 1:
			return 1 
		elif n > 1:
			return n * factorial(n-1)

####Permutations

Suppose we have a list $$[1, 2, 3]$$ 

The trivial case is either 1 element or 0 elements. But we'll stick with the base case of 1 element definition. Recursive case will be element 1, followed by permutations of remaining elements. And then element 2, followed by permutations of remaining. Etc. 

	def permutations(p):
		if len(p) == 1:
			return [p]
		else:
			rv = []
			for val in p:
				p_prime = [v for v in p if v!= x]
				perms = permutations(p_prime)
				for perm in perms:
					pl = [x] + perm 
					rv.append(pl)
			return rv