级联递归 - 数组中的最大元素

Question

我试图弄清楚如何编写级联递归函数来查找整数数组中的最大元素。我尝试编写一些代码，但我认为我的函数比级联更线性。

这是我的帕斯卡代码。矢量 = 整数数组，l 和 r 用作索引，首先 l = 0 且 r = v - 1 的大小。我尝试在没有辅助变量的情况下编写此代码以获得最大值，但是，我不确定是否可以在没有这样的变量的情况下以级联方式完成此任务。

function cascademax(v: vector; l, r: integer): integer;
begin
    if r = 0 then
        result := v[0]
    else
    begin
        if (l < 0) or (r < 0) or (l > r) then
            result := -1
        else
        begin
            if l = r then
            begin
                if v[l] >= v[r] then
                    result := v[l]
                else
                    result := v[r]
            end
            else 
            begin
                if v[l] >= v[r] then
                    result := cascademax(v, l, r - 1)
                else
                    result := cascademax(v, l + 1, r)
            end;
        end;
    end;
end;

如果您用任何语言编写代码，或者至少告诉我是否需要辅助变量，我会很高兴

Answer 1

递归确实不是解决这个问题所必需的，但如果您出于教学原因坚持使用它，那也不难。对于您需要的任何递归函数：

• 至少有一种基本情况，其中函数返回而不是递归调用自身。
• 至少在一种情况下，函数递归调用自身，更新参数/参数以收敛于基本情况之一。

program Test;
const
  max_dim = 10;

type
  arr = array [1..max_dim] of integer;

var
  a : arr = (2, 3, 8, -1, 0, 9, 11, 3, 4, 5);

  function casc_max(a : arr; cur_idx : integer; max : integer) : integer;
  begin
    if cur_idx > max_dim then
      casc_max := max
    else if a[cur_idx] > max then
      casc_max := casc_max(a, cur_idx + 1, a[cur_idx])
    else
      casc_max := casc_max(a, cur_idx + 1, max)
  end;

begin
  writeln(casc_max(a, 1, a[1]));

end.

$ fpc test.pas
Free Pascal Compiler version 3.0.4+dfsg-18ubuntu2 [2018/08/29] for x86_64
Copyright (c) 1993-2017 by Florian Klaempfl and others
Target OS: Linux for x86-64
Compiling test.pas
Linking test
/usr/bin/ld.bfd: warning: link.res contains output sections; did you forget -T?
24 lines compiled, 0.1 sec
$ ./test
11