Question

ok this is from problem set three question one.
from string import*
def countSubStringMatchRecursive(target, key):
index = 0
count = 0

index = find(target, key, index)

if index != -1:
count += 1
index += len(key)
print "index %d" % (index)
print "target[index:]: %s" % (target[index:])
count += countSubStringMatchRecursive(target[index:], key)

return count
this code works, I took it from http://www.kevinladenheim.com/2011/07/mit-600-problem-set-3-problem-1.html because i didn't quite understand what was meant by re

Answer 1

recursive ( I guess its like iteration but with a smaller sample size each time?). my real question comes from "count += countSubStringMatchRecursive(target[index:], key)" I am a bit puzzled how this code allows it to add one to the count value for each inter iteration. Is it because the return within the definition is assigned to count, so it adds what the count value becomes each time? mad props if you understand my question lol ty

Answer 2

the return statement is the last statement and isn't part of the iteration, and the last count assignment is a recursive statement done if index is not found,

index=find(...)
if index!=-1:

so count really is assigned a value at count+=1, the second one only allows the recursion.

idk if i answered u cos i'm not clear about your question, but this is my general understanding of the code in ur question.

Answer 3

i haven't seen the problem set though so my knowledge to your question is limited. sorry if i was of no help here lol

Answer 4

x += something is the same as x = x + something.
the code you posted builds up a string of count + somethings for each recursion.

this link is a good explanation - but the language being used is scheme/lisp -
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2

Answer 5

same thing but different http://dpaste.com/842357/

Answer 6

Recursion is used when a problem can be solved by aggregating the results of solving a section of the problem. Recursion is the best way to traverse trees and graphs.

A recursive function, say one to reverse a string, will take one part of the problem, and call itself with the rest of the problem (string). Each time a function is called, it gets a frame, it's execution environment (mostly the memory where it's variables are stored). The calling code is pushed to the side, a reference to it is stored on a stack (a LIFO, Last In First Out structure).

One of the most important parts of a recursive function is the "base case", when to stop calling itself. The function can work on the problem before and/or after it calls itself, getting the results of the sub-problem. When the function is in the returning phase, it's referred to as unwinding.

A simple Python program:

def reverse( string ):
# the base case
if( len( string ) == 0 ):
return

char = string[ 0 ]
reverse( string[ 1: ] )
print char

if( __name__ == "__main__" ):
reverse( "Hello World" )

You can play around with this and get comfortable with what's going on in recursion.