Question

2011 python Unit 1 Quiz , QU3
Hi was wondering if someone can give me some help understanding the defination in this example

def f(s):
if len(s) <= 1:
return s
return f(f(s[1:])) + s[0]

i am sruggling with understanding the functions within the fuctions
The example string to pass into the function is 'mat' and then 'math'

so for Mat it is greater than 1 so it goes into the second return statement
which is ( and i am might be getting this wrong
f (f (s[1:0])) + s[0]

f ( f( at) + m

it is at this point i get stuck.... does atm need to be passed into the function
would this not go on for ever.......

any pointers , would be great or links to previous questions , thanks a lot

Answer 1

Welcome to the wonderful, wacky world of recursion! Here is a link that will introduce you to recursion: http://www.freenetpages.co.uk/hp/alan.gauld/tutrecur.htm

This example is a bit gnarly, hard to read. I typed it out, and it works fine, it reverses the string passed in.

>>> def f( s ):
... if( len( s ) <= 1 ):
... return s
... return f( f( s[ 1: ] ) ) + s[ 0 ]
...
>>> f( "Mat" )
'atM'

Indentation is everything in Python. The "if" statement is what's called a "base case". It is the condition where we should stop recursing (calling ourself) and start backing out (this is called "unwinding"). So when we get to the last letter of s, we start unwinding.

If we have more than one character, the "if" would be false, so it will go on with the second, gnarly, return statement. There are two calls to function "f" in this statement. It's returning f called with the result of f called with the (current) string s[ 1: ] (which eliminates the first character of (current) s), and all of this gets the first character of s added to the end.

If you walk through this manually, just be careful to slavishly do the instructions like the machine would do.