在 Ada 中用递归绘制保龄球瓶（金字塔）

Question

我知道这是通过展示我最不复杂的作品来推动社区的善意，希望有人来救我，但我别无选择，没有任何损失。在过去的几周里，我已经了解了数据包、文件、类型、标志和框，但我没有涉及太多递归。特别是不使用递归绘图。我的考试大约还有一周，我希望这是足够的时间来重复和学习简单的递归技巧，比如画保龄球瓶或其他图案：

I I I I I
 I I I I
  I I I
   I I
    I
n = 5

递归的问题是我不太明白。你应该如何使用递归来解决像这样画图钉这样的问题？

我最接近的是

I I I
I I
I
n = 3

那是在使用

此代码现在可用

with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;

procedure pyramidchaser is

   subtype X_Type is Integer range 0..30;
   X: X_Type;
   Indent : Integer := 0;

   procedure Numbergrabber (X : out Integer) is
   begin

      Put("Enter a number: ");
      Get(X);
      Skip_Line;
   end Numbergrabber;


   procedure PrintSpaces(I : in Integer) is
   begin 
      if I in X_Type then
      Put(" ");
      else
     return;
      end if;

      PrintSpaces(I - 1);
   end Printspaces;




   procedure PrintPins(i, n: in Integer) is
   begin
      if i >= n then 
     return;
      end if;

    Put('I');
    Put(' '); 

    PrintPins(i + 1, n);
    end Printpins;




   function Pins (X, Indent: in Integer) return Integer is

      Printed : Integer;

   begin

      Printed:= 0;
      if X > 0 then
     PrintSpaces(Indent);
     PrintPins(0, X);
     New_Line; 

     Printed := X + Pins(X - 1, Indent + 1);
      end if;
      return Printed;

   end Pins;

   Bowlingpins : Integer;

begin

   Numbergrabber(X);
   Bowlingpins:= Pins(X, Indent);

end pyramidchaser;

但是我投入了一个总和我真的不需要只是开始递归部分我真的不知道为什么我这样做除了它似乎需要在那里。我尝试了一个完全不同的任务中的代码，这就是为什么它看起来是这样的。我知道 mod 2 会给我太多新行，但至少这是一种寻找金字塔高度的方法。我知道真正的方法类似于 N+1，因为随着不断增长的金字塔的每一步都需要一条新线，但我不知道如何实现它。

我不希望任何人提供完整的代码，但我希望有人能给我提供线索如何思考寻找解决方案。

我仍然可以在不知道递归的情况下通过考试，因为它通常有 2 个作业，一个是递归，一个不是递归，你需要通过一个或另一个，但考虑到我有一些时间，我想我给它一个机会.

一如既往，非常感谢所有为正义而战的人！

看到这个post引起了一些关注我想把金字塔扩展到一个更复杂的：

金字塔问题 2

希望有人看看。没想到会有这么多好的答案，我想为什么不把我所有的都扔出去呢。

Level 1
|=|

Level 2
|===|
||=||
|===|

Level 3

|=====|
||===||
|||=|||
||===||
|=====|

it needs to be figured out recursively. so some way it has to build both upwards and downwards from the center.

澄清一下，我正在为考试而学习，当然还有许多其他人会感谢代码让他们咬牙切齿。也许有一种简单的方法可以应用 Tama 在金字塔墙上的保龄球瓶线方面所构建的东西？

Answer 1

我不会用 Ada 编程（对我来说它看起来像一个奇怪的 Pascal），但是你的 Pins 函数中有一个明显的算法问题。

基本上，如果你想打印一个底数为 N 的金字塔，一直打印到底数为 1 的最底部，你需要做这样的事情（抱歉代码的粗略 pascalization）。

procedure PrintPins(i, n: Integer)
begin
    if i >= n then return;

    Ada.Text_IO.Put('I'); // Print pin
    Ada.Text_IO.Put(' '); // Print space

    PrintPins(i + 1, n);  // Next iteration
end;

function Pins(x, indent: Integer): Integer
   printed: Integer;
begin
    printed := 0;
    if x > 0 then
       PrintSpaces(indent); // Print indentation pretty much using the same artificial approach as by printing pins
       PrintPins(0, x);
       (*Print new line here*)

       (*Now go down the next level and print another
       row*)
       printed := x + Pins(x - 1, indent + 1); 
    end;
    return printed;
end

P.S。您不需要特定的函数来计算此处打印的引脚数。它只是范围为 1..N 的高斯序列和，由 N(N + 1)/2

给出

Answer 2

你要打印多少行就多少行。每行都有一个缩进，由一些 space 和一些引脚组成，每个引脚打印为 "I " （好的，行尾有一个额外的 space，但没有有人会看到的）。

开始时没有前导 space 和您被要求打印的图钉数量。

下一行需要多一个前导 space 和少一个引脚（当然，除非这意味着打印 no 个引脚，在这种情况下我们完成）。

Answer 3

你开发递归算法的方法是假装你已经有一个子程序可以做你想做的，除了第一位，你知道，或者可以弄清楚，如何做第一位。那么你的算法就是

Do the first bit
Call the subprogram to do the rest on what remains,
   taking into account the effect of the first bit, if necessary

诀窍在于 "Call the subprogram to do the rest" 是对您正在创建的子程序的递归调用。

子程序总是有可能在无事可做的情况下被调用，所以你要考虑到这一点：

if Ending Condition then
   Do any final actions

   return [expression];
end if;

Do the first bit
Call the subprogram to do the rest

大功告成。通过反复执行第一位直到结束条件为真，您最终完成了整个事情。

举个例子，Ada.Text_IO中的函数Get_Line可能是通过思考来实现的（通常不是这样实现的），"I know how to get the first Character of the line. If I have a function to return the rest of the line, then I can return the first Character concatenated with the function result."所以：

function Get_Line return String is
   C : Character;
begin
   Get (Item => C);

   return C & Get_Line;
end Get_Line;

但是，如果我们已经在一行的末尾，所以没有一行可以获取怎么办？

function Get_Line return String is
   C : Character;
begin
   if End_Of_Line then
      Skip_Line;

      return "";
   end if;

   Get (Item => C);

   return C & Get_Line;
end Get_Line;

对于您的问题，第一位是打印带有缩进和多个引脚的行，结束条件是没有更多行要打印时。

对于你的金字塔问题，这个尾递归方案是行不通的。你需要做 "middle recursion":

if Level = 1 then
   Print the line for Level

   return
end if

Print the top line for Level
Recurse for Level - 1
Print the bottom line for Level

Answer 4

保龄球瓶：

打印 ----I---- 只是：（为了便于阅读，我将在整个过程中使用破折号而不是空格）

Put_Line (4 * "-" & "I" & 4 * "-");

打印整个保龄球三角形可以是：

with Ada.Strings.Fixed; use Ada.Strings.Fixed;
with Ada.Text_IO;       use Ada.Text_IO;

procedure Main is
   procedure Print_Bowling_Line (Dashes : Natural; Pins : Positive) is
      Middle : constant String := (if Pins = 1 then "I"
                                   else (Pins - 1) * "I-" & "I");
   begin
      Put_Line (Dashes * "-" & Middle & Dashes * "-");
   end Print_Bowling_Line;
begin
   Print_Bowling_Line (0, 5);
   Print_Bowling_Line (1, 4);
   Print_Bowling_Line (2, 3);
   Print_Bowling_Line (3, 2);
   Print_Bowling_Line (4, 1);
end Main;

将重复的五行写成一个循环是很明显的。对于递归，有两种方式。

尾递归

尾递归是更自然的 'ask questions, then shoot' 方法；首先检查结束条件的参数，如果没有，做一些事情，最后调用 self.

procedure Tail_Recurse (Pins : Natural) is
begin
   if Pins = 0 then
      return;
   end if;
   Print_Bowling_Line (Total_Pins - Pins, Pins);
   Tail_Recurse (Pins - 1);
end Tail_Recurse;

头部递归

head递归是数学家的最爱；你如何构建 N 的证明？好吧，假设您已经有了 N-1 的证明，您只需应用 X 就可以了。同样，我们需要在寻找 N-1 的证明之前检查结束条件，否则我们将无休止地递归并导致堆栈溢出。

procedure Head_Recurse (Pins : Natural) is
begin
   if Pins < Total_Pins then
      Head_Recurse (Pins + 1); -- assuming N + 1 proof here
   end if;
   Print_Bowling_Line (Total_Pins - Pins, Pins);
end Head_Recurse;

如需完整代码，请展开以下代码段：

with Ada.Strings.Fixed; use Ada.Strings.Fixed;
with Ada.Text_IO;       use Ada.Text_IO;

procedure Main is
   Total_Pins : Natural := 5;

   procedure Print_Bowling_Line (Dashes : Natural; Pins : Positive) is
      Middle : constant String := (if Pins = 1 then "I"
                                   else (Pins - 1) * "I-" & "I");
   begin
      Put_Line (Dashes * "-" & Middle & Dashes * "-");
   end Print_Bowling_Line;

   procedure Tail_Recurse (Pins : Natural) is
   begin
      if Pins = 0 then
         return;
      end if;
      Print_Bowling_Line (Total_Pins - Pins, Pins);
      Tail_Recurse (Pins - 1);
   end Tail_Recurse;

   procedure Head_Recurse (Pins : Natural) is
   begin
      if Pins < Total_Pins then
         Head_Recurse (Pins + 1); -- assuming N + 1 proof here
      end if;
      Print_Bowling_Line (Total_Pins - Pins, Pins);
   end Head_Recurse;
begin
   Total_Pins := 8;
   Head_Recurse (1);
end Main;

为简单起见，我没有传递第二个数字，表示停止条件，而是在运行整体之前设置一次。

我总是觉得尝试通过应用一种技术来使代码更复杂而不是更复杂来学习它是很不幸的。所以我想向您展示一个递归真正发挥作用的问题。使用以下深度优先搜索伪代码编写一个程序，打印出迷宫中每两点之间只有一条路径的迷宫：

start by 'visiting' any field (2,2 in this example)
(recursion starts with this:)
while there are any neighbours that are unvisited,
   pick one at random and 
   connect the current field to that field and 
   run this procedure for the new field

正如您在下面的动画中看到的那样，它应该随机蜿蜒曲折，直到它到达左下角的 'stuck'，然后它 backtracks 到一个仍然有未访问邻居的节点。最后，当所有内容都填满后，所有仍处于活动状态的函数调用将 return 因为对于每个节点，将没有剩余的邻居可以连接。

您可以使用下面代码段中的框架代码。答案应该只修改 Depth_First_Make_Maze 程序。它不需要超过 15 行，在结果上调用 Get_Unvisited_Neighbours、Is_Empty、Get_Random_Neighbour 和 Connect（当然还有它本身）。

with Ada.Strings.Fixed; use Ada.Strings.Fixed;
with Ada.Text_IO;       use Ada.Text_IO;
with Ada.Containers;                     use Ada.Containers;
with Ada.Containers.Vectors;
with Ada.Numerics.Discrete_Random;

procedure Main is
   N : Positive := 11; -- should be X*2 + 1 for some X >= 1

   type Cell_Status is (Filled, Empty);
   Maze : array (1 .. N, 1 .. N) of Cell_Status := (others => (others => Filled));

   procedure Print_Maze is
   begin
  for Y in 1 .. N loop
     for X in 1 .. N loop
        declare
           C : String := (case Maze (X, Y) is
                             --when Filled => "X", -- for legibility,
                             when Filled => "█", -- unicode block 0x2588 for fun
                             when Empty  => " ");
        begin
           Put (C);
        end;
     end loop;
     Put_Line ("");
  end loop;
   end Print_Maze;

   type Cell_Address is record
  X : Positive;
  Y : Positive;
   end record;

   procedure Empty (Address : Cell_Address) is
   begin
  Maze (Address.X, Address.Y) := Empty;
   end Empty;

   procedure Connect (Address1 : Cell_Address; Address2 : Cell_Address) is
  Middle_X : Positive := (Address1.X + Address2.X) / 2;
  Middle_Y : Positive := (Address1.Y + Address2.Y) / 2;
   begin
  Empty (Address1);
  Empty (Address2);
  Empty ((Middle_X, Middle_Y));
   end Connect;

   function Cell_At (Address : Cell_Address) return Cell_Status is (Maze (Address.X, Address.Y));
   function Left (Address : Cell_Address) return Cell_Address is (Address.X - 2, Address.Y);
   function Right (Address : Cell_Address) return Cell_Address is (Address.X + 2, Address.Y);
   function Up (Address : Cell_Address) return Cell_Address is (Address.X, Address.Y - 2);
   function Down (Address : Cell_Address) return Cell_Address is (Address.X, Address.Y + 2);

   type Neighbour_Count is new Integer range 0 .. 4;
   package Neighbours_Package is new Ada.Containers.Vectors (Index_Type => Natural, Element_Type => Cell_Address);
   use Neighbours_Package;

   function Get_Unvisited_Neighbours (Address : Cell_Address) return Neighbours_Package.Vector is
  NeighbourList : Neighbours_Package.Vector;
   begin
  NeighbourList.Reserve_Capacity (4);
  if Address.X >= 4 then
     declare
        L : Cell_Address := Left (Address);
     begin
        if Cell_At (L) = Filled then
           NeighbourList.Append (L);
        end if;
     end;
  end if;
  if Address.Y >= 4 then
     declare
        U : Cell_Address := Up (Address);
     begin
        if Cell_At (U) = Filled then
           NeighbourList.Append (U);
        end if;
     end;
  end if;
  if Address.X <= (N - 3) then
     declare
        R : Cell_Address := Right (Address);
     begin
        if Cell_At (R) = Filled then
           NeighbourList.Append (R);
        end if;
     end;
  end if;
  if Address.Y <= (N - 3) then
     declare
        D : Cell_Address := Down (Address);
     begin
        if Cell_At (D) = Filled then
           NeighbourList.Append (D);
        end if;
     end;
  end if;
  return NeighbourList;
   end Get_Unvisited_Neighbours;

   package Rnd is new Ada.Numerics.Discrete_Random (Natural);
   Gen : Rnd.Generator;

   function Get_Random_Neighbour (List : Neighbours_Package.Vector) return Cell_Address is
  Random : Natural := Rnd.Random (Gen);
   begin
  if Is_Empty (List) then
     raise Program_Error with "Cannot select any item from an empty list";
  end if;
  declare
     Index : Natural := Random mod Natural (List.Length);
  begin
     return List (Index);
  end;
   end Get_Random_Neighbour;

   procedure Depth_First_Make_Maze (Address : Cell_Address) is
   begin
  null;
   end Depth_First_Make_Maze;
begin
   Rnd.Reset (Gen);
   Maze (1, 2) := Empty; -- entrance
   Maze (N, N - 1) := Empty; -- exit
   Depth_First_Make_Maze ((2, 2));
   Print_Maze;
end Main;

要查看答案，请展开以下代码段。

procedure Depth_First_Make_Maze (Address : Cell_Address) is
begin
   loop
  declare
     Neighbours : Neighbours_Package.Vector := Get_Unvisited_Neighbours (Address);
  begin
     exit when Is_Empty (Neighbours);
     declare
        Next_Node : Cell_Address := Get_Random_Neighbour (Neighbours);
     begin
        Connect (Address, Next_Node);
        Depth_First_Make_Maze (Next_Node);
     end;
  end;
   end loop;
end Depth_First_Make_Maze;

将递归转换为循环

考虑函数调用的工作原理；我们获取实际参数并将它们与函数地址一起放在 call stack 上。当函数完成时，我们再次从堆栈中取出这些值并放回 return 值。

我们可以通过用显式堆栈替换包含参数的隐式调用堆栈来转换递归函数。 IE。而不是：

procedure Foo (I : Integer) is
begin
   Foo (I + 1);
end Foo;

我们会将 I 放入堆栈，只要堆栈中有值，就查看顶部值并使用该值执行 Foo 过程的主体。当在该主体中调用 Foo 时，推送您将用来调用该过程的值，然后重新启动循环，以便我们立即开始处理新值。如果在这种情况下没有调用 self，我们将丢弃栈顶的值。

以这种方式重构递归过程将使您深入了解它的工作原理，特别是因为推送到堆栈现在与 'calling' 该函数分开，因为您明确地从堆栈中取出一个项目并且用它做点什么。

您将需要一个堆栈实现，这是一个合适的实现：

Bounded_Stack.ads

generic
   max_stack_size : Natural;
   type Element_Type is private;
package Bounded_Stack is
   type Stack is private;
   function Create return Stack;
   procedure Push (Onto : in out Stack; Item : Element_Type);
   function Pop (From : in out Stack) return Element_Type;
   function Top (From : in out Stack) return Element_Type;
   procedure Discard (From : in out Stack);
   function Is_Empty (S : in Stack) return Boolean;
   Stack_Empty_Error : exception;
   Stack_Full_Error : exception;
private
   type Element_List is array (1 .. max_stack_size) of Element_Type;
   type Stack is
      record
         list : Element_List;
         top_index : Natural := 0;
      end record;
end Bounded_Stack;

Bounded_Stack.adb

package body Bounded_Stack is

   function Create return Stack is
   begin
      return (top_index => 0, list => <>);
   end Create;

   procedure Push (Onto : in out Stack; Item : Element_Type) is
   begin
      if Onto.top_index = max_stack_size then
         raise Stack_Full_Error;
      end if;
      Onto.top_index := Onto.top_index + 1;
      Onto.list (Onto.top_index) := Item;
   end Push;

   function Pop (From : in out Stack) return Element_Type is
      Top_Value : Element_Type := Top (From);
   begin
      From.top_index := From.top_index - 1;
      return Top_Value;
   end Pop;

   function Top (From : in out Stack) return Element_Type is
   begin
      if From.top_index = 0 then
         raise Stack_Empty_Error;
      end if;
      return From.list (From.top_index);
   end Top;

   procedure Discard (From : in out Stack) is
   begin
      if From.top_index = 0 then
         raise Stack_Empty_Error;
      end if;
      From.top_index := From.top_index - 1;
   end Discard;

   function Is_Empty (S : in Stack) return Boolean is (S.top_index = 0);
end Bounded_Stack;

它可以用宽度*高度的最大堆栈大小实例化，因为最坏的情况是当您碰巧选择访问每个单元格一次的非分叉路径时：

N_As_Cell_Size : Natural := (N - 1) / 2;
package Cell_Stack is new Bounded_Stack(max_stack_size => N_As_Cell_Size * N_As_Cell_Size, Element_Type => Cell_Address);

把你对上一个作业的答案，并在没有递归的情况下重写它，而是使用上面的堆栈。

要查看答案，请展开以下代码段。

procedure Depth_First_Make_Maze (Address : Cell_Address) is
   Stack : Cell_Stack.Stack := Cell_Stack.Create;
   use Cell_Stack;
begin
   Push (Stack, Address);
   loop
  exit when Is_Empty (Stack);
  declare
     -- this shadows the parameter, which we shouldn't refer to directly anyway
     Address : Cell_Address := Top (Stack);
     Neighbours : Neighbours_Package.Vector := Get_Unvisited_Neighbours (Address);
  begin
     if Is_Empty (Neighbours) then
        Discard (Stack); -- equivalent to returning from the function in the recursive version
     else
        declare
           Next_Cell : Cell_Address := Get_Random_Neighbour (Neighbours);
        begin
           Connect (Address, Next_Cell);
           Push (Stack, Next_Cell); -- equivalent to calling self in the recursive version
        end;
     end if;
  end;
   end loop;
end Depth_First_Make_Maze;

Answer 5

这个程序的一个变体是在同一过程中同时使用头递归和尾递归。这样一个程序的输出是

Enter the number of rows in the pyramid: 5
I I I I I 
 I I I I 
  I I I 
   I I 
    I 
    I 
   I I 
  I I I 
 I I I I 
I I I I I 

N = 5

尾递归产生上三角，头递归产生下三角。

在 Ada 中用递归绘制保龄球瓶（金字塔）

Drawing Bowling Pins (pyramid) with Recursion in Ada

recursion

drawing

ada

保龄球瓶：

尾递归

头部递归

将递归转换为循环

Bounded_Stack.ads

Bounded_Stack.adb