再帰処理

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

> 「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

> ループだと期待通り「ノード0」が得られますが、
> 再帰だと「ノード3」が返却されます。

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

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

ありがとうございます。

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

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

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

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

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

> 具体的にどうすればいいですか？

こういうことです。

Private Function 再帰(node As TreeNode) As TreeNode

    Return If(node?.Parent Is Nothing, node, 再帰(node.Parent))

End Function

>> 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)」
というコードになるでしょうね。

ありがとうございます。

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

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

魔界の仮面弁士さんの

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

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

１段階目

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

となります。

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

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

shu 様、解説、ありがとうございます。

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

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