CODEWITHSUNDEEP
python
dixonticonderoga
dixonticonderoga

Reputation: 31

Failing to understand recursion

New to Python and trying to understand recursion. I'm trying to make a program that prints out the number of times string 'key' is found in string 'target' using a recursive function, as in Problem 1 of the MIT intro course problem set. I'm having a problem trying to figure out how the function will run. I've read the documentation and some tutorials on it, but does anyone have any tips on how to better comprehend recursion to help me fix this code?

from string import *

def countR(target,key):
    numb = 0
    if target.find(key) == -1:
        print numb
    else:
        numb +=1
        return countR(target[find(target,key):],key)

countR('ajdkhkfjsfkajslfajlfjsaiflaskfal','a')

Upvotes: 3

Views: 265

Answers (4)

mariusnn
mariusnn

Reputation: 1897

By recursion you want to split the problem into smaller sub-problems that you can solve independently and then combine their solution together to get the final solution.

In your case you can split the task in two parts: Checking where (if) first occurence of key exists and then counting recursively for the rest.

Is there a key in there:
- No: Return 0.
- Yes: Remove key and say that the number of keys is 1 + number of key in the rest

In Code:

def countR(target,key):
    if target.find(key) == -1:
        return 0
    else:
        return 1+ countR(target[target.find(key)+len(key):],key)

Edit:
The following code then prints the desired result:

print(countR('ajdkhkfjsfkajslfajlfjsaiflaskfal','a'))

Upvotes: 8

kojiro
kojiro

Reputation: 77059

Most recursive functions that I've seen make a point of returning an interesting value upon which higher frames build. Your function doesn't do that, which is probably why it's confusing you. Here's a recursive function that gives you the factorial of an integer:

def factorial(n):
    """return the factorial of any positive integer n"""
    if n > 1:
        return n * factorial(n - 1)
    else:
        return 1 # Cheating a little bit by ignoring illegal values of n

The above function demonstrates what I'd call the "normal" kind of recursion – the value returned by inner frames is operated upon by outer frames.

Your function is a little unusual in that it:

  1. Doesn't always return a value.
  2. Outer frames don't do anything with the returned value of inner frames.

Let's see if we can refactor it to follow a more conventional recursion pattern. (Written as spoiler syntax so you can see if you can get it on your own, first):

def countR(target,key): idx = target.find(key)` if idx > -1: return 1 + countR(target[idx + 1:], key) else: return 0

Here, countR adds 1 each time it finds a target, and then recurs upon the remainder of the string. If it doesn't find a match it still returns a value, but it does two critical things:

  1. When added to outer frames, doesn't change the value.
  2. Doesn't recur any further.

(OK, so the critical things are things it doesn't do. You get the picture.)

Meta/Edit: Despite this meta article it's apparently not possible to actually properly format code in spoiler text. So I'll leave it unformatted until that feature is fixed, or forever, whichever comes first.

Upvotes: 1

Idan Arye
Idan Arye

Reputation: 12603

This is not how recursion works. numb is useless - every time you enter the recursion, numb is created again as 0, so it can only be 0 or 1 - never the actual result you seek.

Recursion works by finding the answer the a smaller problem, and using it to solve the big problem. In this case, you need to find the number of appearances of the key in a string that does not contain the first appearance, and add 1 to it.

Also, you need to actually advance the slice so the string you just found won't appear again.

from string import *

def countR(target,key):
    if target.find(key) == -1:
        return 0
    else:
        return 1+countR(target[target.find(key)+len(key):],key)

print(countR('ajdkhkfjsfkajslfajlfjsaiflaskfal','a'))

Upvotes: 1

Mene
Mene

Reputation: 3799

If key is not found in target, print numb, else create a new string that starts after the the found occurrence (so cut away the beginning) and continue the search from there.

Upvotes: 0

Related Questions