Visual Basic 中学校 掲示板 投稿内容
タグのない投稿を抽出 統計 RSS

Visual Basic 中学校 > 投稿一覧 >

再帰処理 解決済み

タグの編集...

投稿者 まこ   (社会人)   投稿日時 2021/2/14 12:21:27
VB2019、WindowsFormアプリケーションで現在、再帰処理について勉強しています。
お題として、「TreeNodeの親を辿って、RootNodeを得る」というのを、実験しています。

Treeviewの構成は以下で試しています。
「ノード3の親ノードのレベルが0じゃないなら、さらに、その親を調べる」というのを
再帰で書くには、どうすればいいでしょうか。最後はレベル0の「ノード0」を結果として得たいです。

ノード0
   |--ノード1
        |--ノード2
              |--ノード3


以下は自分でやってみたのですが、ループだと期待通り「ノード0」が得られますが、
再帰だと「ノード3」が返却されます。
デバッガで追いかけると
「ノード3」=>「ノード2」=>「ノード1」=>「ノード0」=>「ノード1」=>「ノード2」=>「ノード3」
と「ノード0」でReturnして欲しいのに、関数から抜けずに、逆戻りしてしまいます。

    Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
        'ノード3 
        Dim target As TreeNode = TreeView1.Nodes(0).Nodes(0).Nodes(0).Nodes(0)
        '親を辿ってルートを得る 
        Dim root1 As TreeNode = 再帰(target) '再帰では× 
        Dim root2 As TreeNode = ループ(target) 'ループでは〇 
    End Sub

    Private Function 再帰(node As TreeNode) As TreeNode
        If node Is Nothing Then Return Nothing
        Dim temp As TreeNode = node
        If temp.Level > 0 Then
            再帰(temp.Parent)
        End If
        Return temp
    End Function

    Private Function ループ(node As TreeNode) As TreeNode
        If node Is Nothing Then Return Nothing
        Dim temp As TreeNode = node
        While temp.Level > 0
            temp = temp.Parent
        End While
        Return temp
    End Function



投稿者 魔界の仮面弁士   (社会人)   投稿日時 2021/2/14 18:29:39
> 「TreeNodeの親を辿って、RootNodeを得る」

Parent プロパティが親ノードを表しています。
最上位ノード(RootNode)は、Parent が Nothing になります。

Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
    Dim node As TreeNode = TreeView1.SelectedNode
    Dim rootNode As TreeNode = node
    Do Until rootNode.Parent Is Nothing
        rootNode = rootNode.Parent
    Loop
    rootNode.Text = "これがルートです。"
End Sub


投稿者 魔界の仮面弁士   (社会人)   投稿日時 2021/2/14 18:35:47
> ループだと期待通り「ノード0」が得られますが、
> 再帰だと「ノード3」が返却されます。

Return された戻り値を捨てているからですね。

ループ版では、「temp = 別のノード」に相当する代入式がありますが、
再帰版にはそれが無いので、「Dim temp As TreeNode = node」のままになっているわけです。

投稿者 まこ   (社会人)   投稿日時 2021/2/14 20:31:54
ありがとうございます。

再帰の勉強の為にやっていて、Do-LoopやWhile-End Whileで、答えを導く自信はあるのですが
再帰処理の挙動が、理解出来ていません。

お題は何でも良かったのですが、「親=>子」、「子=>親」を辿るパターンは他でも応用がきく
と思い、このお題にしました。

本当に知りたいのは、再帰の途中で「特定の条件」になったら、「処理を終了して、その時点までの
値を得る」という事です。

今回の場合だと、ノードの親が「レベル0」又は提示いただいた「Nothing」になった時に、処理を終了
させる事です。
最初の質問でも書きましたが、
tempが「ノード3」=>「ノード2」=>「ノード1」=>「ノード0」=>「ノード1」=>「ノード2」=>「ノード3」
と変化するのですが、「ノード0」の所で処理を終了させるには、どうすればいいですか?

>Return された戻り値を捨てているからですね。
これの意味がわからないのですが、具体的にどうすればいいですか?

投稿者 魔界の仮面弁士   (社会人)   投稿日時 2021/2/14 21:33:54
> 具体的にどうすればいいですか?

こういうことです。

Private Function 再帰(node As TreeNode) As TreeNode
    Return If(node?.Parent Is Nothing, node, 再帰(node.Parent))
End Function


投稿者 魔界の仮面弁士   (社会人)   投稿日時 2021/2/14 21:49:29
>> Return された戻り値を捨てているからですね。
> これの意味がわからないのですが、

言い換えると、メソッドの戻り値を受け取っていないのが問題だということです。
Dim n As TreeNode = 再帰(temp.Parent)



元のコードはこうなっています。

Dim temp As TreeNode = node  '変数 temp に現在のノードを渡す 
If temp.Level > 0 Then
     再帰(temp.Parent)   'temp.Parent に対して何か処理しているが、変数 temp は node を指したまま 
End If
Return temp    'だから結局、これは「Return node」と何も変わらない 



元のコードを活かすのであれば、
 「node.Level = 0 の時は Return node」
 「node.Level > 0 の時は、Return 再帰(node.Parent)」
というコードになるでしょうね。

投稿者 まこ   (社会人)   投稿日時 2021/2/14 22:32:57
ありがとうございます。

なんとなく、理解できました。でもなんか、もやもや感が...
End Functionに到達した後に又、処理に戻るというのが、とても変な感じです。

教えてもらっておいて、すみません。
再帰とは、こういうものだと理解します。
どうも、ありがとうございました。

投稿者 shu   (社会人)   投稿日時 2021/3/2 13:59:38
魔界の仮面弁士さんの

Private Function 再帰(node As TreeNode) As TreeNode
    Return If(node?.Parent Is Nothing, node, 再帰(node.Parent))
End Function



を利用させてもらって

Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
        Dim target As TreeNode = TreeView1.Nodes(0).Nodes(0).Nodes(0)
        Dim root1 As TreeNode = 再帰(target)
End Sub



コードの関数を展開すると

1段階目
Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
        Dim target As TreeNode = TreeView1.Nodes(0).Nodes(0).Nodes(0).Nodes(0)
        Dim root1 As TreeNode = If(target?.Parent Is Nothing, target, 再帰(target.Parent))
End Sub



2段階目
Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
        Dim target As TreeNode = TreeView1.Nodes(0).Nodes(0).Nodes(0).Nodes(0)
        Dim root1 As TreeNode = If(target?.Parent Is Nothing, target, 
                   If(target.Parent?.Parent Is Nothing, target.Parent, 再帰(target.Parent.Parent)))
End Sub



3段階目
Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
        Dim target As TreeNode = TreeView1.Nodes(0).Nodes(0).Nodes(0).Nodes(0)
        Dim root1 As TreeNode = If(target?.Parent Is Nothing, target, 
                   If(target.Parent?.Parent Is Nothing, target.Parent,
                   If(target.Parent.Parent?.Parent Is Nothing, target.Parent.Paret, 再帰(target.Parent.Parent.Parent))))
End Sub


となりますがtarget.Parent.Parent?.Parent Is Nothing = nothing のため

Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
        Dim target As TreeNode = TreeView1.Nodes(0).Nodes(0).Nodes(0).Nodes(0)
        Dim root1 As TreeNode = If(target?.Parent Is Nothing, target, 
                   If(target.Parent?.Parent Is Nothing, target.Parent,
                   target.Parent.Parent))
End Sub


となり
target.Parent?.ParentはNothingでない為
Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
        Dim target As TreeNode = TreeView1.Nodes(0).Nodes(0).Nodes(0).Nodes(0)
        Dim root1 As TreeNode = If(target?.Parent Is Nothing, target, target.Parent.Parent))
End Sub


となり
target?.ParentはNothingでない為
Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
        Dim target As TreeNode = TreeView1.Nodes(0).Nodes(0).Nodes(0).Nodes(0)
        Dim root1 As TreeNode = target.Parent.Parent
End Sub


となります。

階層が変わっても同じ様に考えることが出来ます。
再帰処理の動作はまず深く潜っていき戻ってきて結果が出るという動きになります。

今回のような関数内の最後の部分で再帰を行っているものはループ構造に変更が出来る為
ループ構造で実装した方が処理コストが減ります。









投稿者 まこ   (社会人)   投稿日時 2021/3/3 08:33:00
shu 様、解説、ありがとうございます。

大変、よくわかりました。
こうして、展開して説明してもらうと、すごく理解できます。
横着して、頭だけで考えてしまうと、頭の中がスパゲッティ状態になり、わけがわからなくなります。
このように、紙に書きだせばよいということが、わかりました。
なんか、学生の頃の算数を思い出しました。

ご丁寧な解説、感謝いたします。