时间戳

首页 > 解决方案 > 递归函数的执行顺序

c++ - 递归函数的执行顺序

问题描述

我最近尝试了这个问题：

一排排有N酒。每年你要么卖最左边的酒，要么卖最右边的酒。第- 年的i酒有初始价格arr[i]和第 - 年y*arr[i]的价格y。最大可能的总利润是多少？

我能够使用递归正确解决问题，但我无法理解程序的执行顺序。

代码是：

  #include<iostream>
  using namespace std;

  int func(int arr[],int n,int l, int r, int y){
    if(y>n)
      return 0;
    if(l>n-1)
      return 0;
    if(r<0)
      return 0;

    cout<<"l is: "<<l<<" and r is: "<<r<<endl;

    int sum=max(arr[l]*y+func(arr,n,l+1,r,y+1), arr[r]*y+func(arr,n,l,r-1,y+1));

    return sum;
  }  


  int main()
  {
    int n=0;

    cin>>n;
    int arr[n];

    for (int i = 0; i < n; ++i){
      cin>>arr[i];
    }

    cout<<func(arr,n,0,n-1,1);

    return 0;
  }

对于输入n= 5&values= 2,4,6,2,5

输出是：

l is: 0 and r is: 4
l is: 0 and r is: 3
l is: 0 and r is: 2
l is: 0 and r is: 1
l is: 0 and r is: 0
l is: 1 and r is: 1
l is: 1 and r is: 2
l is: 1 and r is: 1
l is: 2 and r is: 2
l is: 1 and r is: 3
l is: 1 and r is: 2
l is: 1 and r is: 1
l is: 2 and r is: 2
l is: 2 and r is: 3
l is: 2 and r is: 2
l is: 3 and r is: 3
l is: 1 and r is: 4
l is: 1 and r is: 3
l is: 1 and r is: 2
l is: 1 and r is: 1
l is: 2 and r is: 2
l is: 2 and r is: 3
l is: 2 and r is: 2
l is: 3 and r is: 3
l is: 2 and r is: 4
l is: 2 and r is: 3
l is: 2 and r is: 2
l is: 3 and r is: 3
l is: 3 and r is: 4
l is: 3 and r is: 3
l is: 4 and r is: 4
64

由于多个参数，我无法想象递归在做什么。请解释递归如何开始执行，以及如何可视化使用更多参数的递归。

标签： c++algorithmrecursiondata-structures

解决方案

首先，没有定义 C++ 中的参数评估顺序。请参阅：https : //en.cppreference.com/w/cpp/language/eval_order 在您的情况下，max 的参数是从右到左评估的。

首先，您使用初始参数调用函数：

l = 0 , r = n-1, y = 1

到达语句 int sum=max(arr[l]*y+func(arr,n,l+1,r,y+1), arr[r]*y+func(arr,n,l,r-1,y+1)); 时，评估右侧并调用函数 for func(arr,n,0,r-1,y+1)。因为最右边的元素在 y 年被拾取，现在最右边的元素现在位于 index r-1。当您在 year 中y+1再次调用函数时，最右边的函数被调用r-2and y+2and r-3andy+3等等，直到您在递归中遇到基本情况。

当 r 等于 -1 时，该函数第一次达到基本情况。

l is: 0 and r is: 0

当 r 为 0 时打印。这意味着你做了：

int sum=max(arr[0]*y+func(arr,n,0+1,0,y+1), arr[0]*y+func(arr,n,0,-1,y+1));

然后要求右侧

func(arr,n,0,-1,y+n-1). 请注意， l 仍然为零，因为始终调用了递归的右侧。然后if(r<0)case 返回函数。然后评估上一步的左侧。由于再次存在递归，直到l>n-1每一步递增 l。

这称为深度优先搜索。

推荐阅读