Recursive Function Produces Stack-Overflow Error

Question

I'm attempting to solve a homework problem:

The first explorers of the Napieuler Mountains, in their leisure time, entertained themselves by shouting different phrases, to listen how the echo sounded. In their games, they noticed that the first echo was always a fraction of the original phrase, and the second was the same fraction of the first echo, and so on until everything was silent. For example, in the Napieuler area, the fraction was approximately 0.368.

When shouting a phrase of 100 seconds long, the first echo was 100 * 0.368 seconds long. The second was 100 * 0.368 * 0.368, and so on until it was imperceptible. Write a program that approximates, in text, the echo of the Napieuler Mountains. The program must receive by console the characteristic fraction of the echo that it wants to approximate (as a single decimal number). Then program must need to call a recursive function that you should receive a phrase. Finally, you should print out all the echoes of the phrase, including the original phrase shouted by a human. You must also show the total of repetitions, including the original phrase. As you can not easily calculate the time duration of a written phrase, you can assume that each letter takes a constant time, including spaces and punctuation. Round down multiplications with non-integer result. If you do the program correctly without calling a recursive function you will have a 0 in the problem.

Your function needs to be

Examples:

Enter the fraction: 0.369
Enter the sentence: I love mac and cheese
I love mac and cheese
cheese
se

Total of echoes: 3

Enter the fraction: 0.369
Enter the sentence: Today it is not a beautiful spring day. I wish ot was.
Today it is not a beautiful spring day. I wish ot was.
day. I wish it was.
it was.
s.
Total of echoes: 4

I've started writing the code, but I keep getting a stack-overflow error. Any help would be appreciated.

The code that keeps producing the stack-overflow error:

def echo(a,b):
    if len(b)>=2:
        return [b]+echo(a,b[(-(int(len(b)*a))):])
    else:
        return []

print(echo(0.369,"I love mac and cheese."))

Barmar · Accepted Answer · 2019-04-04 04:56:23Z

1

When len(b) == 2 then len(b) * a == 0.738, and int(len(b)*a) is 0. -0 is the same as 0, so you're making the recursive call with b[0:], which is the same as b, so you recurse infinitely.

You need to stop recursing when int(a * len(b)) == 0.

def echo(a,b):
    newlen = int(len(b)*a)
    if newlen > 0:
        return [b]+echo(a,b[-newlen:])
    else:
        return [b]

print(echo(0.369,"I love mac and cheese"))

answered Apr 4, 2019 at 4:56

Barmar

789k57 gold badges555 silver badges669 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Niayesh Isky · Accepted Answer · 2019-04-04 07:24:46Z

You can debug this yourself using a few simple lines of code. If you artificially limit your code from stack-overflowing by adding a counter to limit it to 10 recursions, and add a print statement to see the state of your program in every recursive call, you can easily find out what your code is doing and compare it to what you expect it to be doing:

def echo(a,b, counter=0):
    if counter < 10 and len(b)>=2:
        print('counter is: ', counter, ', I am using index: ', (-(int(len(b)*a))), ' which gives: ', b[(-(int(len(b)*a))):])
        return [b]+echo(a,b[(-(int(len(b)*a))):], counter+1)
    else:
        return []

Calling print(echo(0.369,"I love mac and cheese.")) on this gives us:

counter is:  0 , I am using index:  -8  which gives:   cheese.
counter is:  1 , I am using index:  -2  which gives:  e.
counter is:  2 , I am using index:  0  which gives:  e.
counter is:  3 , I am using index:  0  which gives:  e.
counter is:  4 , I am using index:  0  which gives:  e.
counter is:  5 , I am using index:  0  which gives:  e.
counter is:  6 , I am using index:  0  which gives:  e.
counter is:  7 , I am using index:  0  which gives:  e.
counter is:  8 , I am using index:  0  which gives:  e.
counter is:  9 , I am using index:  0  which gives:  e.
['I love mac and cheese.', ' cheese.', 'e.', 'e.', 'e.', 'e.', 'e.', 'e.', 'e.', 'e.']

This means that, as Joran said, you end up calculating this piece infinitely:

'e.'[0:]

which always evaluates to 'e.'.

With this knowledge, I'm sure you'll be able to figure out what to do to fix your code.

Joran Beasley · Accepted Answer · 2019-04-04 04:51:07Z

0

on your last iteration you have e.

which is len 2

you do echo(a,b[-0:])

which actually evaluates to echo(a,b[0:])

which calls it again with e.

theres 2 characters you need to change (one deletion and one insertion) that will correct your code

answered Apr 4, 2019 at 4:51

Joran Beasley

114k13 gold badges167 silver badges187 bronze badges

Collectives™ on Stack Overflow

Recursive Function Produces Stack-Overflow Error

Examples:

Total of echoes: 3

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Examples:

Total of echoes: 3

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related