Tips on how to make this a recursive function

JavaScript
1 
def check(text1,text2):
    if text1 =="":
        return True
     if text2 in text1:
        return True
    else:
        return False
        
     
    
def main():
    text2=str(raw_input("Enter the text2: "))
    text1= str(raw_input("Enter the text1: "))
    print(check(text1,text2))

main()

can you give me tips on how to make this recursive function? I have to go by each index like text1 n and compares the another text2 of index n keeps going tell it stops. text1=tion text2=automation the function i have doesn’t go on by one but actually just checks if its has same words in each one text1 in text2. In the recursive function it checks each index than returns true if text1=tion is there in another word text2= automation. Tips will be useful for me.

2

It would be great if you can articulate exactly what you’re trying to accomplish and why you want to use recursion accomplish this. Also, if you’re using a different language than JavaScript, you should specify it since this website is focused on learning JavaScript.

I’m guessing you’re trying to build a function that checks to see if text2 contains a substring of text1. Why bother with recursion when you can use the function text2.contains(text1); in JavaScript es6? Other languages have similar functions.

3

Im using python language. I know its no need for a recursion for this. But I’m practicing thats why.

4

Here is a good example of recursion in Python:

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

Your example is not a good use case for recursion.

5

I know that. I was trying to make like that recursion function. but did not work

6

NOTE: I edited your post for readability, adding a code block so it’s a bit clearer.

So this might not be the ideal exercise as the recursive solution is a little involved. I’ll just put a possible solution here - it could be a lot more concise, but I’ve tried to make it a bit more verbose so you can see each condition. You need to be really careful to explicitly handle every possible case, else you can very easily get into infinite recursion situations.

It’s easy enough to write a recursive function if text1 is a single character.

So for a function check(char, text) where char is a single character and text is the string you’re going to recurse over:

  1. if the length both the character and the text are 0, return True (exit as soon as possible if this is the case, this is a sanity check to stop the function erroring if "" and "" get passed as arguments).
  2. If the character is found in text, return True.
  3. If the length of text is 0, return False (it is important that this comes after the two conditions above).
  4. Otherwise run the function again with the first character from text dropped.
def check(char, text):
    if len(char) == 0 and len(text) == 0:
        return True
    if  len(text) == 0:
        return False
    if char == text[0]:
        return True
    else:
        return check(char, text[1:])

check("o", "hello")

You can step through this here.

But you want to check if a set of characters appears in the text. So we need to change the conditions slightly.

  1. If the length of text1 is greater than text2, it isn’t possible for text1 to be in text2, so return False (this replaces the len(text) == 0 check in the first function).
  2. If the length both the character and the text are 0, return True.
  3. If text1[0] == text2[0], need to check that text1[1] == text2[1] and so on, so we’ll split that out into another function.
    i. if that returns True, return True in the main function.
    ii. if it doesn’t, run the main function again with the first character in text2 dropped.
def check(text1, text2):
    if len(text1) > len(text2):
        return False
    if len(text1) == 0 and len(text2) == 0:
        return True
    if text1[0] == text1[0]:
        subcheck = substring_check(text1, text2)
        if subcheck:
            return True
        else:
            return check(text1, text2[1:])
        

def substring_check(str1, str2):
    if (len(str1) == 0):
        return True
    if (str1[0] != str2[0]):
        return False
    else:
        return substring_check(str1[1:], str2[1:])

check("llo", "hello")

Step through the code here

Apologies if there are any typing mistakes there, but hopefully that should be somewhat helpful.

7

Would you say a functional language like Haskell would be better for recursion then?

8

You don’t have a choice, there aren’t any loops. ML-based functional languages (Haskell, ML, OCaml, F# etc), Erlang-VM based languages (Erlang, Elixir, etc), Lisps (like Scheme), logic languages (like Prolog), none of those have looping constructs. Declarative languages, of which they are all types of, don’t have or need loops, they use recursion instead.

Python is imperative, and has awesome built in stuff for doing what recursion is used for in the above languages, so not necessary; it explicitly does not optimise for recursion, so it’s best avoided.

1 Like
9

I guess @zuzutahan was just practicing the theory as Python is an easy language to learn. :wink:

1 Like
10

Yeah I should have emphasised that - it may well be best avoided overall/unecessary when building real things in Python, but Python is a v good language to actually learn in so it’s a good way to investigate how recursion works; it might not be performant but it’s much easier to read the code than most of those other languages

(edit: edited my OP to take out the mentions of it not being the best lang for recursion)

1 Like