Chapter 15. Recursive functions

Table of Contents

15.1. Recursive functions definition
15.2. Flow of execution of recursive functions
15.3. Recursive data structures
15.4. Solutions

15.1. Recursive functions definition

In Chapter 11 we have introduced a way to execute repetitive tasks, but we have also mentionned that repetition can be done without the special for and whileloop statements. This chapter will explain this in detail.

Translate a cds sequence into its corresponding protein. Let's start with the example of the cds translation. In Chapter 11 we have already written functions that solve this task using either for (Example 11.1) or while (???). Let's remind the pseudocode of the examples:

INPUT: a cds sequence cds and a genetic code code

OUTPUT: the translated cds sequence prot

prot <- empty string
as long as there are still codons to translate:
1. codon <- get next codon from sequence cds
2. lookup the corresponding amino acid of codon codon in genetic code code and add it to prot
return prot

prot <- empty string
for each codon in sequence cds:
1. add the corresponding amino acid of the current codon to sequence prot using genetic code code
return prot

In both examples the translation is defined as:

the concatenation of the first codon of the sequence and the translation of the cds sequence without this codon or in more mathematical terms:
translation(cds) = code(cds[:3]) + translation(cds[3:])

This is a recursive definition of the translation function.

	Recursive function
	A recursive function is a function that use itself during the calculation procedure.

	Recursive definition
	A recursive definition of a function is a definition that uses the function itself in the definition.

It is important to notice that we need a terminal condition otherwise the recursion would never stop. In our case the recursion stops if there are no more codons to translate:

the protein sequence of the an empty cds sequence is empty
or in more mathematical terms: translation("") = ""

Therefore the pseudocode can be written as follow without using loop structures:

INPUT: a cds sequence cds and a genetic code code

OUTPUT: the translated sequence prot

if cds is empty:
1. *** This is the terminal condition ***
2. return empty string
otherwise:
1. *** This is the recursion ***
2. codon <- first codon of sequence cds
3. return the concatenation of the corresponding amino acid of the first codon of sequence cds in genetic code code and the translation of the rest of the cds sequence

and implemented in Python like that:

  code = {'ttt': 'F', 'tct': 'S', 'tat': 'Y', 'tgt': 'C',
        'ttc': 'F', 'tcc': 'S', 'tac': 'Y', 'tgc': 'C',
        'tta': 'L', 'tca': 'S', 'taa': '*', 'tga': '*',
        'ttg': 'L', 'tcg': 'S', 'tag': '*', 'tgg': 'W',
        'ctt': 'L', 'cct': 'P', 'cat': 'H', 'cgt': 'R',
        'ctc': 'L', 'ccc': 'P', 'cac': 'H', 'cgc': 'R',
        'cta': 'L', 'cca': 'P', 'caa': 'Q', 'cga': 'R',
        'ctg': 'L', 'ccg': 'P', 'cag': 'Q', 'cgg': 'R',
        'att': 'I', 'act': 'T', 'aat': 'N', 'agt': 'S',
        'atc': 'I', 'acc': 'T', 'aac': 'N', 'agc': 'S',
        'ata': 'I', 'aca': 'T', 'aaa': 'K', 'aga': 'R',
        'atg': 'M', 'acg': 'T', 'aag': 'K', 'agg': 'R', 
        'gtt': 'V', 'gct': 'A', 'gat': 'D', 'ggt': 'G',
        'gtc': 'V', 'gcc': 'A', 'gac': 'D', 'ggc': 'G',
        'gta': 'V', 'gca': 'A', 'gaa': 'E', 'gga': 'G',
        'gtg': 'V', 'gcg': 'A', 'gag': 'E', 'ggg': 'G'
       }

def rectranslate(cds, code):
    if cds == "":
        return ""
    else:
        codon = cds[:3]
        return  code[codon] + rectranslate(cds[3:], code)
	
print rectranslate("atgattgctggt", code)


14.4. Designing a module		15.2. Flow of execution of recursive functions