为什么我的递归函数没有返回正确的值? [英] Why my recursive function doesn't return the right value?

问题描述

我正在实现二进制搜索，但是代码在下面，但是，它没有打印出正确的答案，而在函数体内却打印出了正确的答案，所以这让我感到非常困惑.

#include <iostream>
using namespace std;

int research(int a[], int target, int lowIndex, int highIndex)
{
    int finalIndex;
    cout << lowIndex << " " << highIndex << endl;
    int midIndex = (lowIndex + highIndex) / 2;
    if (a[midIndex] == target)
    {
        finalIndex = midIndex;
        cout << "The final index is: " << finalIndex << endl;
    }
    else
    {
        if (a[midIndex] < target)
        {
            research(a, target, midIndex + 1, highIndex);
        }
        else
        {
            research(a, target, lowIndex, midIndex - 1);
        }
    }
    return finalIndex;
}

int main()
{
    int* array = new int[1000];
    for (int i = 0; i < 1000; i++)
    {
        array[i] = i + 1;
    }
    cout << research(array, 234, 0, 999) << endl;
    return 0;
}

该行:

cout << "The final index is: " << finalIndex << endl;

打印出正确的最终索引，但行

cout << research(array, 234, 0, 999) << endl;

没有，而是打印出随机数.有人知道这里出了什么问题吗?谢谢！

解决方案

真正将finalIndex设置为任何值的唯一时间是a[midIndex] == target，因此，当您递归时，您将返回未初始化的变量的值./p>

(finalIndex变量在函数调用之间不共享-每个调用都使用自己的变量.)

您需要使用递归调用的返回值:

    if (a[midIndex] < target)
    {
        finalIndex = research(a, target, midIndex + 1, highIndex);
    }
    else
    {
        finalIndex = research(a, target, lowIndex, midIndex - 1);
    }

I'm implementing a binary search and the code is below, however, it doesn't print out the right answer buy it prints out correct answer inside the function body, so it makes me really confused.

#include <iostream>
using namespace std;

int research(int a[], int target, int lowIndex, int highIndex)
{
    int finalIndex;
    cout << lowIndex << " " << highIndex << endl;
    int midIndex = (lowIndex + highIndex) / 2;
    if (a[midIndex] == target)
    {
        finalIndex = midIndex;
        cout << "The final index is: " << finalIndex << endl;
    }
    else
    {
        if (a[midIndex] < target)
        {
            research(a, target, midIndex + 1, highIndex);
        }
        else
        {
            research(a, target, lowIndex, midIndex - 1);
        }
    }
    return finalIndex;
}

int main()
{
    int* array = new int[1000];
    for (int i = 0; i < 1000; i++)
    {
        array[i] = i + 1;
    }
    cout << research(array, 234, 0, 999) << endl;
    return 0;
}

The line:

cout << "The final index is: " << finalIndex << endl;

prints out the right final index but the line

cout << research(array, 234, 0, 999) << endl;

doesn't, instead it prints out random number. Anyone know what is going wrong here? Thank you!

解决方案

The only time you actually set finalIndex to anything is when a[midIndex] == target, so when you recurse you're returning the value of an uninitialised variable.

(The finalIndex variable isn't shared between function invocations - each invocation uses its own variable.)

You need to use the return value from the recursive calls:

    if (a[midIndex] < target)
    {
        finalIndex = research(a, target, midIndex + 1, highIndex);
    }
    else
    {
        finalIndex = research(a, target, lowIndex, midIndex - 1);
    }

这篇关于为什么我的递归函数没有返回正确的值?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！