递归和链表

Question

我想看看链表的表示。我创建了一个 class 用于创建链表：

class LinkedListNode
  attr_accessor :value, :next_node

  def initialize(value, next_node = nil)
    @value = value
    @next_node = next_node
  end
  def print_values(list_node)
    print "#{list_node.value} --> "
    if list_node.next_node.nil?
      print "nil"
      return
    else
      print_values(list_node.next_node)
    end
  end

  node1 = LinkedListNode.new(37)
  node2 = LinkedListNode.new(99, node1)
  node3 = LinkedListNode.new(12, node2)
  print_values(node3)
end

我得到：

practice.rb:24:in `<class:LinkedListNode>': undefined method `print_values' for LinkedListNode:Class (NoMethodError)

递归是一种调用自身的方法吗？是否可以让一个方法调用另一个方法来代替递归？还是不允许调用其他方法？

Answer 1

您应该将处理 class 的代码移出 class 定义：

class LinkedListNode

  attr_accessor :value, :next_node

  def initialize(value, next_node = nil)
    @value = value
    @next_node = next_node
  end

  def print_values(list_node)
    print "#{list_node.value} --> "
    if list_node.next_node.nil?
        print "nil"
        return
    else
        print_values(list_node.next_node)
    end
  end
end

node1 = LinkedListNode.new(37)
node2 = LinkedListNode.new(99, node1)
node3 = LinkedListNode.new(12, node2)

node3.print_values(node3)

该代码还有很多其他问题，例如 print_values 是一个 class 方法，而不是实例方法，但主要问题在上面。这就是我将代码转换为使用 class 方法打印值的方式：

class LinkedListNode

  attr_accessor :value, :next_node

  def initialize(value, next_node = nil)
    @value = value
    @next_node = next_node
  end 

  def self.print_values list_node
    print "#{list_node.value} --> "
    if list_node.next_node.nil?
        print "nil"
        return
    else
        print_values(list_node.next_node)
    end 
  end 
end

node1 = LinkedListNode.new(37)
node2 = LinkedListNode.new(99, node1)
node3 = LinkedListNode.new(12, node2)

LinkedListNode.print_values node3

希望对您有所帮助。

注意 @joelparkerhenderson 提供的答案实际上更好。

Answer 2

Is recursion a method calling upon itself?

是的，一般来说。有关细节、示例和例外情况，请参阅 Wikipedia。

如果你简化你的方法，你也许能够在你自己的代码中理解递归。

您编写的代码更类似于过程代码，而 Ruby 通常使用更类似于此的面向对象代码：

class LinkedListNode

  attr_accessor :value, :next_node

  def initialize(value, next_node = nil)
    @value = value
    @next_node = next_node
  end

  # This is how to write a typical Ruby recursive method.
  # Notice the method does something with this object's value,
  # then transfers control to the next object's same method name.

  def to_s
    "#{value} --> " + (next_node ? next_node.to_s : "nil")
  end

end

# This code is moved out of your class definition.
# This fixes one of the errors in your original code.

node1 = LinkedListNode.new(37)
node2 = LinkedListNode.new(99, node1)
node3 = LinkedListNode.new(12, node2)

print node3.to_s

Is it possible to have a method call on another method to replace recursion?

是的，一般来说。例如，在你的代码中，你可以调用一个使用迭代而不是递归的方法，就像这个例子。

递归：

  def to_s
    "#{value} --> " + (next_node ? next_node.to_s : "nil")
  end

迭代次数：

  def to_s
    s = ""
    node = self
    while node != nil
      s += "#{value} --> " 
      node = next_node
    end
    s += "nil"
  end

使用迭代实现的算法通常比使用递归实现的类似算法运行得更快。

某些类型的递归（包括您在此处的代码）比其他类型的递归更有效。您的代码是可以高效使用 tail call optimization.

的一个很好的代码示例

Answer 3

你的print_values方法是一个实例方法，虽然它没有使用其中的实例。

我相信您打算使用实例数据来实现：

class LinkedListNode
  attr_accessor :value, :next_node

  def initialize(value, next_node = nil)
    @value = value
    @next_node = next_node
  end
  def print_values
    print "#{value} --> "
    if next_node.nil?
      print "nil"
      return
    else
      next_node.print_values
    end
  end
end

node1 = LinkedListNode.new(37)
node2 = LinkedListNode.new(99, node1)
node3 = LinkedListNode.new(12, node2)
node3.print_values

另一种选择是使方法成为 static 方法，它不需要实例，如下所示：

class LinkedListNode
  attr_accessor :value, :next_node

  def initialize(value, next_node = nil)
    @value = value
    @next_node = next_node
  end
  def self.print_values(list_node)
    print "#{list_node.value} --> "
    if list_node.next_node.nil?
      print "nil"
      return
    else
      print_values(list_node.next_node)
    end
  end
end

  node1 = LinkedListNode.new(37)
  node2 = LinkedListNode.new(99, node1)
  node3 = LinkedListNode.new(12, node2)
  LinkedListNode.print_values(node3)

这两个选项都将被视为递归，因为该方法会调用自身。没有关于递归的规则（允许调用另一个方法），但是有些事情你需要注意，比如如果你没有一个好的停止条件，你的方法可能"explode" 出现堆栈溢出异常。

递归和链表

Recursion and linked list

ruby

recursion

list