Recursive arbitrary Sequence

Question

I am trying to define a recursive geometric function that will ask the user the first value of the sequence and the multiplier value for the sequence. The function should give a sequence of the desired length as the argument and produce as the return value a list of the arbitrary Geometric sequence of that length. As a clarifying example, if the user provides 5 as the start value and 3 as the multiplier with the desired length of 6, the first 6 elements of the arbitrary geometric sequence would be [5, 15, 45, 135, 405, 1215]

When I run this code, I get the sequence in weirdly random order. This is my code so far:

# This will define a recursive arbitrary Geometric sequence function
def recursive_geo_helper(length):
    start = int(input("Enter the first value of the sequence: "))
    multiplier = int(input("Enter the value that must be multiplied: "))
    return actual_recursive_geo(length, start, multiplier)


def actual_recursive_geo(length, start, multiplier):
    sequence = []

   # print(start)
    if length <= 1:

        exit()
       # return sequence

    else:
        sequence.append(start)

        start = start * multiplier
        length = length - 1



        return actual_recursive_geo(length, start, multiplier)

#recursive_geo_helper(5)

print(recursive_geo_helper(6))

Please provide an [MCVE](https://stackoverflow.com/help/mcve) that demonstrates how your program fails to behave as expected, and how you would expect it to behave. — hnefatl, Mar 31 '18 at 16:27
This code makes no sense: `exit` after `return`, two calls to `actual_recursive_geo` in the recusive case, and each recursive call makes its own list...? — Davis Herring, Mar 31 '18 at 16:32
I just created a new stack overflow account so I am new to the environment in terms of tools to ask the question. Let me try editing it again. — Saalim Qamar, Mar 31 '18 at 16:39

Olivier Melançon · Answer 1 · 2018-04-01T02:36:45.420

Your code unfortunately does not make much sense. Here are just some issues with it: the builtin exit should never be used outside of the shell, your function returns no base case and even if it did, it would not recursively appends to that base case.

Solving all these issues, here is what your recursive solution would look like.

def actual_recursive_geo(length, a, r):
    if length <= 0:
        return  [] # base case
    else:
        return [a] + actual_recursive_geo(length - 1, a * r, r) # prepend to your base case

Although this is somewhat inefficient since it does a lot of unnecessary list concatenation..

Generators

Let me recommend to start from scratch using a better suited data structure to represent infinite sequences: generators.

Generators can lazily represent infinite sequences. Moreover Python provides you with the itertools standard library to manipulate them. Here we will return a generator and slice it with itertools.islice.

import itertools

def geometric_input():
    """
    Prompt the user for an initial value and a ratio
    Return the corresponding geometric series
    """
    a = int(input("Enter the first value of the sequence: "))
    r = int(input("Enter the ratio: "))
    return geometric_sequence(a, r)


def geometric_sequence(a, r):
    """ Return a generator for the sequence x_i = a * r ^ i"""
    r_exp = 1
    while True:
        yield a * r_exp
        r_exp *= r


seq = geometric_input()

first_elements = list(itertools.islice(seq, 6))

print(*first_elements)

Here is the output.

Enter the first value of the sequence: 5
Enter the ratio: 3
5 15 45 135 405 1215

Another nice thing about generators is that an element is consumed on generation. This means that if you slice the generator again, you will get the next elements in the sequence

next_elements = list(itertools.islice(seq, 6))

print(*next_elements)
# prints: 3645, 10935, 32805, 98415, 295245, 885735

I appreciate your answer. However, as per my assignment guidelines, I am strictly limited to use only recursion to create the geometric sequence. I will edit my current code and repost it again. — Saalim Qamar, Mar 31 '18 at 17:51
@SaalimQamar here I updated the answer to provide a recursive solution. I still left the generator approach as I believe as you evolve as a Python dev, this is what you should strive to achieve. — Olivier Melançon, Mar 31 '18 at 18:46
Thank you very much @OlivierMelançon. Unfortunately, I am unable to see the updated solution of recursion. Will it be possible to post it again with only recursive function? I will be very grateful for you. — Saalim Qamar, Mar 31 '18 at 18:52
I don't think performance is an issue in this case and the recursive solution is much simpler to understand. Plus I think you're underestimating your nice recursive solution, it was better than mine at least :) — icc97, May 15 '18 at 09:53

icc97 · Answer 2 · 2018-05-15T09:47:55.727

0

I believe your problem is that you're declaring the sequence in the function and not returning it correctly.

Also if we've going to use recursion we can go one step further and avoid mutating our variables by only passing through the modified variables to the recursive call.

def geo(sequence, length, multiplier):
    if length <= 1:
        return sequence
    else:
        return sequence + geo([sequence[-1] * multiplier], length - 1, multiplier)

Here's the output from the REPL:

>>> geo([5], 6, 3)
[5, 15, 45, 135, 405, 1215]

P.S. I'm more of a JavaScript than a Python guy, so I first did it in JS and then ported it.

This is the equivalent function in JavaScript:

function geo(sequence, length, multiplier) {
    if (length <= 1) {
      return sequence
    }
    return sequence.concat(geo([sequence.slice(-1) * multiplier], length - 1, multiplier))
}
console.log(geo([5], 6, 3))

edited May 15 '18 at 09:47

answered Mar 31 '18 at 18:15

icc97

11,395
8
76
90

Thank you very much for this. How do I incorporate my two input statements within your updated version of the code? I used a helper function in mine. My program should ask me the start value and the multiplier value in order to generate the sequence. – Saalim Qamar Mar 31 '18 at 18:55
I'm guessing this is some kind of homework. There's a tiny modification to the return line of your helper function that you should be able to figure out. – icc97 Mar 31 '18 at 19:00
I ran the function that you had posted, however, I do not understand the return statement that you wrote under the else statement. It gives me an error when I run it saying that int van cannot be subscribable. – Saalim Qamar Mar 31 '18 at 21:50
It's because you're calling `geo(5, 6, 3)` instead of `geo([5], 6, 3)`. You need to pass in a list – icc97 Mar 31 '18 at 21:54
Please ignore the previous comment, I figured it out – Saalim Qamar Mar 31 '18 at 22:45

Recursive arbitrary Sequence

2 Answers2

Generators