# [Tutor] request for sugestions on fragement of code for generating truth-tables

Danny Yoo dyoo at hkn.eecs.berkeley.edu
Sat Apr 1 04:27:02 CEST 2006

```
> Then, the output is like so:
>
>  >>> atoms = ["a","b","c"]
>  >>> tvas = tva_dict_maker(atoms)
>  >>> display_tvas(tvas)
> a:True	b:True	c:True
> a:True	b:True	c:False
> a:True	b:False	c:True
> a:True	b:False	c:False
> a:False	b:True	c:True
> a:False	b:True	c:False
> a:False	b:False	c:True
> a:False	b:False	c:False

Hi Brian,

We might be able to take advantage of the recursive nature of this
problem.

I'll sketch out the idea and try to fight the temptation to write it out
in full.  *grin* If you haven't encountered recursion before, please shout
out and ask for more details.

When we look above, we're looking at the solution for tva_dict_maker-ing
the list ['a', 'b', 'c'].

But let's imagine what tva_dict_maker() looks like for a slightly smaller
problem, for ['b', 'c']:

b:True	c:True
b:True	c:False
b:False	c:True
b:False	c:False

If we look at this and use our pattern-matching abilities, we might say
that the solution for ['b', 'c'] really looks like half of the solution
for ['a', 'b', 'c'] That is, to get:

tva_dict_maker(['a', 'b', 'c'])

all we really need are the results of tva_dict_maker(['b', 'c']).  We can
then twiddle two copies of the samller solution to make 'a' either True or
False, combine them together, and we've got it.

Recursive approachs have two parts to them, a "base" case and an
"inductive" case:

1.  Figure out solutions for really simple examples.  For example, in
the problem above, We know that something like:

tva_dict_maker(['c'])

has a very simple solution, since we're only dealing with a list
of one element.  ([{'c': True}, {'c' : False}])

2.  And for larger problems, let's figure out a way to break the
problem into something smaller.  We might be able to take the
solution of the smaller problem and make it scale up.

So a recursive approach will typically fit some template like this:

## Pseduocode #########################################################
def recursive_problem(some_problem):
if some_problem is really obviously simple:
return the obviously simple answer to some_problem
otherwise:
smaller_problem = some way of making some_problem slightly
smaller.  On lists, usually attack list[1:].
small_solution = recursive_problem(smaller_problem)
full_solution = twiddle small_solution somehow to make it solve
some_problem
return full_solution
#######################################################################