Debug recursion problem; incorrect output

Question

I am trying to write a program that'll find the length of the longest (adjacent) increasing subsequence in a vector with n elements.

I have written my code with recursion for exercise on understanding the subject. When trying to compile the program earlier, instead of 4, my output was 12 on getting the longest increasing sequence. I'm trying to get the correct output. I'm under suspicion that my counters are not incrementing correctly. My "largest element" function works properly, but my issues lie within my sequence function. Help would be appreciated. I am still learning how recursion works.

Here is my code (.hpp file just has my two prototypes):

#include <iostream>
#include <vector>
#include "increasing_sequences_recursive.hpp"

int main() {
    std::vector<int> numbers;
    int input;
    int startIdx = 0;

    std::cout << "Enter a set of numbers (0 to stop): " << std::endl;

    while (true) {
        std::cin >> input;

        if (input != 0) {
            numbers.push_back(input);
        }
        else {
            break;
        }
    } 
    
    startIdx = numbers.size();
    std::cout << "Length of longest sequence: " <<
           increasing_sequences_recursive(numbers, startIdx);

    return 0;
}

// Recursively find the largest sequence
int increasing_sequences_recursive(std::vector<int> &numbers, int startIdx) {
    int counter = 0;
    int maxCounter = 0;

    if (startIdx == 1) {
        return 1;
    }
    int largeElmt = largestElement(numbers, startIdx);
    counter += increasing_sequences_recursive(numbers, startIdx - 1);
    if (numbers[startIdx - 1] <= largeElmt) {//numbers[startIdx]) {
        counter++;
        if (counter >= maxCounter) {
            maxCounter = counter;
        }
    }
    else {
        if (counter >= maxCounter) {
            maxCounter = counter;
        }
    }

    return maxCounter;
}

// Recursively find the largest element.
int largestElement(std::vector<int> &numbers, int n) {
    // Assume n >= 1; Find largest element in the first
    // n elements of n "numbers"
    if (n == 1)
        return numbers[n - 1];

    int res = largestElement(numbers, n - 1);
    if (res > numbers[n - 1])
        return res;

    return numbers[n - 1];
}

Mikhail · Accepted Answer · 2020-02-08 22:43:38Z

This sounds like a homework assignment, thus I'm not going to find a bug in your code since it won't be useful for you in any sense. Instead, I'll give some hints that I hope will lead you in the right direction.

First, there is nothing weird C++-specific in your code going on. Thus, it is essentially not a C++ question, but rather an algorithmic question.

The essence of recursion is to formulate a parametrized task F(N) in terms of the task of lower values of the parameter, e.g. in terms of F(N-1), and to define a trivial case, e.g. F(0). In your case, F(N) might stand for "the length of the longest increasing subsequence withing the first N+1 elements of the whole sequence" (I use "N+1" here to support zero-based indexing). How could we express F(N) in terms of F(N-1)?

Let's call the sequence A, and it's Nth element A[N] (starting with zero). Then we can say that F(N) is F(N-1)+1 in case A[N] >= A[N-1] and 1 otherwise. Check for yourself. And of course F(0) is 1. Now your task is to translate this definition into C++. The code should look MUCH simpler than the one you came up with. But again, I'm not going to provide it here, since you should make it yourself.

HTH

Community · Accepted Answer · 2020-06-20 09:12:55Z

First algorithmic flaw:

There is an algorithmic flaw here:

int largeElmt = largestElement(numbers, startIdx);    // (1)<========= 
counter += increasing_sequences_recursive(numbers, startIdx - 1);
if (numbers[startIdx - 1] <= largeElmt) {             // (2)<=========  
    counter++;

In (1), you look for the largest element in the startIdx first numbers. Since largestElmt is the largest in the subarray, the condition in (2) is always true. So you always add 1 to the recursive result, that starts at 1. So in the end, you only count the number of elemnts in the array (although in a complicated manner).

Second algorithmic flaw:

Now you could correct this by just checking that the last numbers are decreasing:

 if (numbers[startIdx-2]<=numbers[startIdx - 1] )    // no need for largest

This is ok from the index perspective, since startIdx is guaranteed to be at least 2. Unfortunately, your recursion does not take into account the contiguity. So you'll just count the subsequent pairs that are increasing, without restarting the count in case of disruption. So here you'll find 8.

The way out?

You need to distinguish in your recursion the case where you prolonge a sequence (just adding one to the current length), and the case where you have a disruption (and have to restart from 1). In both cases, you must keep track of the longest sequence so far. So you'll need at least to pass something more as recursion parameter if you want a recursion element by element.

But does it have to be so? If not, you could loop to look for a sequence of increasing numbers and use recursion to find the largest such sequence in the rest of the array once you find a disruption. This would be much much easier !

Collectives™ on Stack Overflow

Debug recursion problem; incorrect output

2 Answers 2

Comments

First algorithmic flaw:

Second algorithmic flaw:

The way out?

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

First algorithmic flaw:

Second algorithmic flaw:

The way out?

Comments

Your Answer

Sign up or log in

Post as a guest

Related