Recursion algorithm

Python
1

How can ı code finding minimum value in any sequence using the recursion algorithm?

Your code so far

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/88.0.4324.190 Safari/537.36.

Challenge: Probability Calculator

Link to the challenge:

2

What have you tried so far?

3

Unfortunately, I don’t have much, except for a few meaningless lines. And I couldn’t share because delete all lines

4

Well, how are you approaching the problem?

With recursion, the big questions are

  1. what is your base case?
  2. what is your recursive case?
  3. how do you reduce your problem in each recursive function call
5

This time, ı’ve tried somethings according to big question with recursion but haven’t reached any clear result yet.
I know that it looks pretty weird but here is my attempt
Thanks a lots

def min_value(sequence, step=0):
if step == len(sequence) - 1:
smallest = sequence[step]

if len(sequence) - 1 > step:

    cur_value = sequence[step + 1]
    smallest = sequence[step]
    min_value(sequence, step + 1)
    if cur_value <= smallest:
        smallest = cur_value
    else:
        smallest = smallest
    print(smallest)
6

Why do you want to do this using recursion? I can’t see anything in the challenge description that mentions recursion. In general, if you’re just trying to find the smallest value in a list, the more efficient way to do it is to use an iterative algorithm, not a recursive one.

  1. Store the first value in the list in a variable (call it current_minimum or something)
  2. Loop over each item in the list
  3. If you find an item smaller than current_minimum, set current_minimum to that item
  4. Once you’ve looped over the whole list, whatever value is in current_minimum is the smallest value in the list.

Recursion is a little slower than iteration, so if you can do it easily using iteration, that’s probably a better solution. Recursion would be good if you were finding the minimum value in a nested structure, like a list of lists.

3 Likes
7

Thank you for your idea. I’ve already done that
I’m just trying to learn new algorithms. If you know the recursion algorithm in any challenge, I’m open to your ideas

def min_value(sequence):
        smallest = sequence[0]
        for item in sequence:
                if item < smallest:
                      smallest = item
        return smallest
1 Like
8

That’s a good reason! There are plenty of examples of problems that can be solved using recursive algorithms. For example:

  • Nested data structures:
    • “Flatten” a list of lists (eg. [[2, 6, 1], [5], [8, 9]] into a single list ([2, 6, 1, 5, 8, 9])
    • Print a list of lists as a 2D grid of values (eg. [[2, 1, 5], [3, 2, 8], [5, 6, 4]])
    • Store a chessboard as a 2D grid of pieces, and count the number of pawns on the board.
    • Check if a single value exists in a list of lists of lists of lists…
  • Computing the fibonacci sequence (where the next number in the sequence is the sum of the previous two numbers).
  • Minimax algorithm: make a basic AI for a 2-player game, where you simulate every possible move you could make, and then every possible way the opponent could respond, etc. (this one is be pretty challenging but it’s a famous algorithm and there’s lots about it on google).
1 Like
9

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.