Optimization of deep recursion

Optimization of deep recursion

using System.Collections;

Stack st = new Stack();

// Order traversal in binary tree 
// recursive ....
List<int> list = new List<int>();
 List<int> inorderTraversal(TreeNode root)
{
    
    if (root == null)
        return list;
    inorder(root.left);
    list.Add(root.val);
    inorder(root.right);
    return list;
}
 void inorder(TreeNode root)
{
    
    if (root == null)
        return;
    inorder(root.left);
    list.Add(root.val);
    inorder(root.right);
}


foreach (var item in inorderTraversal(new TreeNode(1, null, new TreeNode(2, new TreeNode(3, null, null), null))))
{
    
    Console.WriteLine(item);
}


// Explicit stack ：



List<int> inorderTraversal1(TreeNode root)
{
    
    List<int> res = new List<int>();
    LinkedList<TreeNode> stk = new LinkedList<TreeNode>();
    while (root != null || !(stk.Count == 0))
    {
    
        while (root != null)
        {
    
            stk.AddLast(root);
            root = root.left;
        }
        root = stk.Last();
        stk.RemoveLast();
        res.Add(root.val);
        root = root.right;
    }
    return res;
}

Console.WriteLine("======================");

foreach (var item in inorderTraversal1(new TreeNode(1, null, new TreeNode(2, new TreeNode(3, null, null), null))))
{
    
    Console.WriteLine(item);
}


// Fibonacci 
int Fib(int n)
{
    
    if (n == 1 || n == 2) return 1;
    else return Fib(n - 1) + Fib(n - 2);
}
Console.WriteLine("=========== Fibonacci ===========");

Console.WriteLine(Fib(16));

// Use the cache 

int FibCache(int n)
{
    
    int[] cache = {
     0, 1, 1 };

    int _fib(int n)
    {
    
        if (cache[n] == 1) return cache[n];

        cache[n] = _fib(n - 1) + _fib(n - 2);

        return cache[n];

    }
    return _fib(n);
}

Console.WriteLine("=========== Fibonacci 2===========");

Console.WriteLine(Fib(16));

public class TreeNode
{
    
    public int val {
     get; set; }
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
    
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

result ：

1
3
2
======================
1
3
2
=========== Fibonacci ===========
987
=========== Fibonacci 2===========
987

D:\Csharp\ConsoleTest1\ConsoleTest1\bin\Debug\net6.0\ConsoleTest1.exe ( process  2356) Exited , The code is  0.
 To automatically close the console when debugging stops , Please enable “ Tools ”->“ Options ”->“ debugging ”->“ Automatically close the console when debugging stops ”.
 Press any key to close this window . . .